Almost Planar Graph

Author

Eric W. Weisstein
September 11, 2022

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

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

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

Source

Karpov

https://arxiv.org/pdf/1307.1013.pdf

Definition 1. 1) Let k be a nonnegative integer. We say that a graph is k-planar, if it can be drawn on the plane such that any edge intersects at most k other edges.

For k = 1 we call such graph almost planar.

Mathoverflow

https://mathoverflow.net/questions/430153/how-to-construct-a-5-regular-1-planar-bipartite-graph

GraphData[#,"Graph","3D"]&/{"Quintic",{32,1}}

Embeddings

Used to construction almost planar bipartite quintic graphs {"Quintic", {32, 1 | 2}}

GraphData["AlmostPlanarCapGraph","StandardName"]

Primary

GraphData["AlmostPlanarCapGraph"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["AlmostPlanarCapGraph","Graph","All"]//StyleGraphs

Construction from source

https://mathoverflow.net/questions/430153/how-to-construct-a-5-regular-1-planar-bipartite-graph

v=Join[CirclePoints[{Csc[Pi/12]/2,-Pi/2},12],CirclePoints[{((Sqrt[2+(Sqrt[3])])/2),-Pi/2},4]];
g=Graph[Range[Length[v]],Sort[UndirectedEdge@@@Sort/@{e[{1,12},1,13,14,15,16,13],e[11,13,3],e[2,14,6],e[9,15,5],e[8,16,12],{7,15},{4,14},{10,16}}],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Default embedding

GraphPlot@GraphData["AlmostPlanarCapGraph","Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData["AlmostPlanarCapGraph","EdgeList"]]

Degenerate

GraphData["AlmostPlanarCapGraph","Graph","Degenerate"]//StyleGraphs

Circular

GraphData["AlmostPlanarCapGraph","Graph","Circular"]//StyleGraphs

Planar

GraphData["AlmostPlanarCapGraph","Planar"]

GraphData["AlmostPlanarCapGraph","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["AlmostPlanarCapGraph",{"RCN","CN"}]

GraphData["AlmostPlanarCapGraph","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

CrossingNumber[GraphData["AlmostPlanarCapGraph"],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData["AlmostPlanarCapGraph"],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData["AlmostPlanarCapGraph"],"CrossingNumber"->4]]

RecognizeGraph[g]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["AlmostPlanarCapGraph","Circulant"]

GraphData["AlmostPlanarCapGraph","NotationRules","Circulant"]

Halin

GraphData["AlmostPlanarCapGraph","Halin"]

GraphData["AlmostPlanarCapGraph","Graph","Halin"]//StyleGraphs

LCF

GraphData["AlmostPlanarCapGraph","LCF"]

GraphData["AlmostPlanarCapGraph","Regular"]

GraphData["AlmostPlanarCapGraph","Hamiltonian"]

GraphData["AlmostPlanarCapGraph","LCFSignature"]

GraphData["AlmostPlanarCapGraph","Graph","LCF"]//StyleGraphs

UnitDistance

GraphData["AlmostPlanarCapGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["AlmostPlanarCapGraph"],Debug->True]//Timing

GraphData["AlmostPlanarCapGraph","Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData["AlmostPlanarCapGraph","Matchstick"]

GraphData["AlmostPlanarCapGraph","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["AlmostPlanarCapGraph","Edges"]]

3D All

GraphData["AlmostPlanarCapGraph","Graph",{"3D","All"}]

3D UnitDistance

GraphData["AlmostPlanarCapGraph","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["AlmostPlanarCapGraph","Polyhedral"]

GraphData["AlmostPlanarCapGraph","Graph",{"3D","Polyhedron"}]

Quintic bipartite almost planar

SortBy[GraphData[{"Quintic","Connected","Bipartite","Nonplanar"}],GraphData[#,"V"]&]

GraphicsRow[Table[VertexColoredGraph[g=GraphData[{"Quintic",{32,n}},"Graph","3D"],FindVertexColoring[g],"VertexColors"->{Red,Black},VertexSize->.2,EdgeStyle->GrayLevel[.4]],{n,2}]]