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 G as a graph for which either G-e or G\e is planar, where G-e denotes edge deletion and G\E edge contraction.

Following Karpov (2013), call a k-planar graph a graph that can be drawn on the plane such that any edge intersects at most k 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 beta(n) be the maximum number of edges in a bipartite almost planar graph on n>=4 vertices, then

 beta(n)={3n-8   for even n!=6; 3n-9   for odd n or n=6

(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 K_(1,n), K_(2,n), K_(3,3), K_(3,4), K_(3,5), K_(3,6), and K_(4,4) (Karpov 2013).

See also

Graph Crossing Number, Planar Graph, Singlecross Graph

Explore with Wolfram|Alpha


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. "How to Construct a 5-Regular 1-Planar Bipartite Graph?" Sep. 10, 2022., 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., 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.

Subject classifications