Cage Graph

Author

Eric W. Weisstein
March 10, 2024

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

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

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

List

GraphData["Cage"]

Length[%]

nontrivial=SortBy[Complement[GraphData["Cage"],Join@@(GraphData/@{"Complete","CompleteBipartite"})],GraphData[#,"V"]&]

Royle

https://web.archive.org/web/20090125032457/http://people.csse.uwa.edu.au/gordon/cages/allcages.html

= means known to be minimal

Graphic

GraphicsGrid[Partition[Show[StyleGraphs[GraphData[#],VertexSize->Scaled[.05]],PlotLabel->Style[GraphData[#,"Name"],Black,Italic,FontFamily->"Times"]]&/@Select[nontrivial,GraphData[#,"Embeddings"]=!={}&],UpTo[5]],ImageSize->600]

Embeddings

<<MathWorld`Graphs`

{"Cage", {3, 9}, 1}

GraphData[{"Cage",{3,9},1},"StandardName"]

All

GraphData[{"Cage",{3,9},1},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},1},"LCFSignature"]

GraphData[{"Cage",{3,9},1},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},1},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},1}],Debug->True]//Timing

GraphData[{"Cage",{3,9},1},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},1}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},1},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},1}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},1},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},1},{"RCN","CN"}]

GraphData[{"Cage",{3,9},1},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},1},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},1},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},1}],"CrossingNumber"->36]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 2}

GraphData[{"Cage",{3,9},2},"StandardName"]

All

GraphData[{"Cage",{3,9},2},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},2},"LCFSignature"]

GraphData[{"Cage",{3,9},2},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},2},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},2}],Debug->True]//Timing

GraphData[{"Cage",{3,9},2},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},2}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},2},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},2}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},2},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},2},{"RCN","CN"}]

GraphData[{"Cage",{3,9},2},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},2},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},2},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},2}],"CrossingNumber"->35]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 3}

GraphData[{"Cage",{3,9},3},"StandardName"]

All

GraphData[{"Cage",{3,9},3},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},3},"LCFSignature"]

GraphData[{"Cage",{3,9},3},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},3},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},3}],Debug->True]//Timing

GraphData[{"Cage",{3,9},3},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},3}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},3},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},3},{"RCN","CN"}]

GraphData[{"Cage",{3,9},3},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},3},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},3},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},3}],"CrossingNumber"->35]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 4}

GraphData[{"Cage",{3,9},4},"StandardName"]

All

GraphData[{"Cage",{3,9},4},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},4},"LCFSignature"]

GraphData[{"Cage",{3,9},4},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},4},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},4}],Debug->True]//Timing

GraphData[{"Cage",{3,9},4},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},4}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},4},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},4}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},4},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},4},{"RCN","CN"}]

GraphData[{"Cage",{3,9},4},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},4},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},4},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},4}],"CrossingNumber"->35]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 5}

GraphData[{"Cage",{3,9},5},"StandardName"]

All

GraphData[{"Cage",{3,9},5},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},5},"LCFSignature"]

GraphData[{"Cage",{3,9},5},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},5},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},5}],Debug->True]//Timing

GraphData[{"Cage",{3,9},5},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},5}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},5},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},5}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},5},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},5},{"RCN","CN"}]

GraphData[{"Cage",{3,9},5},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},5},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},5},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},5}],"CrossingNumber"->35]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 6}

GraphData[{"Cage",{3,9},6},"StandardName"]

All

GraphData[{"Cage",{3,9},6},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},6},"LCFSignature"]

GraphData[{"Cage",{3,9},6},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},6},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},6}],Debug->True]//Timing

GraphData[{"Cage",{3,9},6},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},6}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},6},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},6}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},6},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},6},{"RCN","CN"}]

GraphData[{"Cage",{3,9},6},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},6},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},6},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},6}],"CrossingNumber->36"]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 7}

GraphData[{"Cage",{3,9},7},"StandardName"]

All

GraphData[{"Cage",{3,9},7},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},7},"LCFSignature"]

GraphData[{"Cage",{3,9},7},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},7},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},7}],Debug->True]//Timing

GraphData[{"Cage",{3,9},7},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},7}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},7},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},7}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},7},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},7},{"RCN","CN"}]

GraphData[{"Cage",{3,9},7},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},7},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},7},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},7}],"CrossingNumber"->34]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 8}

GraphData[{"Cage",{3,9},8},"StandardName"]

All

GraphData[{"Cage",{3,9},8},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},8},"LCFSignature"]

GraphData[{"Cage",{3,9},8},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},8},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},8}],Debug->True]//Timing

GraphData[{"Cage",{3,9},8},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},8}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},8},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},8}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},8},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},8},{"RCN","CN"}]

GraphData[{"Cage",{3,9},8},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},8},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},8},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},8}],"CrossingNumber"->35]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 9}

GraphData[{"Cage",{3,9},9},"StandardName"]

All

GraphData[{"Cage",{3,9},9},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},9},"LCFSignature"]

GraphData[{"Cage",{3,9},9},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},9},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},9}],Debug->True]//Timing

GraphData[{"Cage",{3,9},9},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},9}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},9},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},9},{"RCN","CN"}]

GraphData[{"Cage",{3,9},9},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},9},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},9},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},9}],"CrossingNumber"->34]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 10}

GraphData[{"Cage",{3,9},10},"StandardName"]

All

GraphData[{"Cage",{3,9},10},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},10},"LCFSignature"]

GraphData[{"Cage",{3,9},10},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},10},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},10}],Debug->True]//Timing

GraphData[{"Cage",{3,9},10},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},10}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},10},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},10}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},10},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},10},{"RCN","CN"}]

GraphData[{"Cage",{3,9},10},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},10},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},10},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},10}],"CrossingNumber"->37]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 11}

GraphData[{"Cage",{3,9},11},"StandardName"]

All

GraphData[{"Cage",{3,9},11},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},11},"LCFSignature"]

GraphData[{"Cage",{3,9},11},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},11},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},11}],Debug->True]//Timing

GraphData[{"Cage",{3,9},11},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},11}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},11},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},11}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},11},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},11},{"RCN","CN"}]

GraphData[{"Cage",{3,9},11},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},11},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},11},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},11}],"CrossingNumber"->37]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 12}

GraphData[{"Cage",{3,9},12},"StandardName"]

All

GraphData[{"Cage",{3,9},12},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},12},"LCFSignature"]

GraphData[{"Cage",{3,9},12},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},12},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},12}],Debug->True]//Timing

GraphData[{"Cage",{3,9},12},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},12}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},12},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},12}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},12},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},12},{"RCN","CN"}]

GraphData[{"Cage",{3,9},12},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},12},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},12},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},12}],"CrossingNumber"->33]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 13}

GraphData[{"Cage",{3,9},13},"StandardName"]

All

GraphData[{"Cage",{3,9},13},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},13},"LCFSignature"]

GraphData[{"Cage",{3,9},13},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},13},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},13}],Debug->True]//Timing

GraphData[{"Cage",{3,9},13},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},13}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},13},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},13}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},13},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},13},{"RCN","CN"}]

GraphData[{"Cage",{3,9},13},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},13},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},13},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},13}],"CrossingNumber"->34]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 14}

GraphData[{"Cage",{3,9},14},"StandardName"]

All

GraphData[{"Cage",{3,9},14},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},14},"LCFSignature"]

GraphData[{"Cage",{3,9},14},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},14},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},14}],Debug->True]//Timing

GraphData[{"Cage",{3,9},14},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},14}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},14},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},14}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},14},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},14},{"RCN","CN"}]

GraphData[{"Cage",{3,9},14},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},14},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},14},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},14}],"CrossingNumber"->35]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 15}

GraphData[{"Cage",{3,9},15},"StandardName"]

All

GraphData[{"Cage",{3,9},15},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},15},"LCFSignature"]

GraphData[{"Cage",{3,9},15},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},15},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},15}],Debug->True]//Timing

GraphData[{"Cage",{3,9},15},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},15}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},15},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},15}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},15},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},15},{"RCN","CN"}]

GraphData[{"Cage",{3,9},15},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},15},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},15},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},15}],"CrossingNumber"->34]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 16}

GraphData[{"Cage",{3,9},16},"StandardName"]

All

GraphData[{"Cage",{3,9},16},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},16},"LCFSignature"]

GraphData[{"Cage",{3,9},16},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},16},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},16}],Debug->True]//Timing

GraphData[{"Cage",{3,9},16},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},16}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},16},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},16}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},16},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},16},{"RCN","CN"}]

GraphData[{"Cage",{3,9},16},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},16},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},16},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},16}],"CrossingNumber"->37]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 17}

GraphData[{"Cage",{3,9},17},"StandardName"]

All

GraphData[{"Cage",{3,9},17},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},17},"LCFSignature"]

GraphData[{"Cage",{3,9},17},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},17},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},17}],Debug->True]//Timing

GraphData[{"Cage",{3,9},17},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},17}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},17},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},17}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},17},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},17},{"RCN","CN"}]

GraphData[{"Cage",{3,9},17},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},17},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},17},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},17}],"CrossingNumber"->37]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 9}, 18}

GraphData[{"Cage",{3,9},18},"StandardName"]

All

GraphData[{"Cage",{3,9},18},"Graph","All"]//StyleGraphs

LCF

GraphData[{"Cage",{3,9},18},"LCFSignature"]

GraphData[{"Cage",{3,9},18},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cage",{3,9},18},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,9},18}],Debug->True]//Timing

GraphData[{"Cage",{3,9},18},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,9},18}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

{{"Cage",{3,9},18},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cage",{3,9},18}],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,9},18},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,9},18},{"RCN","CN"}]

GraphData[{"Cage",{3,9},18},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"Cage",{3,9},18},"Edges"]]

Default embedding

g=Graph@GraphData[{"Cage",{3,9},18},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,9},18}],"CrossingNumber"->35]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"Cage", {3, 13}}

Names

GraphData[{"Cage",{3,13}},"StandardName"]

GraphData[{"Cage",{3,13}},"StandardNames"]

Primary

GraphData[{"Cage",{3,13}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{3,13}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{3,13}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{3,13}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{3,13}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{3,13}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{3,13}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{3,13}},"Configuration"]

GraphData[{"Cage",{3,13}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{3,13}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{3,13}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{3,13}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{3,13}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{3,13}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{3,13}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{3,13}},"Planar"]

GraphData[{"Cage",{3,13}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,13}},{"RCN","CN"}]

GraphData[{"Cage",{3,13}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{3,13}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{3,13}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{3,13}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{3,13}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{3,13}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{3,13}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,13}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{3,13}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{3,13}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{3,13}},"Circulant"]

GraphData[{"Cage",{3,13}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{3,13}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{3,13}},"Line"]

LineGraphQ[GraphData[{"Cage",{3,13}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{3,13}}&]

RootGraph[GraphData[{"Cage",{3,13}}]]

Halin

GraphData[{"Cage",{3,13}},"Halin"]

GraphData[{"Cage",{3,13}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{3,13}},"Rigid"]

GraphData[{"Cage",{3,13}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{3,13}},"Flexible"]

GraphData[{"Cage",{3,13}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{3,13}},"LCF"]

GraphData[{"Cage",{3,13}},"HamiltonianCycleCount"]

GraphData[{"Cage",{3,13}},"LCFSignature"]

GraphData[{"Cage",{3,13}},"LCFNotations"]

GraphData[{"Cage",{3,13}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{3,13}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{3,13}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Cage",{3,13}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Cage",{3,13}}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,3,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{3,13}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{3,13}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{3,13}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{3,13}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{3,13}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{3,13}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,13}}],Debug->True]//Timing

GraphData[{"Cage",{3,13}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{3,13}},"VertexList"],GraphData[{"Cage",{3,13}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{3,13}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,13}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,13}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cage",{3,13}},"Matchstick"]

GraphData[{"Cage",{3,13}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{3,13}},"Edges"]]

3D All

GraphData[{"Cage",{3,13}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{3,13}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{3,13}},"Polyhedral"]

GraphData[{"Cage",{3,13}},"Graph",{"3D","Polyhedron"}]

{"Cage", {3, 14}}

Names

GraphData[{"Cage",{3,14}},"StandardName"]

GraphData[{"Cage",{3,14}},"StandardNames"]

Primary

GraphData[{"Cage",{3,14}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{3,14}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{3,14}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{3,14}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{3,14}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{3,14}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{3,14}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{3,14}},"Configuration"]

GraphData[{"Cage",{3,14}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{3,14}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{3,14}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{3,14}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{3,14}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{3,14}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{3,14}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{3,14}},"Planar"]

GraphData[{"Cage",{3,14}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{3,14}},{"RCN","CN"}]

GraphData[{"Cage",{3,14}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{3,14}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{3,14}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{3,14}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{3,14}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{3,14}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{3,14}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{3,14}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{3,14}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{3,14}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{3,14}},"Circulant"]

GraphData[{"Cage",{3,14}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{3,14}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{3,14}},"Line"]

LineGraphQ[GraphData[{"Cage",{3,14}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{3,14}}&]

RootGraph[GraphData[{"Cage",{3,14}}]]

Halin

GraphData[{"Cage",{3,14}},"Halin"]

GraphData[{"Cage",{3,14}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{3,14}},"Rigid"]

GraphData[{"Cage",{3,14}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{3,14}},"Flexible"]

GraphData[{"Cage",{3,14}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{3,14}},"LCF"]

GraphData[{"Cage",{3,14}},"HamiltonianCycleCount"]

GraphData[{"Cage",{3,14}},"LCFSignature"]

GraphData[{"Cage",{3,14}},"LCFNotations"]

GraphData[{"Cage",{3,14}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{3,14}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{3,14}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{3,14}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{3,14}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{3,14}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{3,14}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{3,14}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{3,14}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{3,14}}],Debug->True]//Timing

GraphData[{"Cage",{3,14}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{3,14}},"VertexList"],GraphData[{"Cage",{3,14}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{3,14}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,14}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{3,14}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{3,14}},"Matchstick"]

GraphData[{"Cage",{3,14}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{3,14}},"Edges"]]

3D All

GraphData[{"Cage",{3,14}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{3,14}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{3,14}},"Polyhedral"]

GraphData[{"Cage",{3,14}},"Graph",{"3D","Polyhedron"}]

{"Cage", {4, 6}}

Names

GraphData[{"Cage",{4,6}},"StandardName"]

GraphData[{"Cage",{4,6}},"StandardNames"]

Primary

GraphData[{"Cage",{4,6}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{4,6}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{4,6}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{4,6}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{4,6}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{4,6}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{4,6}},"Graph","Degenerate"]

Perspective

GraphData[{"Cage",{4,6}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{4,6}},"Polyhedron"]

Bilateral

GraphData[{"Cage",{4,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{4,6}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{4,6}},"Planar"]

GraphData[{"Cage",{4,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{4,6}},{"RCN","CN"}]

GraphData[{"Cage",{4,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{4,6}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{4,6}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{4,6}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{4,6}}],"CrossingNumber"->cn,RandomSeed->n]],{n,500}],Max[OuterFace[#]]<=GraphData[{"Cage",{4,6}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{4,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{4,6}},"Circulant"]

GraphData[{"Cage",{4,6}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"Cage",{4,6}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{4,6}},"Line"]

LineGraphQ[GraphData[{"Cage",{4,6}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{4,6}}&]

RootGraph[GraphData[{"Cage",{4,6}}]]

Halin

GraphData[{"Cage",{4,6}},"Halin"]

GraphData[{"Cage",{4,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{4,6}},"Rigid"]

GraphData[{"Cage",{4,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{4,6}},"Flexible"]

GraphData[{"Cage",{4,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{4,6}},"LCF"]

GraphData[{"Cage",{4,6}},"HamiltonianCycleCount"]

GraphData[{"Cage",{4,6}},"LCFSignature"]

GraphData[{"Cage",{4,6}},"LCFNotations"]

GraphData[{"Cage",{4,6}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute all

Divisors[GraphData[{"Cage",{4,6}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{4,6}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{4,6}}],All])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{4,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{4,6}}],Debug->True]//Timing

GraphData[{"Cage",{4,6}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{4,6}},"VertexList"],GraphData[{"Cage",{4,6}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{4,6}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{4,6}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{4,6}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{4,6}},"Matchstick"]

GraphData[{"Cage",{4,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{4,6}},"Edges"]]

3D All

GraphData[{"Cage",{4,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{4,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{4,6}},"Polyhedral"]

GraphData[{"Cage",{4,6}},"Graph",{"3D","Polyhedron"}]

{"Cage", {4, 7}}

GraphData[{"Cage",{4,7}},"Graph","All"]

{"Cage", {4, 8}}

GraphData[{"Cage",{4,8}},"Graph","All"]

LCFFromEmbedding@

LCF

From Ed Pegg, Jr.
Mar 28, 2021

So, I had the 5-symmetric embedding.

For a symmetric LCF embedding to exist, I needed 5 disjoint 16-cycles.  Or 10 disjoint 8-cycles, but that didn't seem to work.

I used FindCycle  to get all the 16 cycles, then applied Norm[Mean[ ]] on all of the cycles to group them.  They nicely grouped into batches of 5 and 10.

Then some code-massaging on the disjoint sets of 5 16-cycles to get start-end points symmetrically equivalent.
Then looked for endpoints that matched up well.
I'd say I did the last two steps poorly, I probably missed a lot, but I just needed a few so i took what worked and called it a day.

I suppose that doing a look at all 8 cycles again could yield two batches of 5 8-cycles that were disjoint, and more symmetry might come from that.

ee={{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,8},{8,9},{9,10},{10,11},{11,12},{12,13},{13,14},{14,15},{15,16},{16,17},{17,18},{18,19},{19,20},{20,21},{21,22},{22,23},{23,24},{24,25},{25,26},{26,27},{27,28},{28,29},{29,30},{30,31},{31,32},{32,33},{33,34},{34,35},{35,36},{36,37},{37,38},{38,39},{39,40},{40,41},{41,42},{42,43},{43,44},{44,45},{45,46},{46,47},{47,48},{48,49},{49,50},{50,51},{51,52},{52,53},{53,54},{54,55},{55,56},{56,57},{57,58},{58,59},{59,60},{60,61},{61,62},{62,63},{63,64},{64,65},{65,66},{66,67},{67,68},{68,69},{69,70},{70,71},{71,72},{72,73},{73,74},{74,75},{75,76},{76,77},{77,78},{78,79},{79,80},{11,22},{27,38},{43,54},{59,70},{13,26},{29,42},{45,58},{61,74},{1,16},{6,21},{17,32},{22,37},{33,48},{38,53},{49,64},{54,69},{65,80},{9,28},{25,44},{41,60},{57,76},{2,23},{5,26},{11,32},{15,36},{18,39},{21,42},{27,48},{31,52},{34,55},{37,58},{43,64},{47,68},{50,71},{53,74},{59,80},{1,28},{4,31},{7,34},{14,41},{17,44},{20,47},{23,50},{30,57},{33,60},{36,63},{39,66},{46,73},{49,76},{52,79},{3,40},{8,45},{14,51},{19,56},{24,61},{30,67},{35,72},{40,77},{3,46},{8,51},{13,56},{19,62},{24,67},{29,72},{35,78},{2,55},{9,62},{12,65},{15,68},{18,71},{25,78},{4,63},{7,66},{10,69},{16,75},{20,79},{12,73},{5,70},{10,77},{6,75},{1,80}}

gg=Graph[Range[80], ee, VertexCoordinates->Thread[Range[80]-> CirclePoints[80]]]

g1=;

LCFFromEmbedding[g1]

IsomorphicGraphQ[gg, GraphData[{"Cage", {4, 8}}]]

alts={{{17,18,39,38,27,28,29,72,35,36,37,58,57,30,31,32},{33,34,55,54,43,44,45,8,51,52,53,74,73,46,47,48},{49,50,71,70,59,60,61,24,67,68,69,10,9,62,63,64},{65,66,7,6,75,76,77,40,3,4,5,26,25,78,79,80},{1,2,23,22,11,12,13,56,19,20,21,42,41,14,15,16}},{{38,39,66,65,80,79,52,51,14,41,40,77,76,75,74,53},{54,55,2,1,16,15,68,67,30,57,56,13,12,11,10,69},{70,71,18,17,32,31,4,3,46,73,72,29,28,27,26,5},{6,7,34,33,48,47,20,19,62,9,8,45,44,43,42,21},{22,23,50,49,64,63,36,35,78,25,24,61,60,59,58,37}},{{49,50,23,22,21,20,19,56,13,12,11,10,9,62,63,64},{65,66,39,38,37,36,35,72,29,28,27,26,25,78,79,80},{1,2,55,54,53,52,51,8,45,44,43,42,41,14,15,16},{17,18,71,70,69,68,67,24,61,60,59,58,57,30,31,32},{33,34,7,6,5,4,3,40,77,76,75,74,73,46,47,48}},{{49,50,23,24,67,68,15,14,41,60,61,74,53,54,43,64},{65,66,39,40,3,4,31,30,57,76,77,10,69,70,59,80},{1,2,55,56,19,20,47,46,73,12,13,26,5,6,75,16},{17,18,71,72,35,36,63,62,9,28,29,42,21,22,11,32},{33,34,7,8,51,52,79,78,25,44,45,58,37,38,27,48}},{{49,76,75,6,21,20,19,18,71,72,73,74,61,62,63,64},{65,12,11,22,37,36,35,34,7,8,9,10,77,78,79,80},{1,28,27,38,53,52,51,50,23,24,25,26,13,14,15,16},{17,44,43,54,69,68,67,66,39,40,41,42,29,30,31,32},{33,60,59,70,5,4,3,2,55,56,57,58,45,46,47,48}},{{70,71,72,73,12,11,32,17,18,19,20,79,78,77,10,69},{54,55,56,57,76,75,16,1,2,3,4,63,62,61,74,53},{38,39,40,41,60,59,80,65,66,67,68,47,46,45,58,37},{22,23,24,25,44,43,64,49,50,51,52,31,30,29,42,21},{6,7,8,9,28,27,48,33,34,35,36,15,14,13,26,5}}};

Table[Graph[Range[80], ee, VertexCoordinates->Thread[Flatten[alts[[k]]]-> CirclePoints[80]]],{k,1,6,1}]

gs={,,,,,};

LCFFromEmbedding/@gs

Configuration

https://www.researchgate.net/publication/338924957_ON_A_SMALLEST_TOPOLOGICAL_TRIANGLE_FREE_n_4_POINT-LINE_CONFIGURATION

ON A SMALLEST TOPOLOGICAL TRIANGLE FREE (n 4 ) POINT-LINE CONFIGURATION
January 2020
Jürgen BokowskiHendrik Van Maldeghem

Import["~/W31-2.pdf",{"PageGraphics",5}]

Import["~/W31-2.pdf","PageGraphics"]

Import["~/W31-2.pdf"][[5]]

Rings

From Ed Pegg, Jr.
Mar 28, 2021
Based on https://www.researchgate.net/publication/338924957_ON_A_SMALLEST_TOPOLOGICAL_TRIANGLE_FREE_n_4_POINT-LINE_CONFIGURATION

ON A SMALLEST TOPOLOGICAL TRIANGLE FREE (n 4 ) POINT-LINE CONFIGURATION
January 2020
Jürgen BokowskiHendrik Van Maldeghem

loop={68,24,43,25,73,19,62,35,71,22,74,34,77,27,63,39,59,29,67,33,70,17,79,13,49,3,51,31,72,16,78,30,64,18,76,12,75,36,65,21,58,38,66,28,60,7,61,26,47,23,55,4,56,32,48,2,45,5,53,10,69,40,57,6,41,1,42,14,46,20};
loop2 = {15,11,9,8,37};
loop3 ={44,50,80,52,54};
out2 ={{69,42,63,66},{73,74,72,45},{67,49,66,68},{64,65,45,63},{61,56,68,72}};
out3 ={{1,34,33,32},{22,3,18,14},{13,21,26,34},{36,32,40,3},{4,14,19,21}};
pos= Join[N[CirclePoints[70]], Table[RotationMatrix[2 n Pi/5].{-0.3777556436364167`,-0.5722753386490278`},{n,0,4}],
Table[RotationMatrix[2 n Pi/5].{0.2818875625697587`,-0.38130293883647604`},{n,0,4}]];
lab=Join[loop,loop2,loop3];
edge= UndirectedEdge@@@Join[Partition[loop,2,1,1], 
Flatten[Table[Transpose[{Table[loop2[[n]],{4}],out2[[n]]}],{n,1,5}],1],
Flatten[Table[Transpose[{Table[loop3[[n]],{4}],out3[[n]]}],{n,1,5}],1],
{{1,43},{42,16},{46,2},{46,17},{20,57},{20,77},{24,65},{24,71},{43,23},{25,76},{25,79},{73,40},
{19,67},{62,7},{62,27},{35,48},{35,78},{71,10},{22,59},{74,28},{77,12},{27,51},{6,59},{6,58},{41,5},{41,7},{39,56},{39,79},{29,47},{29,75},{33,64},{70,10},{70,31},{17,60},{49,5},{13,78},{30,57},{30,55},{51,23}, {69,26}, {53,12},{53,4},{2,47},{48,38},{55,28},{61,18},{60,36},{38,76},{58,31},{75,16}}];

g2=Graph[Range[80],edge,VertexCoordinates->Thread[lab-> pos]]

g2=;

RecognizeGraph[g]

{"Cage", {4, 9}}

Names

GraphData[{"Cage",{4,9}},"StandardName"]

GraphData[{"Cage",{4,9}},"StandardNames"]

Primary

GraphData[{"Cage",{4,9}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{4,9}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{4,9}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{4,9}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{4,9}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{4,9}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{4,9}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{4,9}},"Configuration"]

GraphData[{"Cage",{4,9}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{4,9}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{4,9}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{4,9}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{4,9}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{4,9}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{4,9}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{4,9}},"Planar"]

GraphData[{"Cage",{4,9}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{4,9}},{"RCN","CN"}]

GraphData[{"Cage",{4,9}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{4,9}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{4,9}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{4,9}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{4,9}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{4,9}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{4,9}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{4,9}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{4,9}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{4,9}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{4,9}},"Circulant"]

GraphData[{"Cage",{4,9}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{4,9}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{4,9}},"Line"]

LineGraphQ[GraphData[{"Cage",{4,9}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{4,9}}&]

RootGraph[GraphData[{"Cage",{4,9}}]]

Halin

GraphData[{"Cage",{4,9}},"Halin"]

GraphData[{"Cage",{4,9}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{4,9}},"Rigid"]

GraphData[{"Cage",{4,9}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{4,9}},"Flexible"]

GraphData[{"Cage",{4,9}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{4,9}},"LCF"]

GraphData[{"Cage",{4,9}},"HamiltonianCycleCount"]

GraphData[{"Cage",{4,9}},"LCFSignature"]

GraphData[{"Cage",{4,9}},"LCFNotations"]

GraphData[{"Cage",{4,9}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{4,9}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{4,9}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{4,9}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{4,9}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{4,9}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{4,9}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{4,9}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{4,9}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{4,9}}],Debug->True]//Timing

GraphData[{"Cage",{4,9}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{4,9}},"VertexList"],GraphData[{"Cage",{4,9}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{4,9}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{4,9}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{4,9}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{4,9}},"Matchstick"]

GraphData[{"Cage",{4,9}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{4,9}},"Edges"]]

3D All

GraphData[{"Cage",{4,9}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{4,9}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{4,9}},"Polyhedral"]

GraphData[{"Cage",{4,9}},"Graph",{"3D","Polyhedron"}]

{"Cage", {4, 10}}

Names

GraphData[{"Cage",{4,10}},"StandardName"]

GraphData[{"Cage",{4,10}},"StandardNames"]

Primary

GraphData[{"Cage",{4,10}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{4,10}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{4,10}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{4,10}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{4,10}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{4,10}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{4,10}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{4,10}},"Configuration"]

GraphData[{"Cage",{4,10}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{4,10}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{4,10}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{4,10}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{4,10}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{4,10}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{4,10}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{4,10}},"Planar"]

GraphData[{"Cage",{4,10}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{4,10}},{"RCN","CN"}]

GraphData[{"Cage",{4,10}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{4,10}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{4,10}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{4,10}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{4,10}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{4,10}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{4,10}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{4,10}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{4,10}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{4,10}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{4,10}},"Circulant"]

GraphData[{"Cage",{4,10}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{4,10}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{4,10}},"Line"]

LineGraphQ[GraphData[{"Cage",{4,10}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{4,10}}&]

RootGraph[GraphData[{"Cage",{4,10}}]]

Halin

GraphData[{"Cage",{4,10}},"Halin"]

GraphData[{"Cage",{4,10}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{4,10}},"Rigid"]

GraphData[{"Cage",{4,10}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{4,10}},"Flexible"]

GraphData[{"Cage",{4,10}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{4,10}},"LCF"]

GraphData[{"Cage",{4,10}},"HamiltonianCycleCount"]

GraphData[{"Cage",{4,10}},"LCFSignature"]

GraphData[{"Cage",{4,10}},"LCFNotations"]

GraphData[{"Cage",{4,10}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{4,10}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{4,10}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{4,10}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{4,10}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{4,10}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{4,10}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{4,10}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{4,10}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{4,10}}],Debug->True]//Timing

GraphData[{"Cage",{4,10}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{4,10}},"VertexList"],GraphData[{"Cage",{4,10}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{4,10}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{4,10}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{4,10}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{4,10}},"Matchstick"]

GraphData[{"Cage",{4,10}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{4,10}},"Edges"]]

3D All

GraphData[{"Cage",{4,10}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{4,10}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{4,10}},"Polyhedral"]

GraphData[{"Cage",{4,10}},"Graph",{"3D","Polyhedron"}]

{"Cage", {5, 6}}

Names

GraphData[{"Cage",{5,6}},"StandardName"]

GraphData[{"Cage",{5,6}},"StandardNames"]

Primary

GraphData[{"Cage",{5,6}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{5,6}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{5,6}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Cage",{5,6}},"Edges"]

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

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{5,6}},"EdgeList"]]

Degenerate

GraphData[{"Cage",{5,6}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Cage",{5,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{5,6}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{5,6}},"Planar"]

GraphData[{"Cage",{5,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{5,6}},{"RCN","CN"}]

GraphData[{"Cage",{5,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{5,6}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"Cage",{5,6}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Cage",{5,6}}],TimeConstraint->3600]//AbsoluteTiming

CrossingNumber[GraphData[{"Cage",{5,6}}],TimeConstraint->5 3600]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{5,6}}],"CrossingNumber"->cn]]

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{5,6}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{5,6}},"V"]&]]//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{5,6}},"Circulant"]

GraphData[{"Cage",{5,6}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{5,6}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{5,6}},"Line"]

LineGraphQ[GraphData[{"Cage",{5,6}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{5,6}}&]

RootGraph[GraphData[{"Cage",{5,6}}]]

Halin

GraphData[{"Cage",{5,6}},"Halin"]

GraphData[{"Cage",{5,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{5,6}},"Rigid"]

GraphData[{"Cage",{5,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{5,6}},"Flexible"]

GraphData[{"Cage",{5,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{5,6}},"LCF"]

GraphData[{"Cage",{5,6}},"HamiltonianCycleCount"]

GraphData[{"Cage",{5,6}},"LCFSignature"]

GraphData[{"Cage",{5,6}},"LCFNotations"]

GraphData[{"Cage",{5,6}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{5,6}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{5,6}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,3,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{5,6}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Cage",{5,6}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

LCFGraph@@@DeleteCases[lcf,{_,1|2}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,3,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{5,6}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Cage",{5,6}}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

LCFGraph@@@DeleteCases[lcf,{_,1|2}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,4,3])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{5,6}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

LCF compute 5*^7

Tally[(lcf=LCF[GraphData[{"Cage",{5,6}}],5*^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2|3}]

LCFGraph@@@DeleteCases[lcf,{_,1|2|3}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,4])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{5,6}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{5,6}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{5,6}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{5,6}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{5,6}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{5,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{5,6}}],Debug->True]//Timing

GraphData[{"Cage",{5,6}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData[{"Cage",{5,6}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Cage",{5,6}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{5,6}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{5,6}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{5,6}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{5,6}},"Matchstick"]

GraphData[{"Cage",{5,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{5,6}},"Edges"]]

3D All

GraphData[{"Cage",{5,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{5,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{5,6}},"Polyhedral"]

GraphData[{"Cage",{5,6}},"Graph",{"3D","Polyhedron"}]

{"Cage", {6, 5}}

Names

GraphData[{"Cage",{6,5}},"StandardName"]

GraphData[{"Cage",{6,5}},"StandardNames"]

Primary

GraphData[{"Cage",{6,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{6,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{6,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Cage",{6,5}},"Edges"]

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

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{6,5}},"EdgeList"]]

Degenerate

GraphData[{"Cage",{6,5}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Cage",{6,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{6,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{6,5}},"Planar"]

GraphData[{"Cage",{6,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{6,5}},{"RCN","CN"}]

GraphData[{"Cage",{6,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{6,5}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"Cage",{6,5}}],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{6,5}}],"CrossingNumber"->cn]]

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{6,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{6,5}},"V"]&]]//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{6,5}},"Circulant"]

GraphData[{"Cage",{6,5}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Cage",{6,5}},"Halin"]

GraphData[{"Cage",{6,5}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Cage",{6,5}},"LCF"]

GraphData[{"Cage",{6,5}},"HamiltonianCycleCount"]

GraphData[{"Cage",{6,5}},"LCFSignature"]

GraphData[{"Cage",{6,5}},"LCFNotations"]

GraphData[{"Cage",{6,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{6,5}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Cage",{6,5}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Cage",{6,5}}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Cage",{6,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{6,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{6,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{6,5}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

UnitDistance

GraphData[{"Cage",{6,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{6,5}}],Debug->True]//Timing

GraphData[{"Cage",{6,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData[{"Cage",{6,5}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Cage",{6,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{6,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{6,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{6,5}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{6,5}},"Matchstick"]

GraphData[{"Cage",{6,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{6,5}},"Edges"]]

3D All

GraphData[{"Cage",{6,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{6,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{6,5}},"Polyhedral"]

GraphData[{"Cage",{6,5}},"Graph",{"3D","Polyhedron"}]

{"Cage", {6, 6}}

GraphData[{"Cage",{6,6}},"StandardName"]

Primary

GraphData[{"Cage",{6,6}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{6,6}},"Graph","All"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Cage",{6,6}},"Edges"]

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

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{6,6}},"EdgeList"]]

Degenerate

GraphData[{"Cage",{6,6}},"Graph","Degenerate"]//StyleGraphs

Circular

GraphData[{"Cage",{6,6}},"Graph","Circular"]//StyleGraphs

Circular construction

Ed Pegg 2019-04-18

On 4/18/19 12:21 PM, 
> Here's a nice embedding of the 6,6 cage graph.   It can be built from the order-6 difference set
>
> IsomorphicGraphQ[GraphData[{"Cage", {6, 6}}],
>   Graph[Range[62], Flatten[Table[{Mod[{1, 5, 11, 24, 25, 27}[[n]] + k + 6, 31, 1], (k + 31)}, {n, 1, 6}, {k, 1, 31}], 1],
>    VertexCoordinates -> Join[-CirclePoints[31], CirclePoints[31] ]]]

g1=Graph[Range[62],Flatten[Table[{Mod[{1,5,11,24,25,27}[[n]]+k+6,31,1],(k+31)},{n,1,6},{k,1,31}],1],VertexCoordinates->Join[-CirclePoints[31],CirclePoints[31]]]

g2=Graph[Range[62],Flatten[Table[{Mod[{1,5,11,24,25,27}[[n]]+k+22,31,1],(k+31)},{n,1,6},{k,1,31}],1],VertexCoordinates->Join[-CirclePoints[31],CirclePoints[31]]]

Planar

GraphData[{"Cage",{6,6}},"Planar"]

GraphData[{"Cage",{6,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{6,6}},{"RCN","CN"}]

GraphData[{"Cage",{6,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{6,6}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"Cage",{6,6}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Cage",{6,6}}],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{6,6}}],"CrossingNumber"->cn]]

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{6,6}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{6,6}},"V"]&]]//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{6,6}},"Circulant"]

GraphData[{"Cage",{6,6}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Cage",{6,6}},"Halin"]

GraphData[{"Cage",{6,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Cage",{6,6}},"LCF"]

GraphData[{"Cage",{6,6}},"LCFSignature"]

GraphData[{"Cage",{6,6}},"Graph","LCF"]//StyleGraphs

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Cage",{6,6}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{6,6}}],All])[[All,2]]]

gs=LCFGraph@@@DeleteCases[lcf,{_,1|2}]

UnitDistance

GraphData[{"Cage",{6,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{6,6}}],Debug->True]//Timing

GraphData[{"Cage",{6,6}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData[{"Cage",{6,6}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Cage",{6,6}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{6,6}}],MaxIterations->1000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{6,6}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{6,6}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{6,6}},"Matchstick"]

GraphData[{"Cage",{6,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{6,6}},"Edges"]]

3D All

GraphData[{"Cage",{6,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{6,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{6,6}},"Polyhedral"]

GraphData[{"Cage",{6,6}},"Graph",{"3D","Polyhedron"}]

{"Cage", {8, 5}}

Names

GraphData[{"Cage",{8,5}},"StandardName"]

GraphData[{"Cage",{8,5}},"StandardNames"]

Primary

GraphData[{"Cage",{8,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{8,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{8,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{8,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{8,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{8,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{8,5}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{8,5}},"Configuration"]

GraphData[{"Cage",{8,5}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{8,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{8,5}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{8,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{8,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{8,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{8,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{8,5}},"Planar"]

GraphData[{"Cage",{8,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{8,5}},{"RCN","CN"}]

GraphData[{"Cage",{8,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{8,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{8,5}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{8,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{8,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{8,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{8,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{8,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{8,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{8,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{8,5}},"Circulant"]

GraphData[{"Cage",{8,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{8,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{8,5}},"Line"]

LineGraphQ[GraphData[{"Cage",{8,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{8,5}}&]

RootGraph[GraphData[{"Cage",{8,5}}]]

Halin

GraphData[{"Cage",{8,5}},"Halin"]

GraphData[{"Cage",{8,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{8,5}},"Rigid"]

GraphData[{"Cage",{8,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{8,5}},"Flexible"]

GraphData[{"Cage",{8,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{8,5}},"LCF"]

GraphData[{"Cage",{8,5}},"HamiltonianCycleCount"]

GraphData[{"Cage",{8,5}},"LCFSignature"]

GraphData[{"Cage",{8,5}},"LCFNotations"]

GraphData[{"Cage",{8,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{8,5}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{8,5}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Cage",{8,5}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Cage",{8,5}}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{8,5}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{8,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{8,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{8,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{8,5}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{8,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{8,5}}],Debug->True]//Timing

GraphData[{"Cage",{8,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{8,5}},"VertexList"],GraphData[{"Cage",{8,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{8,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{8,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{8,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{8,5}},"Matchstick"]

GraphData[{"Cage",{8,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{8,5}},"Edges"]]

3D All

GraphData[{"Cage",{8,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{8,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{8,5}},"Polyhedral"]

GraphData[{"Cage",{8,5}},"Graph",{"3D","Polyhedron"}]

{"Cage", {8, 6}}

Names

GraphData[{"Cage",{8,6}},"StandardName"]

GraphData[{"Cage",{8,6}},"StandardNames"]

Primary

GraphData[{"Cage",{8,6}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{8,6}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{8,6}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{8,6}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{8,6}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{8,6}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{8,6}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{8,6}},"Configuration"]

GraphData[{"Cage",{8,6}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{8,6}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{8,6}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{8,6}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{8,6}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{8,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{8,6}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{8,6}},"Planar"]

GraphData[{"Cage",{8,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{8,6}},{"RCN","CN"}]

GraphData[{"Cage",{8,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{8,6}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{8,6}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{8,6}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{8,6}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{8,6}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{8,6}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{8,6}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{8,6}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{8,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{8,6}},"Circulant"]

GraphData[{"Cage",{8,6}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{8,6}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{8,6}},"Line"]

LineGraphQ[GraphData[{"Cage",{8,6}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{8,6}}&]

RootGraph[GraphData[{"Cage",{8,6}}]]

Halin

GraphData[{"Cage",{8,6}},"Halin"]

GraphData[{"Cage",{8,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{8,6}},"Rigid"]

GraphData[{"Cage",{8,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{8,6}},"Flexible"]

GraphData[{"Cage",{8,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{8,6}},"LCF"]

GraphData[{"Cage",{8,6}},"HamiltonianCycleCount"]

GraphData[{"Cage",{8,6}},"LCFSignature"]

GraphData[{"Cage",{8,6}},"LCFNotations"]

GraphData[{"Cage",{8,6}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

BilateralGraphEmbeddingQ/@%%

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{8,6}}],TimeConstraint->120]

LCF compute 10^4

Tally[(lcf=LCF[GraphData[{"Cage",{8,6}}],10^4])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{8,6}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{8,6}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Cage",{8,6}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Cage",{8,6}}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 2*^7

Tally[(lcf=LCF[GraphData[{"Cage",{8,6}}],2*^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{8,6}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{8,6}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{8,6}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{8,6}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{8,6}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{8,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{8,6}}],Debug->True]//Timing

GraphData[{"Cage",{8,6}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{8,6}},"VertexList"],GraphData[{"Cage",{8,6}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{8,6}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{8,6}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{8,6}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{8,6}},"Matchstick"]

GraphData[{"Cage",{8,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{8,6}},"Edges"]]

3D All

GraphData[{"Cage",{8,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{8,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{8,6}},"Polyhedral"]

GraphData[{"Cage",{8,6}},"Graph",{"3D","Polyhedron"}]

{"Cage", {9, 6}}

GraphData[{"Cage",{9,6}},"Graph","All"]

Ed Pegg 2019-04-18

g1=Graph[Range[146],Flatten[Table[{Mod[{0,1,12,20,26,30,33,35,57}[[n]]+k+2,73,1],(k+73)},{n,1,9},{k,1,73}],1],VertexCoordinates->Join[-CirclePoints[73],CirclePoints[73]]]

g2=Graph[Range[146],Flatten[Table[{Mod[{0,1,12,20,26,30,33,35,57}[[n]]+k+36,73,1],(k+73)},{n,1,9},{k,1,73}],1],VertexCoordinates->Join[-CirclePoints[73],CirclePoints[73]]]

{r,r2}=RecognizeGraph/@{g1,g2}

{"Cage", {10, 5}}

Names

GraphData[{"Cage",{10,5}},"StandardName"]

GraphData[{"Cage",{10,5}},"StandardNames"]

Primary

GraphData[{"Cage",{10,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{10,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{10,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{10,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{10,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{10,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{10,5}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{10,5}},"Configuration"]

GraphData[{"Cage",{10,5}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{10,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{10,5}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{10,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{10,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{10,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{10,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{10,5}},"Planar"]

GraphData[{"Cage",{10,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{10,5}},{"RCN","CN"}]

GraphData[{"Cage",{10,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{10,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{10,5}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{10,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{10,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{10,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{10,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{10,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{10,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{10,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{10,5}},"Circulant"]

GraphData[{"Cage",{10,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{10,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{10,5}},"Line"]

LineGraphQ[GraphData[{"Cage",{10,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{10,5}}&]

RootGraph[GraphData[{"Cage",{10,5}}]]

Halin

GraphData[{"Cage",{10,5}},"Halin"]

GraphData[{"Cage",{10,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{10,5}},"Rigid"]

GraphData[{"Cage",{10,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{10,5}},"Flexible"]

GraphData[{"Cage",{10,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{10,5}},"LCF"]

GraphData[{"Cage",{10,5}},"HamiltonianCycleCount"]

GraphData[{"Cage",{10,5}},"LCFSignature"]

GraphData[{"Cage",{10,5}},"LCFNotations"]

GraphData[{"Cage",{10,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{10,5}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{10,5}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Cage",{10,5}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{10,5}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{10,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{10,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{10,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{10,5}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{10,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{10,5}}],Debug->True]//Timing

GraphData[{"Cage",{10,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{10,5}},"VertexList"],GraphData[{"Cage",{10,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{10,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{10,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{10,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{10,5}},"Matchstick"]

GraphData[{"Cage",{10,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{10,5}},"Edges"]]

3D All

GraphData[{"Cage",{10,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{10,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{10,5}},"Polyhedral"]

GraphData[{"Cage",{10,5}},"Graph",{"3D","Polyhedron"}]

{"Cage", {10, 6}}

Names

GraphData[{"Cage",{10,6}},"StandardName"]

GraphData[{"Cage",{10,6}},"StandardNames"]

Primary

GraphData[{"Cage",{10,6}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{10,6}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{10,6}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{10,6}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{10,6}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{10,6}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{10,6}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{10,6}},"Configuration"]

GraphData[{"Cage",{10,6}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{10,6}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{10,6}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{10,6}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{10,6}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{10,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{10,6}},"Graph","Circular"]//StyleGraphs

Circular construction

Ed Pegg 2019-04-18

g=Graph[
Range[182],
Flatten[Table[{Mod[{0,2,6,7,18,21,31,54,63,71}[[n]]+k+1,91,1],k+91},{n,10},{k,91}],1],
VertexCoordinates->Join[-CirclePoints[91],CirclePoints[91]]
]

RecognizeGraph@g

LCFGraphEmbeddingQ@g

Planar

GraphData[{"Cage",{10,6}},"Planar"]

GraphData[{"Cage",{10,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{10,6}},{"RCN","CN"}]

GraphData[{"Cage",{10,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{10,6}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{10,6}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{10,6}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{10,6}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{10,6}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{10,6}}],TimeConstraint->86400])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{10,6}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{10,6}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{10,6}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{10,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{10,6}},"Circulant"]

GraphData[{"Cage",{10,6}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{10,6}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{10,6}},"Line"]

LineGraphQ[GraphData[{"Cage",{10,6}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{10,6}}&]

RootGraph[GraphData[{"Cage",{10,6}}]]

Halin

GraphData[{"Cage",{10,6}},"Halin"]

GraphData[{"Cage",{10,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{10,6}},"Rigid"]

GraphData[{"Cage",{10,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{10,6}},"Flexible"]

GraphData[{"Cage",{10,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{10,6}},"LCF"]

GraphData[{"Cage",{10,6}},"HamiltonianCycleCount"]

GraphData[{"Cage",{10,6}},"LCFSignature"]

GraphData[{"Cage",{10,6}},"LCFNotations"]

GraphData[{"Cage",{10,6}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{10,6}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{10,6}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{10,6}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{10,6}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{10,6}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{10,6}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{10,6}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{10,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{10,6}}],Debug->True]//Timing

GraphData[{"Cage",{10,6}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{10,6}},"VertexList"],GraphData[{"Cage",{10,6}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{10,6}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{10,6}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{10,6}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{10,6}},"Matchstick"]

GraphData[{"Cage",{10,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{10,6}},"Edges"]]

3D All

GraphData[{"Cage",{10,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{10,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{10,6}},"Polyhedral"]

GraphData[{"Cage",{10,6}},"Graph",{"3D","Polyhedron"}]

{"Cage", {11, 5}}

Names

GraphData[{"Cage",{11,5}},"StandardName"]

GraphData[{"Cage",{11,5}},"StandardNames"]

Primary

GraphData[{"Cage",{11,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{11,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{11,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{11,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{11,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{11,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{11,5}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{11,5}},"Configuration"]

GraphData[{"Cage",{11,5}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{11,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{11,5}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{11,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{11,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{11,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{11,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{11,5}},"Planar"]

GraphData[{"Cage",{11,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{11,5}},{"RCN","CN"}]

GraphData[{"Cage",{11,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{11,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{11,5}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{11,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{11,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{11,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{11,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{11,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{11,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{11,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{11,5}},"Circulant"]

GraphData[{"Cage",{11,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{11,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{11,5}},"Line"]

LineGraphQ[GraphData[{"Cage",{11,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{11,5}}&]

RootGraph[GraphData[{"Cage",{11,5}}]]

Halin

GraphData[{"Cage",{11,5}},"Halin"]

GraphData[{"Cage",{11,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{11,5}},"Rigid"]

GraphData[{"Cage",{11,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{11,5}},"Flexible"]

GraphData[{"Cage",{11,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{11,5}},"LCF"]

GraphData[{"Cage",{11,5}},"HamiltonianCycleCount"]

GraphData[{"Cage",{11,5}},"LCFSignature"]

GraphData[{"Cage",{11,5}},"LCFNotations"]

GraphData[{"Cage",{11,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{11,5}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{11,5}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{11,5}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{11,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{11,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{11,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{11,5}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{11,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{11,5}}],Debug->True]//Timing

GraphData[{"Cage",{11,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{11,5}},"VertexList"],GraphData[{"Cage",{11,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{11,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{11,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{11,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{11,5}},"Matchstick"]

GraphData[{"Cage",{11,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{11,5}},"Edges"]]

3D All

GraphData[{"Cage",{11,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{11,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{11,5}},"Polyhedral"]

GraphData[{"Cage",{11,5}},"Graph",{"3D","Polyhedron"}]

{"Cage", {11, 6}}

Names

GraphData[{"Cage",{11,6}},"StandardName"]

GraphData[{"Cage",{11,6}},"StandardNames"]

Primary

GraphData[{"Cage",{11,6}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{11,6}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{11,6}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{11,6}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{11,6}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{11,6}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{11,6}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{11,6}},"Configuration"]

GraphData[{"Cage",{11,6}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{11,6}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{11,6}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{11,6}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{11,6}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{11,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{11,6}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{11,6}},"Planar"]

GraphData[{"Cage",{11,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{11,6}},{"RCN","CN"}]

GraphData[{"Cage",{11,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{11,6}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{11,6}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{11,6}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{11,6}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{11,6}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{11,6}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{11,6}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{11,6}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{11,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{11,6}},"Circulant"]

GraphData[{"Cage",{11,6}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{11,6}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{11,6}},"Line"]

LineGraphQ[GraphData[{"Cage",{11,6}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{11,6}}&]

RootGraph[GraphData[{"Cage",{11,6}}]]

Halin

GraphData[{"Cage",{11,6}},"Halin"]

GraphData[{"Cage",{11,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{11,6}},"Rigid"]

GraphData[{"Cage",{11,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{11,6}},"Flexible"]

GraphData[{"Cage",{11,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{11,6}},"LCF"]

GraphData[{"Cage",{11,6}},"HamiltonianCycleCount"]

GraphData[{"Cage",{11,6}},"LCFSignature"]

GraphData[{"Cage",{11,6}},"LCFNotations"]

GraphData[{"Cage",{11,6}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{11,6}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{11,6}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{11,6}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{11,6}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{11,6}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{11,6}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{11,6}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{11,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{11,6}}],Debug->True]//Timing

GraphData[{"Cage",{11,6}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{11,6}},"VertexList"],GraphData[{"Cage",{11,6}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{11,6}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{11,6}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{11,6}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{11,6}},"Matchstick"]

GraphData[{"Cage",{11,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{11,6}},"Edges"]]

3D All

GraphData[{"Cage",{11,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{11,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{11,6}},"Polyhedral"]

GraphData[{"Cage",{11,6}},"Graph",{"3D","Polyhedron"}]

{"Cage", {12, 5}}

Names

GraphData[{"Cage",{12,5}},"StandardName"]

GraphData[{"Cage",{12,5}},"StandardNames"]

Primary

GraphData[{"Cage",{12,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{12,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{12,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{12,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{12,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{12,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{12,5}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{12,5}},"Configuration"]

GraphData[{"Cage",{12,5}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{12,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{12,5}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{12,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{12,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{12,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{12,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{12,5}},"Planar"]

GraphData[{"Cage",{12,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{12,5}},{"RCN","CN"}]

GraphData[{"Cage",{12,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{12,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{12,5}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{12,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{12,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{12,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{12,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{12,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{12,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{12,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{12,5}},"Circulant"]

GraphData[{"Cage",{12,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{12,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{12,5}},"Line"]

LineGraphQ[GraphData[{"Cage",{12,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{12,5}}&]

RootGraph[GraphData[{"Cage",{12,5}}]]

Halin

GraphData[{"Cage",{12,5}},"Halin"]

GraphData[{"Cage",{12,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{12,5}},"Rigid"]

GraphData[{"Cage",{12,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{12,5}},"Flexible"]

GraphData[{"Cage",{12,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{12,5}},"LCF"]

GraphData[{"Cage",{12,5}},"HamiltonianCycleCount"]

GraphData[{"Cage",{12,5}},"LCFSignature"]

GraphData[{"Cage",{12,5}},"LCFNotations"]

GraphData[{"Cage",{12,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{12,5}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{12,5}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{12,5}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{12,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{12,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{12,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{12,5}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{12,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{12,5}}],Debug->True]//Timing

GraphData[{"Cage",{12,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{12,5}},"VertexList"],GraphData[{"Cage",{12,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{12,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{12,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{12,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{12,5}},"Matchstick"]

GraphData[{"Cage",{12,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{12,5}},"Edges"]]

3D All

GraphData[{"Cage",{12,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{12,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{12,5}},"Polyhedral"]

GraphData[{"Cage",{12,5}},"Graph",{"3D","Polyhedron"}]

{"Cage", {13, 5}}

Names

GraphData[{"Cage",{13,5}},"StandardName"]

GraphData[{"Cage",{13,5}},"StandardNames"]

Primary

GraphData[{"Cage",{13,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{13,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{13,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{13,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{13,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{13,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{13,5}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{13,5}},"Configuration"]

GraphData[{"Cage",{13,5}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{13,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{13,5}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{13,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{13,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{13,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{13,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{13,5}},"Planar"]

GraphData[{"Cage",{13,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{13,5}},{"RCN","CN"}]

GraphData[{"Cage",{13,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{13,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{13,5}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{13,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{13,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{13,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{13,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{13,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{13,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{13,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{13,5}},"Circulant"]

GraphData[{"Cage",{13,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{13,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{13,5}},"Line"]

LineGraphQ[GraphData[{"Cage",{13,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{13,5}}&]

RootGraph[GraphData[{"Cage",{13,5}}]]

Halin

GraphData[{"Cage",{13,5}},"Halin"]

GraphData[{"Cage",{13,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{13,5}},"Rigid"]

GraphData[{"Cage",{13,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{13,5}},"Flexible"]

GraphData[{"Cage",{13,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{13,5}},"LCF"]

GraphData[{"Cage",{13,5}},"HamiltonianCycleCount"]

GraphData[{"Cage",{13,5}},"LCFSignature"]

GraphData[{"Cage",{13,5}},"LCFNotations"]

GraphData[{"Cage",{13,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{13,5}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{13,5}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{13,5}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{13,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{13,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{13,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{13,5}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{13,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{13,5}}],Debug->True]//Timing

GraphData[{"Cage",{13,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{13,5}},"VertexList"],GraphData[{"Cage",{13,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{13,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{13,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{13,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{13,5}},"Matchstick"]

GraphData[{"Cage",{13,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{13,5}},"Edges"]]

3D All

GraphData[{"Cage",{13,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{13,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{13,5}},"Polyhedral"]

GraphData[{"Cage",{13,5}},"Graph",{"3D","Polyhedron"}]

{"Cage", {14, 5}}

Names

GraphData[{"Cage",{14,5}},"StandardName"]

GraphData[{"Cage",{14,5}},"StandardNames"]

Primary

GraphData[{"Cage",{14,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{14,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{14,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{14,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{14,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{14,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{14,5}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{14,5}},"Configuration"]

GraphData[{"Cage",{14,5}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{14,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{14,5}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{14,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{14,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{14,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{14,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{14,5}},"Planar"]

GraphData[{"Cage",{14,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{14,5}},{"RCN","CN"}]

GraphData[{"Cage",{14,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{14,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{14,5}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{14,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{14,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{14,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{14,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{14,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{14,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{14,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{14,5}},"Circulant"]

GraphData[{"Cage",{14,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{14,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{14,5}},"Line"]

LineGraphQ[GraphData[{"Cage",{14,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{14,5}}&]

RootGraph[GraphData[{"Cage",{14,5}}]]

Halin

GraphData[{"Cage",{14,5}},"Halin"]

GraphData[{"Cage",{14,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{14,5}},"Rigid"]

GraphData[{"Cage",{14,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{14,5}},"Flexible"]

GraphData[{"Cage",{14,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{14,5}},"LCF"]

GraphData[{"Cage",{14,5}},"HamiltonianCycleCount"]

GraphData[{"Cage",{14,5}},"LCFSignature"]

GraphData[{"Cage",{14,5}},"LCFNotations"]

GraphData[{"Cage",{14,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{14,5}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{14,5}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{14,5}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{14,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{14,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{14,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{14,5}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{14,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{14,5}}],Debug->True]//Timing

GraphData[{"Cage",{14,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{14,5}},"VertexList"],GraphData[{"Cage",{14,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{14,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{14,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{14,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{14,5}},"Matchstick"]

GraphData[{"Cage",{14,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{14,5}},"Edges"]]

3D All

GraphData[{"Cage",{14,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{14,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{14,5}},"Polyhedral"]

GraphData[{"Cage",{14,5}},"Graph",{"3D","Polyhedron"}]

{"Cage", {15 ,5}}

Names

GraphData[{"Cage",{15,5}},"StandardName"]

GraphData[{"Cage",{15,5}},"StandardNames"]

Primary

GraphData[{"Cage",{15,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{15,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{15,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{15,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{15,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{15,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{15,5}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{15,5}},"Configuration"]

GraphData[{"Cage",{15,5}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{15,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{15,5}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{15,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{15,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{15,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{15,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{15,5}},"Planar"]

GraphData[{"Cage",{15,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{15,5}},{"RCN","CN"}]

GraphData[{"Cage",{15,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{15,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{15,5}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{15,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{15,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{15,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{15,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{15,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{15,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{15,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{15,5}},"Circulant"]

GraphData[{"Cage",{15,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{15,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{15,5}},"Line"]

LineGraphQ[GraphData[{"Cage",{15,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{15,5}}&]

RootGraph[GraphData[{"Cage",{15,5}}]]

Halin

GraphData[{"Cage",{15,5}},"Halin"]

GraphData[{"Cage",{15,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{15,5}},"Rigid"]

GraphData[{"Cage",{15,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{15,5}},"Flexible"]

GraphData[{"Cage",{15,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{15,5}},"LCF"]

GraphData[{"Cage",{15,5}},"HamiltonianCycleCount"]

GraphData[{"Cage",{15,5}},"LCFSignature"]

GraphData[{"Cage",{15,5}},"LCFNotations"]

GraphData[{"Cage",{15,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{15,5}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{15,5}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{15,5}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{15,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{15,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{15,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{15,5}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{15,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{15,5}}],Debug->True]//Timing

GraphData[{"Cage",{15,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{15,5}},"VertexList"],GraphData[{"Cage",{15,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{15,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{15,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{15,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{15,5}},"Matchstick"]

GraphData[{"Cage",{15,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{15,5}},"Edges"]]

3D All

GraphData[{"Cage",{15,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{15,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{15,5}},"Polyhedral"]

GraphData[{"Cage",{15,5}},"Graph",{"3D","Polyhedron"}]

{"Cage", {16, 5}}

Names

GraphData[{"Cage",{16,5}},"StandardName"]

GraphData[{"Cage",{16,5}},"StandardNames"]

Primary

GraphData[{"Cage",{16,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{16,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{16,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{16,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{16,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{16,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{16,5}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{16,5}},"Configuration"]

GraphData[{"Cage",{16,5}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{16,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{16,5}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{16,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{16,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{16,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{16,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{16,5}},"Planar"]

GraphData[{"Cage",{16,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{16,5}},{"RCN","CN"}]

GraphData[{"Cage",{16,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{16,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{16,5}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{16,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{16,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{16,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{16,5}}],TimeConstraint->86400])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{16,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{16,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{16,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{16,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{16,5}},"Circulant"]

GraphData[{"Cage",{16,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{16,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{16,5}},"Line"]

LineGraphQ[GraphData[{"Cage",{16,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{16,5}}&]

RootGraph[GraphData[{"Cage",{16,5}}]]

Halin

GraphData[{"Cage",{16,5}},"Halin"]

GraphData[{"Cage",{16,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{16,5}},"Rigid"]

GraphData[{"Cage",{16,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{16,5}},"Flexible"]

GraphData[{"Cage",{16,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{16,5}},"LCF"]

GraphData[{"Cage",{16,5}},"HamiltonianCycleCount"]

GraphData[{"Cage",{16,5}},"LCFSignature"]

GraphData[{"Cage",{16,5}},"LCFNotations"]

GraphData[{"Cage",{16,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{16,5}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{16,5}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{16,5}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{16,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{16,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{16,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{16,5}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{16,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{16,5}}],Debug->True]//Timing

GraphData[{"Cage",{16,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{16,5}},"VertexList"],GraphData[{"Cage",{16,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{16,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{16,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{16,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{16,5}},"Matchstick"]

GraphData[{"Cage",{16,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{16,5}},"Edges"]]

3D All

GraphData[{"Cage",{16,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{16,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{16,5}},"Polyhedral"]

GraphData[{"Cage",{16,5}},"Graph",{"3D","Polyhedron"}]

{"Cage", {17, 5}}

Names

GraphData[{"Cage",{17,5}},"StandardName"]

GraphData[{"Cage",{17,5}},"StandardNames"]

Primary

GraphData[{"Cage",{17,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cage",{17,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Cage",{17,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Cage",{17,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cage",{17,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cage",{17,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cage",{17,5}},"Graph","Degenerate"]

Configuration

GraphData[{"Cage",{17,5}},"Configuration"]

GraphData[{"Cage",{17,5}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Cage",{17,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Cage",{17,5}},"Polyhedron"]

GeneralizedPetersen

GraphData[{"Cage",{17,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Cage",{17,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Cage",{17,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cage",{17,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cage",{17,5}},"Planar"]

GraphData[{"Cage",{17,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cage",{17,5}},{"RCN","CN"}]

GraphData[{"Cage",{17,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Cage",{17,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{17,5}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{17,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{17,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cage",{17,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"Cage",{17,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Cage",{17,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"Cage",{17,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"Cage",{17,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cage",{17,5}},"Circulant"]

GraphData[{"Cage",{17,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Cage",{17,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"Cage",{17,5}},"Line"]

LineGraphQ[GraphData[{"Cage",{17,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cage",{17,5}}&]

RootGraph[GraphData[{"Cage",{17,5}}]]

Halin

GraphData[{"Cage",{17,5}},"Halin"]

GraphData[{"Cage",{17,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cage",{17,5}},"Rigid"]

GraphData[{"Cage",{17,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cage",{17,5}},"Flexible"]

GraphData[{"Cage",{17,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cage",{17,5}},"LCF"]

GraphData[{"Cage",{17,5}},"HamiltonianCycleCount"]

GraphData[{"Cage",{17,5}},"LCFSignature"]

GraphData[{"Cage",{17,5}},"LCFNotations"]

GraphData[{"Cage",{17,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData[{"Cage",{17,5}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cage",{17,5}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Cage",{17,5}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Cage",{17,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cage",{17,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cage",{17,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Cage",{17,5}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cage",{17,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cage",{17,5}}],Debug->True]//Timing

GraphData[{"Cage",{17,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cage",{17,5}},"VertexList"],GraphData[{"Cage",{17,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"Cage",{17,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Cage",{17,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Cage",{17,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Cage",{17,5}},"Matchstick"]

GraphData[{"Cage",{17,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cage",{17,5}},"Edges"]]

3D All

GraphData[{"Cage",{17,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cage",{17,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cage",{17,5}},"Polyhedral"]

GraphData[{"Cage",{17,5}},"Graph",{"3D","Polyhedron"}]

Moore bound

https://web.archive.org/web/20090125032457/http://people.csse.uwa.edu.au/gordon/cages/allcages.html

Odd:

FullSimplify[1+k Sum[(((k-1))^i),{i,0,((g-3)/2)}]]

Even:

FullSimplify[1+k Sum[(((k-1))^i),{i,0,(g/2)-2}]+(((k-1))^(g/2-1))]

MooreBound[k_,g_]:=Piecewise[{{(((((k-1))^((g-1)/2)) k-2)/(k-2)),Mod[g,2]==1},{((2 ((((k-1))^(g/2))-1))/(k-2)),Mod[g,2]==0}}]

TextGrid[Table[MooreBound[k,g],{k,3,15},{g,5,15}],Dividers->All,Alignment->Decimal]

Import

Brouwer

ReadBrouwerCage[u_String]:=Module[{s=Import["http://www.win.tue.nl/~aeb/graphs/cages/"<>u,"String"]},
FromAdjacencyLists[Rest[ImportString[StringReplace[s,{";"->"","."->"",","->" "}],"Table"]]+1]
]

s=Import["http://www.win.tue.nl/~aeb/graphs/cages/cage-k4.g12-00.dr","String"];

ReadBrouwerCage["cage-k4.g12-00.dr"]

ReadBrouwerCage["cage-k5.g12-00.dr"]

ReadBrouwerCage["cage-k6.g12-00.dr"]

Royle

All:

https://web.archive.org/web/20090125032457/http://people.csse.uwa.edu.au/gordon/cages/allcages.html

Cubic:

https://web.archive.org/web/20081030015308/http://people.csse.uwa.edu.au/gordon/cages/index.html

SetDirectory[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages"}]]

files=FileNames["*.s6"]

data=Monitor[Flatten[Function[file,{VertexDegree[#][[1]],GraphGirth[#],v=VertexCount[#],file,RecognizeGraph@#}&/@Import[f=file,{"Sparse6","GraphList"}]]/@files,1],f];//AbsoluteTiming

Files in this directory that are in GraphData but not marked as cages:

Select[DeleteCases[data[[All,-1]],{}|$Failed],!GraphData[#,"Cage"]&]

known=Join[
{3,#}&/@Range[5,12],
{4,#}&/@{5,6,8},
{5,#}&/@{5,6,8,12},
{6,#}&/@{5,6,8,12},
{7,#}&/@{5,6},
{8,#}&/@{6,8},
{9,#}&/@{6,8,12},
{10,#}&/@{6,8,12},
{12,#}&/@{6,8,12},
{14,#}&/@{6,8,12}
];

TextGrid[
Sort[data]/.row:{k_,g_,n_,s_String?(StringMatchQ["*.s6"]),gn_}:>{k,g,n,If[!MemberQ[known,{k,g}]&&n>6,Style[s,Orange],s],gn},
Dividers->All,Alignment->{{Decimal,Decimal,Decimal,{Left}}}]

GraphData

GraphClassString

GraphClassString[GraphData["Cage"]]

GraphDataString

Initialize

<<MathWorld`Graphs`

file=OpenWrite["~/cages.m"]

{"Cage", {3, 13}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","cagesk3g13.s6"}]],
"Embeddings"->{},
"Name"->"(3,13)\[Hyphen]cage",
"StandardName"->{"Cage",{3,13}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{3,13}},
"Skip"->{"MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover"},
TimeConstraint->10
]]

{"Cage", {3, 14}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","cagesk3g14.s6"}]],
"Embeddings"->{},
"Name"->"(3,14)\[Hyphen]cage",
"StandardName"->{"Cage",{3,14}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{3,14}},
"Skip"->{"MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover"},
Debug->True,
TimeConstraint->10
]]

{"Cage", {4, 9}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k04g09v275.s6"}]],
"Embeddings"->{},
"Name"->"(4,9)\[Hyphen]cage",
"StandardName"->{"Cage",{4,9}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{4,9}},
"Skip"->{"MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover"},
Debug->True,
TimeConstraint->10
]]

{"Cage", {4, 10}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k04g10v384.s6"}]],
"Embeddings"->{},
"Name"->"(4,10)\[Hyphen]cage",
"StandardName"->{"Cage",{4,10}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{4,10}},
"Skip"->{"MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover"},
Debug->True,
TimeConstraint->10
]]

{"Cage", {4, 12}}

WriteString[file,GraphDataString[ReadBrouwerCage["cage-k4.g12-00.dr"],
"Name"->"(4,12)-cage",
"StandardName"->{"Cage",{4,12}},
"NotationRules"->{"Cage"->{4,12}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"Vertices"->None,
"Skip"->{"EdgeConnectivity","VertexConnectivity"},
Debug->True,
TimeConstraint->10
]]//Timing

{"Cage", {5, 7}, 1}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k05g07v152.s6"}]][[1]],
"Embeddings"->{},
"Name"->"(5,7)\[Hyphen]cage 1",
"StandardName"->{"Cage",{5,7},1},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{{5,7},1}},
"Skip"->{"MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover"},
Debug->True,
TimeConstraint->10
]]

{"Cage", {5, 7}, 2}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k05g07v152.s6"}]][[2]],
"Embeddings"->{},
"Name"->"(5,7)\[Hyphen]cage 2",
"StandardName"->{"Cage",{5,7},2},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{{5,7},2}},
"Skip"->{"MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming

{"Cage", {5, 12}}

WriteString[file,GraphDataString[ReadBrouwerCage["cage-k5.g12-00.dr"],
"Name"->"(5,12)-cage",
"StandardName"->{"Cage",{5,12}},
"NotationRules"->{"Cage"->{5,12}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"Vertices"->None,
"Skip"->{"CharacteristicPolynomial","EdgeConnectivity","VertexConnectivity"},
Debug->True,
TimeConstraint->10
]]//Timing

{"Cage", {6, 7}}

Length[cages[6,7]=Import["http://people.csse.uwa.edu.au/gordon/cages/uk06g07v294.s6","EdgeRules"]]

MapIndexed[Print[GraphDataString[FromUnorderedPairs[List@@@#1],
"Name"->"(6,7)-cage "<>ToString[#2[[1]]],
"StandardName"->{"Cage",{6,7},#2[[1]]},
"Information"->"CageGraph",
"Classes"->{"Cage"},
Debug->True,
TimeConstraint->60
]]&,cages[6,7]]

{"Cage", {6, 12}} [too large; 7812 vertices; cases errors when building MX file]

WriteString[file,GraphDataString[ReadBrouwerCage["cage-k6.g12-00.dr"],
"Name"->"(6,12)-cage",
"StandardName"->{"Cage",{6,12}},
"NotationRules"->{"Cage"->{6,12}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"Vertices"->None,
"Skip"->{"CharacteristicPolynomial","Bridges","ConnectedComponents","EdgeConnectivity","HamiltonianCycles","HamiltonianPaths","Hypohamiltonian","Hypotraceable","VertexConnectivity"},
Debug->True,
TimeConstraint->10
]]//Timing

{"Cage", {8, 5}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k08g05v80.s6"}]],
"Embeddings"->{},
"Name"->"(8,5)\[Hyphen]cage",
"StandardName"->{"Cage",{8,5}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{8,5}},
"Skip"->{"MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming

{"Cage", {10, 5}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k10g05v126.s6"}]],
"Embeddings"->{},
"Name"->"(10,5)\[Hyphen]cage",
"StandardName"->{"Cage",{10,5}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{10,5}},
"Skip"->{"ConnectedInducedSubgraphPolynomial","MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover","VertexCut"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming

{"Cage", {11, 5}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k11g05v160.s6"}]],
"Embeddings"->{},
"Name"->"(11,5)\[Hyphen]cage",
"StandardName"->{"Cage",{11,5}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{11,5}},
"Skip"->{"ConnectedInducedSubgraphPolynomial","MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover","VertexCut"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming

{"Cage", {11, 6}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k11g06v240.s6"}]],
"Embeddings"->{},
"Name"->"(11,6)\[Hyphen]cage",
"StandardName"->{"Cage",{11,6}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{11,6}},
"Skip"->{"ConnectedInducedSubgraphPolynomial","MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover","VertexCut"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming

{"Cage", {12, 5}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k12g05v203.s6"}]],
"Embeddings"->{},
"Name"->"(12,5)\[Hyphen]cage",
"StandardName"->{"Cage",{12,5}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{12,5}},
"Skip"->{"ConnectedInducedSubgraphPolynomial","MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover","VertexCut"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming

{"Cage", {13, 5}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k13g05v240.s6"}]],
"Embeddings"->{},
"Name"->"(13,5)\[Hyphen]cage",
"StandardName"->{"Cage",{13,5}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{13,5}},
"Skip"->{"ConnectedInducedSubgraphPolynomial","MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover","VertexCut"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming

{"Cage", {14, 5}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k14g05v312.s6"}]],
"Embeddings"->{},
"Name"->"(14,5)\[Hyphen]cage",
"StandardName"->{"Cage",{14,5}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{14,5}},
"Skip"->{"ConnectedInducedSubgraphPolynomial","MatchingGeneratingPolynomial","MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover","VertexCut"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming

{"Cage", {15, 5}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k15g05v406.s6"}]],
"Embeddings"->{},
"Name"->"(15,5)\[Hyphen]cage",
"StandardName"->{"Cage",{15,5}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{15,5}},
"Skip"->{"ConnectedInducedSubgraphPolynomial","MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover","VertexCut"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming

{"Cage", {16, 5}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k16g05v480.s6"}]],
"Embeddings"->{},
"Name"->"(16,5)\[Hyphen]cage",
"StandardName"->{"Cage",{16,5}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{16,5}},
"Skip"->{"ConnectedInducedSubgraphPolynomial","MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover","VertexCut"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming

{"Cage", {17, 5}}

(not known to be minimal)

WriteString[file,GraphDataString[
CanonicalGraph@Import[FileNameJoin[{$GraphDataDirectory,"Collections","Royle","Cages","k17g05v576.s6"}]],
"Embeddings"->{},
"Name"->"(17,5)\[Hyphen]cage",
"StandardName"->{"Cage",{17,5}},
"Information"->"CageGraph",
"Classes"->{"Cage"},
"NotationRules"->{"Cage"->{17,5}},
"Skip"->{"ConnectedInducedSubgraphPolynomial","MinimumDominatingSet","MinimumTotalDominatingSet","MinimumVertexCover","VertexCut"},
Debug->True,
TimeConstraint->10
]]//AbsoluteTiming