Ellingham-Horton Graphs

Author

Eric W. Weisstein
April 20, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Ellingham-HortonGraphs.nb.

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

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

Image

GraphData["Elling*"]

GraphicsRow[GraphData/@GraphData["Elling*"]//StyleGraphs,Dividers->All]

Properties

And@@@(GraphData[#,{"Bicubic","Nonhamiltonian"}]&/@GraphData["Elling*"])

GraphData[#,"VertexConnectivity"]&/@GraphData["Elling*"]

Embeddings

"EllinghamHortonGraph54"

GraphData["EllinghamHortonGraph54","StandardName"]

All

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

LCF

GraphData["EllinghamHortonGraph54","LCFSignature"]

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

UnitDistance

GraphData["EllinghamHortonGraph54","UnitDistance"]

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

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

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData["EllinghamHortonGraph54","Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData["EllinghamHortonGraph54"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{"EllinghamHortonGraph54",l=FindSubgraphUnitDistanceEmbedding[GraphData["EllinghamHortonGraph54"],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

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

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

3D

Graph3D[GraphData["EllinghamHortonGraph54","Edges"]]

Default embedding

g=Graph@GraphData["EllinghamHortonGraph54","Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData["EllinghamHortonGraph54"],"CrossingNumber"->14]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

"EllinghamHortonGraph78"

GraphData["EllinghamHortonGraph78","StandardName"]

All

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

LCF

GraphData["EllinghamHortonGraph78","LCFSignature"]

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

UnitDistance

GraphData["EllinghamHortonGraph78","UnitDistance"]

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

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

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData["EllinghamHortonGraph78","Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData["EllinghamHortonGraph78"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindSubgraphUnitDistanceEmbedding

{"EllinghamHortonGraph78",l=FindSubgraphUnitDistanceEmbedding[GraphData["EllinghamHortonGraph78"],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

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

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

3D

Graph3D[GraphData["EllinghamHortonGraph78","Edges"]]

Default embedding

g=Graph@GraphData["EllinghamHortonGraph78","Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData["EllinghamHortonGraph78"],"CrossingNumber"->18]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]