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).