TOPICS

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 , complete graphs , , , and (e.g., Hearon 2016, p. 20) and the complete bipartite graphs , , , and . In particualr, the smallest complete graph that is not biplanar is , and the smallest complete bipartite graphs that are not biplanar are , , and (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 , edge count , and girth of a biplanar graph satisfy

 (1)
 (2)

and for a bipartite biplanar graph, satisfy

 (3)

(Beineke 1997).

Graph Thickness, Planar Graph

Explore with Wolfram|Alpha

More things to try:

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