Horton Graphs

Author

Eric W. Weisstein
May 23, 2022

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/HortonGraphs.nb.

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

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

Figure

horton=GraphData["Horton*"]

Nonhamiltonian 3-regular 3-connected bipartite graphs:

Outer[GraphData,horton,{"#","Hamiltonian","Cubic","VertexConnectivity"}]//Column

GraphicsRow[Show[StyleGraphs@GraphData[#],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[14,Black,Italic,FontFamily->"Times"]]]]&/@horton,Dividers->All]

Embeddings

"HortonGraph92"

GraphData["HortonGraph92","StandardName"]

All

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

Halin

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

LCF

GraphData["HortonGraph92","LCFSignature"]

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

UnitDistance

GraphData["HortonGraph92","UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

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

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

Default embedding

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

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

RecognizeGraph[g]

MinimalCrossing construction

MinimalCrossingGraph[GraphData["HortonGraph92"],"CrossingNumber"->24]

3D default

Graph3D[GraphData["HortonGraph92","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["HortonGraph92","Polyhedral"]

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

"HortonGraph96"

GraphData["HortonGraph96","StandardName"]

All

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

Halin

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

LCF

GraphData["HortonGraph96","LCFSignature"]

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

UnitDistance

GraphData["HortonGraph96","UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

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

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

Default embedding

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

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

RecognizeGraph[g]

MinimalCrossing construction

MinimalCrossingGraph[GraphData["HortonGraph96"],"CrossingNumber"->26]

3D default

Graph3D[GraphData["HortonGraph96","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["HortonGraph96","Polyhedral"]

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