Biplanar Graph

Author

Eric W. Weisstein
February 11, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/BiplanarGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/BiplanarGraph.html.

©2021 Wolfram Research, Inc. except for portions noted otherwise

Sources

Beineke, L.W.  Biplanar Graphs: A Survey.  Computers & Mathematics with Applications
Volume 34, Issue 11, December 1997, Pages 1-8.

https://doi.org/10.1016/S0898-1221(97)00214-9

It is not easy to tell if a graph is biplanar or not.  Even deciding if a graph has thickness 2 is NP-complete.

https://scholarworks.lib.csusb.edu/cgi/viewcontent.cgi?article=1485&context=etd

Classes that are Biplanar

GraphClassesThatAreClass["Biplanar"]

Graphics

All

GraphicsGrid[Flatten[Partition[#,UpTo[6]]&/@Table[Show[StyleGraphs[GraphData[#]],PlotLabel->GraphData[#,"Name"],LabelStyle->Directive[Italic,Black,FontFamily->"Times"]]&/@GraphData["Biplanar",n],{n,6}],1],Dividers->All,ImageSize->600]

Connected

GraphicsGrid[Flatten[Partition[#,UpTo[6]]&/@Table[Show[StyleGraphs[GraphData[#]],PlotLabel->GraphData[#,"Name"],LabelStyle->Directive[Italic,Black,FontFamily->"Times"]]&/@GraphData[{"Connected","Biplanar"},n],{n,6}],1],Dividers->All,ImageSize->600]

Inequalities

From Beineke, L.W.  Biplanar Graphs: A Survey.  Computers & Mathematics with Applications
Volume 34, Issue 11, December 1997, Pages 1-8.

m≤6 n-12

Select[GraphData["Biplanar"],GraphData[#,"M"]>6GraphData[#,"V"]-12&]

m≤4n-8 (if G is bipartite)

GraphData[{"Biplanar","Bipartite"}]

Select[GraphData[{"Biplanar","Bipartite"}],GraphData[#,"M"]>4GraphData[#,"V"]-8&]

m≤2g(n-2)/(g-2) (if the girth of G is at least g)

Select[GraphData["Biplanar"],GraphData[#,"M"]>((2GraphData[#,"Girth"](GraphData[#,"V"]-2))/(GraphData[#,"Girth"]-2))&]

Examples

Complete

GraphData[{"Biplanar","Complete"}]

CompleteBipartite

GraphData[{"Biplanar","CompleteBipartite"}]

DeleteCases[%,{"CompleteBipartite",{m_,n_}}/;m=!=n]