TOPICS
Search

Biplanar Graph


A biplanar graph is defined as a graph that is the graph union of two planar edge-induced subgraphs. In other words, biplanar graphs are graphs with graph thickness 1 or 2 (e.g., Beineke 1997). Note that by this definition, planar graphs are considered (trivial) biplanar graphs.

Examples of nontrivial biplanar graphs include the Möbius ladders M_n, complete graphs K_5, K_6, K_7, and K_8 (e.g., Hearon 2016, p. 20) and the complete bipartite graphs K_(3,3), K_(4,4), K_(5,5), and K_(6,6). In particualr, the smallest complete graph that is not biplanar is K_9, and the smallest complete bipartite graphs that are not biplanar are K_(7,7), K_(6,9), and K_(5,12) (Hearon 2016, p. 19).

Determining if a graph is biplanar is an NP-complete problem (Mansfeld 1983, Beineke 1997). The precomputed Boolean status for a graph being nontrivially biplanar (i.e., biplanar but not planar) can be obtained for many small named or indexed graphs in the Wolfram Language using GraphData[graph, "Biplanar"].

The vertex count n, edge count m, and girth g of a biplanar graph satisfy

 m<=6n-12
(1)
 m<=(2g(n-2))/(g-2),
(2)

and for a bipartite biplanar graph, satisfy

 m<=4n-8
(3)

(Beineke 1997).


See also

Graph Thickness, Planar Graph

Explore with Wolfram|Alpha

References

Beineke, L. W. "'Biplanar Graphs: A Survey." Computers Math. Appl. 34, 1-8, 1997.Hearon, S. M. "Planar Graphs, Biplanar Graphs and Graph Thickness." Master of Arts thesis. San Bernadino, CA: California State University, San Bernadino, 2016.Mansfeld, A. "Determining the Thickness of a Graph is NP-Hard." Math. Proc. Cambridge Philos. Soc. 93, 9-23, 1983.

Cite this as:

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

Subject classifications