 TOPICS  # Almost Planar Graph

Several differing definitions of almost planar (as well as nearly planar) have been used in the literature (cf. Lipton et al. 2016).

For example, Gubser (1996) defines an almost planar graph as a graph for which either or is planar, where denotes edge deletion and edge contraction.

Following Karpov (2013), call a -planar graph a graph that can be drawn on the plane such that any edge intersects at most other edges (Pach and Tóth 1997, Karpov 2013). A 0-planar graph then corresponds to a planar graph and a 1-planar graph can be termed an almost planar graph (Karpov 2013), a convention adopted here.

Letting be the maximum number of edges in a bipartite almost planar graph on vertices, then (1)

(Karpov 2013). It follows that the minimum degree of any 1-planar bipartite graph is at most 5 and its vertex count is at least 16. It appears that none of the 41 quintic bipartite graphs on 16 vertices is 1-planar and the smallest known example of a quintic bipartite 1-planar graph as of Sep. 2022 has 32 vertices (illustrated below; LeechLattice 2022). The only complete bipartite graphs that are almost planar are , , , , , , and (Karpov 2013).

Graph Crossing Number, Planar Graph, Singlecross Graph

## Explore with Wolfram|Alpha More things to try:

## References

Gubser, B. S. "A Characterization of Almost-Planar Graphs." Combin. Prob. Comput. 5, 227-245, 1996.Karpov, D. V. "Upper Bound on the Number of Edges of an Almost Planar Bipartite Graph." 3 Jul 2013. https://arxiv.org/abs/1307.1013.LeechLattice. "How to Construct a 5-Regular 1-Planar Bipartite Graph?" Sep. 10, 2022. https://mathoverflow.net/questions/430153/how-to-construct-a-5-regular-1-planar-bipartite-graph.Lipton, M.; Mackall, E; Mattman, T. W.; Pierce, M.; Robinson, S.; Thomas, J.; and Weinschelbaum, I. "Six Variations on a Theme: Almost Planar Graphs." 5 Aug 2016. https://arxiv.org/abs/1608.01973.Pach, J. and Tóth. "Graphs Drawn With Few Crossing Per Edge." Combinatorica 17, 427-439, 1997.

## Cite this as:

Weisstein, Eric W. "Almost Planar Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AlmostPlanarGraph.html