KC Graph

Author

Eric W. Weisstein
January 7, 2025

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

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

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

Source

Knuth, D.E.  The Art of Computer Programing, Vol. 4, Pre-Fascicle 7A, §7.2.2.3, p. 22, 2024.

Properties

EdgeCount

DeleteCases[{#,{n,r}=GraphData[#,"NotationRules","KC"],GraphData[#,"EdgeCount"],r(n+1)n/2}&/@GraphData["KC"],{_,_,x_,x_}]

MinimumVertexDegree == MaximumVertexDegree == n+1

DeleteCases[{#,GraphData[#,"NotationRules","KC"][[1]]+1,GraphData[#,"MinimumVertexDegree"],GraphData[#,"MaximumVertexDegree"]}&/@GraphData["KC"],{_,x_,x_,x_}]

Regular

Complement@@GraphData/@{"KC","Regular"}

VertexCount

DeleteCases[{#,{n,r}=GraphData[#,"NotationRules","KC"],GraphData[#,"VertexCount"],r n}&/@GraphData["KC"],{_,_,x_,x_}]

Classes that are Class

GraphClassesThatAre["KC"]

Intersection@@(GraphData[#,"Classes"]&/@GraphData["KC"])

Circulant

c1=GraphData[{"KC","Circulant"}]//Sort

c2=DeleteCases[Quiet@GraphData[{"KC",#},"#"]&/@Select[Flatten[Table[{n,r},{n,30},{r,3,30}],1],CoprimeQ@@#&],_GraphData]//Sort

Complement[c1,c2]

circulants=Complement[c2,c1]

Table

TextGrid[Table[RecognizeGraph@KCGraph[n,r],{n,10},{r,3,8}],Dividers->All]

Gracefulness

Knuth, D.E.  The Art of Computer Programing, Vol. 4, Pre-Fascicle 7A, §7.2.2.3, p. 22, 2024.

graceful=RecognizeGraph/@Table[KCGraph[3,r],{r,4,10,2}]

GraphData[#,"Graceful"]&/@graceful

GraphData[#,"GracefulLabelingCount"]&/@graceful

ungraceful=DeleteCases[RecognizeGraph/@Table[KCGraph[3,r],{r,3,20,2}],{}]

GraphData[#,"Graceful"]&/@ungraceful

rules=Rule[#,{}]&/@ungraceful

Embeddings

<<MathWorld`Graphs`

{"KC", {3, 3}} == {"GeneralizedQuadrangle", {2, 1}}

Names

GraphData[{"KC",{3,3}},"StandardName"]

GraphData[{"KC",{3,3}},"StandardNames"]

{"KC", {3, 4}} == {"TorusGrid", {3, 4}}

Names

GraphData[{"KC",{3,4}},"StandardName"]

GraphData[{"KC",{3,4}},"StandardNames"]

{"KC", {3, 5}} == {"TorusGrid", {3, 5}}

Names

GraphData[{"KC",{3,5}},"StandardName"]

GraphData[{"KC",{3,5}},"StandardNames"]

{"KC", {3, 6}} == {"TorusGrid", {3, 6}}

Names

GraphData[{"KC",{3,6}},"StandardName"]

GraphData[{"KC",{3,6}},"StandardNames"]

{"KC", {3, 7}} == {"TorusGrid", {3, 7}}

Names

GraphData[{"KC",{3,7}},"StandardName"]

GraphData[{"KC",{3,7}},"StandardNames"]

{"KC", {3, 8}} == {"TorusGrid", {3, 8}}

Names

GraphData[{"KC",{3,8}},"StandardName"]

GraphData[{"KC",{3,8}},"StandardNames"]

{"KC", {3, 9}} == {"TorusGrid", {3, 9}}

Names

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

GraphData[{"KC",{3,9}},"StandardNames"]

{"KC", {3, 10}} == {"TorusGrid", {3, 10}}

Names

GraphData[{"KC",{3,10}},"StandardName"]

GraphData[{"KC",{3,10}},"StandardNames"]

{"KC", {4, 3}} == {"Rook", {3, 4}}}

Names

GraphData[{"KC",{4,3}},"StandardName"]

GraphData[{"KC",{4,3}},"StandardNames"]

{"KC", {4, 4}}

Names

GraphData[{"KC",{4,4}},"StandardName"]

GraphData[{"KC",{4,4}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KC",{4,4}}]]

Default embedding

g=Graph[GraphData[{"KC",{4,4}},"VertexList"],GraphData[{"KC",{4,4}},"Edges"]]

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

RecognizeGraph@g

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData[{"KC",{4,4}},"Graph","Degenerate"]//Column

GeneralizedPetersen

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

IGraph

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

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KC",{4,4}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

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

Circular construction

GraphData[{"KC",{4,4}},"Hamiltonian"]

GraphData[{"KC",{4,4}},"LCF"]

GraphData[{"KC",{4,4}},"HamiltonianCycleCount"]

Planar

GraphData[{"KC",{4,4}},"Planar"]

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

MinimalCrossing

GraphData[{"KC",{4,4}},{"RCN","CN"}]

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

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,4}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KC",{4,4}},"V"]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,4}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

GraphPlot@RotateGraph[,-Pi/4]

v={#/9,#2/7}&@@@{{0,0},{9,0},{9,7},{0,7},{1,1},{8,1},{3,2},{6,2},{3,3},{6,3},{4,4},{5,4},{2,5},{7,5},{1,6},{8,6}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,1,7,8,2,16,6,3,12,11,4,5,15,1,5,9,11,7,13,15,4],e[5,6,2],e[8,10,14,16,3],e[7,9,10,12,14,13,11],{8,12},{15,16},{9,13},{8,14},{6,10}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

(gs=Table[MinimalCrossingGraph[GraphData[{"KC",{4,4}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,4}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

MinimalLocalCrossing

GraphData[{"KC",{4,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,4}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KC",{4,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,4}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,4}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,4}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,4}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,4}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"KC",{4,4}},"Circulant"]

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

Circulant construction

GraphData[{"KC",{4,4}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KC",{4,4}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KC",{4,4}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData[{"KC",{4,4}},"Line"]

LineGraphQ[GraphData[{"KC",{4,4}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"KC",{4,4}}]]

RecognizeGraph[%]

Halin

GraphData[{"KC",{4,4}},"Halin"]

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

Rigid

GraphData[{"KC",{4,4}},"Rigid"]

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

Flexible

GraphData[{"KC",{4,4}},"Flexible"]

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

LCF

GraphData[{"KC",{4,4}},"LCF"]

GraphData[{"KC",{4,4}},"HamiltonianCycleCount"]

GraphData[{"KC",{4,4}},"LCFSignature"]

GraphData[{"KC",{4,4}},"LCFNotations"]

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

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

LCF compute all

Divisors[GraphData[{"KC",{4,4}},"V"]]

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

Tally[(lcf=LCF[GraphData[{"KC",{4,4}}],All])[[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

UnitDistance

GraphData[{"KC",{4,4}},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

LabelGraph@

gs={,,,RotateGraph[,{16,2}]}

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"KC",{4,4}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"KC",{4,4}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"KC",{4,4}},"Polyhedral"]

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

{"KC", {4, 5}}

Names

GraphData[{"KC",{4,5}},"StandardName"]

GraphData[{"KC",{4,5}},"StandardNames"]

Primary

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

All

GraphData[{"KC",{4,5}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KC",{4,5}}]]

Default embedding

g=Graph[GraphData[{"KC",{4,5}},"VertexList"],GraphData[{"KC",{4,5}},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph@g

Degenerate

GraphData[{"KC",{4,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"KC",{4,5}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"KC",{4,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KC",{4,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"KC",{4,5}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KC",{4,5}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

GraphData[{"KC",{4,5}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"KC",{4,5}},"Hamiltonian"]

GraphData[{"KC",{4,5}},"LCF"]

GraphData[{"KC",{4,5}},"HamiltonianCycleCount"]

Planar

GraphData[{"KC",{4,5}},"Planar"]

GraphData[{"KC",{4,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"KC",{4,5}},{"RCN","CN"}]

GraphData[{"KC",{4,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

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

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

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

(cn=CrossingNumber[GraphData[{"KC",{4,5}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KC",{4,5}},"V"]&]

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"KC",{4,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}],Max[OuterFace[#]]<=GraphData[{"KC",{4,5}},"V"]&]])//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KC",{4,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"KC",{4,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,5}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KC",{4,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,5}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,5}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"KC",{4,5}},"Circulant"]

GraphData[{"KC",{4,5}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"KC",{4,5}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KC",{4,5}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KC",{4,5}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KC",{4,5}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"KC",{4,5}},"Line"]

LineGraphQ[GraphData[{"KC",{4,5}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"KC",{4,5}}]]

RecognizeGraph[%]

Halin

GraphData[{"KC",{4,5}},"Halin"]

GraphData[{"KC",{4,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KC",{4,5}},"Rigid"]

GraphData[{"KC",{4,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KC",{4,5}},"Flexible"]

GraphData[{"KC",{4,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KC",{4,5}},"LCF"]

GraphData[{"KC",{4,5}},"HamiltonianCycleCount"]

GraphData[{"KC",{4,5}},"LCFSignature"]

GraphData[{"KC",{4,5}},"LCFNotations"]

GraphData[{"KC",{4,5}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Divisors[GraphData[{"KC",{4,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"KC",{4,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"KC",{4,5}}],All])[[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={
{{"KC",{4,5}},Missing["External",LCFNotation/@gs]}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

UnitDistance

GraphData[{"KC",{4,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KC",{4,5}}],Debug->True]//Timing

GraphData[{"KC",{4,5}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"KC",{4,5}},"Matchstick"]

GraphData[{"KC",{4,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KC",{4,5}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"KC",{4,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"KC",{4,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"KC",{4,5}},"Polyhedral"]

GraphData[{"KC",{4,5}},"Graph",{"3D","Polyhedron"}]

{"KC", {4, 6}}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KC",{4,6}}]]

Default embedding

Graph[GraphData[{"KC",{4,6}},"VertexList"],GraphData[{"KC",{4,6}},"Edges"]]

gs={,};

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

RecognizeGraph@g

Degenerate

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

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

GeneralizedPetersen

GraphData[{"KC",{4,6}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KC",{4,6}},"Graph","IGraph"]//StyleGraphs

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KC",{4,6}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]//Quiet

Circular

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

Circular construction

GraphData[{"KC",{4,6}},"Hamiltonian"]

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

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

Planar

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

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

MinimalCrossing

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

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

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KC",{4,6}},"V"]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KC",{4,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

GraphPlot@

RotateGraph[,Pi/6]

v=Join[CirclePoints[6],CirclePoints[x,6],CirclePoints[{1/2,Pi/12},6],CirclePoints[{1/2,-Pi/12},6]];

Solve[SquaredEuclideanDistance@@v[[{10,15}]]==SquaredEuclideanDistance@@v[[{15,21}]],x,PositiveReals]//FullSimplify

v=Join[CirclePoints[6],CirclePoints[((Sqrt[2-(Sqrt[3])])/2),6],CirclePoints[{1/2,Pi/12},6],CirclePoints[{1/2,-Pi/12},6]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,6,1,7,18,19,13,20,14,21,15,22,16,23,17,24,18],e[24,7,8,9,10,11,12,7],e[2,8,13,24,1,18],e[8,19,2,13],e[18,23,12,6,23],e[17,22,11,5,22],e[5,16,21,10,15,20,9,3,14,19],{11,16},e[15,4,21],{3,20},{14,9},e[6,17,12],{4,10}},VertexCoordinates->v,VertexLabels->Automatic]

v=Join[CirclePoints[6],CirclePoints[(1/(Sqrt[2])),6],CirclePoints[{1/2,Pi/12},6],CirclePoints[{1/2,-Pi/12},6]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,6,1,7,18,19,13,20,14,21,15,22,16,23,17,24,18],e[24,7,8,9,10,11,12,7],e[2,8,13,24,1,18],e[8,19,2,13],e[18,23,12,6,23],e[17,22,11,5,22],e[5,16,21,10,15,20,9,3,14,19],{11,16},e[15,4,21],{3,20},{14,9},e[6,17,12],{4,10}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

gs=UnlabelGraph/@{,}

MinimalLocalCrossing

GraphData[{"KC",{4,6}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,6}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KC",{4,6}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,6}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,6}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

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

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

Circulant construction

GraphData[{"KC",{4,6}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KC",{4,6}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KC",{4,6}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KC",{4,6}},"ComplementGraph","Name"]

Line graph

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

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

RootGraph

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

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

RecognizeGraph[%]

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

LCF compute all

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

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

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

l={
{{"KC",{4,6}},{0,{{12,1},{6,4},{4,2},{3,18},{2,260},{1,8768}}}}
};

PropertyReplace[l,"LCFSignature"]

RenameGraphFiles[]

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"KC",{4,6}},{0,Missing["External",LCFNotation/@gs]}}
};

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

UnitDistance

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

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

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

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

3D default

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

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"KC", {4, 7}}

Names

GraphData[{"KC",{4,7}},"StandardName"]

GraphData[{"KC",{4,7}},"StandardNames"]

Primary

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

All

GraphData[{"KC",{4,7}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KC",{4,7}}]]

Default embedding

g=Graph[GraphData[{"KC",{4,7}},"VertexList"],GraphData[{"KC",{4,7}},"Edges"]]

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

RecognizeGraph@g

Degenerate

GraphData[{"KC",{4,7}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"KC",{4,7}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"KC",{4,7}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KC",{4,7}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"KC",{4,7}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KC",{4,7}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

GraphData[{"KC",{4,7}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"KC",{4,7}},"Hamiltonian"]

GraphData[{"KC",{4,7}},"LCF"]

GraphData[{"KC",{4,7}},"HamiltonianCycleCount"]

Planar

GraphData[{"KC",{4,7}},"Planar"]

GraphData[{"KC",{4,7}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"KC",{4,7}},{"RCN","CN"}]

GraphData[{"KC",{4,7}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

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

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

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

(cn=CrossingNumber[GraphData[{"KC",{4,7}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,7}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KC",{4,7}},"V"]&]

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"KC",{4,7}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}],Max[OuterFace[#]]<=GraphData[{"KC",{4,7}},"V"]&]])//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,7}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KC",{4,7}}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,7}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"KC",{4,7}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,7}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KC",{4,7}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,7}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,7}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,7}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,7}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,7}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"KC",{4,7}},"Circulant"]

GraphData[{"KC",{4,7}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"KC",{4,7}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KC",{4,7}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KC",{4,7}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KC",{4,7}},"ComplementGraph","Name"]

Line graph

GraphData[{"KC",{4,7}},"Line"]

LineGraphQ[GraphData[{"KC",{4,7}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"KC",{4,7}}]]

RecognizeGraph[%]

Halin

GraphData[{"KC",{4,7}},"Halin"]

GraphData[{"KC",{4,7}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KC",{4,7}},"Rigid"]

GraphData[{"KC",{4,7}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KC",{4,7}},"Flexible"]

GraphData[{"KC",{4,7}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KC",{4,7}},"LCF"]

GraphData[{"KC",{4,7}},"HamiltonianCycleCount"]

GraphData[{"KC",{4,7}},"LCFSignature"]

GraphData[{"KC",{4,7}},"LCFNotations"]

GraphData[{"KC",{4,7}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Divisors[GraphData[{"KC",{4,7}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"KC",{4,7}}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"KC",{4,7}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KC",{4,7}}],Debug->True]//Timing

GraphData[{"KC",{4,7}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"KC",{4,7}},"Matchstick"]

GraphData[{"KC",{4,7}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KC",{4,7}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"KC",{4,7}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"KC",{4,7}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"KC",{4,7}},"Polyhedral"]

GraphData[{"KC",{4,7}},"Graph",{"3D","Polyhedron"}]

{"KC", {4,  8}}

Names

GraphData[{"KC",{4,8}},"StandardName"]

GraphData[{"KC",{4,8}},"StandardNames"]

Primary

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

All

GraphData[{"KC",{4,8}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KC",{4,8}}]]

Default embedding

GraphPlot[Graph[GraphData[{"KC",{4,8}},"VertexList"],GraphData[{"KC",{4,8}},"Edges"]]]

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

RecognizeGraph@g

Degenerate

GraphData[{"KC",{4,8}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"KC",{4,8}},"Graph","Degenerate"]

Configuration

GetGraphData[{"KC",{4,8}},"File"]

GraphData[{"KC",{4,8}},"Configuration"]

GraphData[{"KC",{4,8}},"Graph","Configuration"]//StyleGraphs

Configuration...

config=%[[1]]

(alledges=AddAllConfigurationEdges[config])//Timing

RecognizeGraph@alledges

ConfigurationDiagram[config,.2]

lines=ConfigurationLines[config]

ConfigurationNotation[lines]

GraphData[{"KC",{4,8}},"IncidenceLines"]

levi=LeviGraph[lines]

RecognizeGraph[levi]

GraphData[{"KC",{4,8}},"LeviGraph","Name"]

FirstCase[GraphData[{"KC",{4,8}},"StandardNames"],{"Incidence",_}]

Cases[GraphData[{"KC",{4,8}},"StandardNames"],_String?(StringMatchQ[#,"*Configuration*"]&)]

GraphData[{"KC",{4,8}},"OrdinaryLineGraphName"]

(ordinarylinegraph=OrdinaryLineGraph[config])//Timing

RecognizeGraph@ordinarylinegraph

Incidence

GetGraphData[{"KC",{4,8}},"File"]

GraphData[{"KC",{4,8}},"Incidence"]

Select[GraphData[All],GraphData[#,"LeviGraph","Name"]==={"KC",{4,8}}&]

lines=GraphData[{"KC",{4,8}},"IncidenceLines"]

ConfigurationNotation[lines]

levi=LeviGraph[lines]

RecognizeGraph@levi

Stereographic projection construction

gs=PolyhedronProjectionGraph[GraphData[{"KC",{4,8}},"Polyhedron"],#]&/@{3/2,4}//StyleGraphs

Perspective

GraphData[{"KC",{4,8}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"KC",{4,8}},"Polyhedron"]

PolyhedronGraph[GraphData[{"KC",{4,8}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"KC",{4,8}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,8}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,8}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,8}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,8}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,8}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,8}},"Polyhedron"],{1,0,1},-Pi/2]

PolyhedronProjectionGraph[GraphData[{"KC",{4,8}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"KC",{4,8}},"NotationRules","HoneycombToroidal"]

HoneycombToroidal construction...

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"KC",{4,8}}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"KC",{4,8}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KC",{4,8}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"KC",{4,8}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KC",{4,8}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

GraphData[{"KC",{4,8}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"KC",{4,8}},"Hamiltonian"]

GraphData[{"KC",{4,8}},"LCF"]

GraphData[{"KC",{4,8}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"KC",{4,8}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"KC",{4,8}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(bilaterallyrotatedgraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[symmetricgraphs=DeleteDuplicatesBy[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Circular construction old

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"KC",{4,8}},"Planar"]

GraphData[{"KC",{4,8}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"KC",{4,8}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"KC",{4,8}}]],10]

PlanarGraphEmbeddings

GraphData[{"KC",{4,8}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"KC",{4,8}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"KC",{4,8}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"KC",{4,8}}],"OuterFace"->#]&/@faces

TextGrid[DeleteCases[{#,GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}],Dividers->All]

Grid[DeleteCases[{#,Cases[GraphSymmetryGroup[#],r_Rotation:>r,∞]}&/@gs,{_,{}}],Dividers->All]

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

TutteLayoutManipulate[g_Graph]:=Manipulate[
With[{face=OuterFace[g]},
IGLayoutTutte[IGEdgeMap[(EuclideanDistance@@#)^pow&,EdgeWeight->IGEdgeVertexProp[VertexCoordinates],IGLayoutTutte[g,"OuterFace"->face]],"OuterFace"->face,ImageSize->Automatic]],{{pow,1},.1,2}]

TutteLayoutManipulate[]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"KC",{4,8}},{"RCN","CN"}]

GraphData[{"KC",{4,8}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

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

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

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

(cn=CrossingNumber[GraphData[{"KC",{4,8}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,8}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KC",{4,8}},"V"]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,8}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KC",{4,8}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,8}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"KC",{4,8}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,8}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KC",{4,8}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,8}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,8}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,8}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,8}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,8}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"KC",{4,8}},"Circulant"]

GraphData[{"KC",{4,8}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"KC",{4,8}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KC",{4,8}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KC",{4,8}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KC",{4,8}},"ComplementGraph","Name"]

Line graph

GraphData[{"KC",{4,8}},"Line"]

LineGraphQ[GraphData[{"KC",{4,8}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"KC",{4,8}}]]

RecognizeGraph[%]

Halin

GraphData[{"KC",{4,8}},"Halin"]

GraphData[{"KC",{4,8}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KC",{4,8}},"Rigid"]

GraphData[{"KC",{4,8}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KC",{4,8}},"Flexible"]

GraphData[{"KC",{4,8}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KC",{4,8}},"LCF"]

GraphData[{"KC",{4,8}},"HamiltonianCycleCount"]

GraphData[{"KC",{4,8}},"LCFSignature"]

GraphData[{"KC",{4,8}},"LCFNotations"]

GraphData[{"KC",{4,8}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"KC",{4,8}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"KC",{4,8}}],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

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

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

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

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"KC",{4,8}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"KC",{4,8}}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"KC",{4,8}},".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

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

i=0;
gs={};
t0=AbsoluteTime[];
count=Length[order2];
Monitor[
Do[
If[!MissingQ[g=BilateralLCFGraph[LCFGraph@@order2[[i]]]],AppendTo[gs,g]],
{i,count}
],
Column[{
ProgressIndicator[i,{1,count}],
Row[{i,"/",count}],
Row[{"estimated time remaining: ",Round[(AbsoluteTime[]-t0) (count/i-1)]," s"}],
Row[{Length[gs]," bilateral graphs"}]
}]
];//Timing

UnitDistance

GraphData[{"KC",{4,8}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KC",{4,8}}],Debug->True]//Timing

GraphData[{"KC",{4,8}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Select[IndexGraph/@gs,!DegenerateGraphEmbeddingQ[#]&&GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]//Timing

Matchstick

GraphData[{"KC",{4,8}},"Matchstick"]

GraphData[{"KC",{4,8}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KC",{4,8}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"KC",{4,8}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"KC",{4,8}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"KC",{4,8}},"Polyhedral"]

GraphData[{"KC",{4,8}},"Graph",{"3D","Polyhedron"}]

{"KC", {4, 9}} == {"Circulant", {36, {4, 9, 18}}}

Names

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

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

{"KC", {4, 10}}

Names

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

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

Primary

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

All

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

Construction from connected components

cc=GraphData[{"KC",{4,10}},"ConnectedComponents","Name"]

GraphData[cc[[1]],"Graph","All"]

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

gs=MyGraphUnion[#,"K1"]&/@GraphData[cc[[1]],"Graph","All"]

RecognizeGraph/@gs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KC",{4,10}}]]

Default embedding

GraphPlot[Graph[GraphData[{"KC",{4,10}},"VertexList"],GraphData[{"KC",{4,10}},"Edges"]]]

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

RecognizeGraph@g

Degenerate

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

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

Configuration

GetGraphData[{"KC",{4,10}},"File"]

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

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

Configuration...

config=%[[1]]

(alledges=AddAllConfigurationEdges[config])//Timing

RecognizeGraph@alledges

ConfigurationDiagram[config,.2]

lines=ConfigurationLines[config]

ConfigurationNotation[lines]

GraphData[{"KC",{4,10}},"IncidenceLines"]

levi=LeviGraph[lines]

RecognizeGraph[levi]

GraphData[{"KC",{4,10}},"LeviGraph","Name"]

FirstCase[GraphData[{"KC",{4,10}},"StandardNames"],{"Incidence",_}]

Cases[GraphData[{"KC",{4,10}},"StandardNames"],_String?(StringMatchQ[#,"*Configuration*"]&)]

GraphData[{"KC",{4,10}},"OrdinaryLineGraphName"]

(ordinarylinegraph=OrdinaryLineGraph[config])//Timing

RecognizeGraph@ordinarylinegraph

Incidence

GetGraphData[{"KC",{4,10}},"File"]

GraphData[{"KC",{4,10}},"Incidence"]

Select[GraphData[All],GraphData[#,"LeviGraph","Name"]==={"KC",{4,10}}&]

lines=GraphData[{"KC",{4,10}},"IncidenceLines"]

ConfigurationNotation[lines]

levi=LeviGraph[lines]

RecognizeGraph@levi

Stereographic projection construction

gs=PolyhedronProjectionGraph[GraphData[{"KC",{4,10}},"Polyhedron"],#]&/@{3/2,4}//StyleGraphs

Perspective

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

Perspective construction

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

PolyhedronGraph[GraphData[{"KC",{4,10}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"KC",{4,10}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,10}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,10}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,10}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,10}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,10}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"KC",{4,10}},"Polyhedron"],{1,0,1},-Pi/2]

PolyhedronProjectionGraph[GraphData[{"KC",{4,10}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"KC",{4,10}},"NotationRules","HoneycombToroidal"]

HoneycombToroidal construction...

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"KC",{4,10}}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

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

IGraph

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

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KC",{4,10}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

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

Circular construction

GraphData[{"KC",{4,10}},"Hamiltonian"]

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

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

Length[hc=FindHamiltonianCycle[GraphData[{"KC",{4,10}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"KC",{4,10}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(bilaterallyrotatedgraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[symmetricgraphs=DeleteDuplicatesBy[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Circular construction old

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

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

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

Planar construction

PlanarGraphEmbedding[GraphData[{"KC",{4,10}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"KC",{4,10}}]],10]

PlanarGraphEmbeddings

GraphData[{"KC",{4,10}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"KC",{4,10}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"KC",{4,10}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"KC",{4,10}}],"OuterFace"->#]&/@faces

TextGrid[DeleteCases[{#,GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}],Dividers->All]

Grid[DeleteCases[{#,Cases[GraphSymmetryGroup[#],r_Rotation:>r,∞]}&/@gs,{_,{}}],Dividers->All]

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

TutteLayoutManipulate[g_Graph]:=Manipulate[
With[{face=OuterFace[g]},
IGLayoutTutte[IGEdgeMap[(EuclideanDistance@@#)^pow&,EdgeWeight->IGEdgeVertexProp[VertexCoordinates],IGLayoutTutte[g,"OuterFace"->face]],"OuterFace"->face,ImageSize->Automatic]],{{pow,1},.1,2}]

TutteLayoutManipulate[]

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

RecognizeGraph[g]

MinimalCrossing

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

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

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,10}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KC",{4,10}},"V"]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,10}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KC",{4,10}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,10}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"KC",{4,10}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,10}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KC",{4,10}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{4,10}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,10}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,10}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{4,10}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{4,10}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

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

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

Circulant construction

GraphData[{"KC",{4,10}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KC",{4,10}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KC",{4,10}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

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

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

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

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

RootGraph

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

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

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

LCF compute random

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

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"KC",{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

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

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

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

RenameGraphFiles[]

LCF compute all

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

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

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"KC",{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

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

i=0;
gs={};
t0=AbsoluteTime[];
count=Length[order2];
Monitor[
Do[
If[!MissingQ[g=BilateralLCFGraph[LCFGraph@@order2[[i]]]],AppendTo[gs,g]],
{i,count}
],
Column[{
ProgressIndicator[i,{1,count}],
Row[{i,"/",count}],
Row[{"estimated time remaining: ",Round[(AbsoluteTime[]-t0) (count/i-1)]," s"}],
Row[{Length[gs]," bilateral graphs"}]
}]
];//Timing

UnitDistance

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

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Select[IndexGraph/@gs,!DegenerateGraphEmbeddingQ[#]&&GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]//Timing

Matchstick

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

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

3D default

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

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

Graphics3D[{FaceForm[Green,Red],GraphData[{"KC",{4,10}},"Polyhedron"]}]

3D Canonical

GraphData[{"KC",{4,10}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"KC",{4,10}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"KC",{4,10}}],1]}]

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->50,MaxIterations->50000,PrecisionGoal->20,"ProgressInterval"->1000,"TangentFactor"->1/10,"PlanarFactor"->1/10,Debug->True])//Timing

SimplePolyhedronQ[can]

If[%===False,Quit[]]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

3D Canonical construction from PolyhedralEmbedding

g=GraphData[{"KC",{4,10}},"Graph","Planar"][[1]]

Show[g2=PolyhedralEmbedding[g,"Circular"->True,"Scale"->3],Boxed->True]//Quiet

With[
{faces=PlanarFaceList[Graph[EdgeList[g2]]],v=GraphEmbedding@g2},
Graphics3D[{Point[{0,0,0}],Opacity[.5],Sphere[],FaceForm[Green,Red],
poly=Polyhedron[1.2v,faces]}]]

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->100,MaxIterations->20000,PrecisionGoal->20,"ProgressInterval"->100,"TangentFactor"->1/5,"PlanarFactor"->1/5,Debug->True])//Timing

SimplePolyhedronQ[can]

If[%===False,Quit[]]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

{"KC", {5, 3}} == {"Circulant", {15, {3, 5, 6}}}

Names

GraphData[{"KC",{5,3}},"StandardName"]

GraphData[{"KC",{5,3}},"StandardNames"]

{"KC", {5, 4}} == {"Circulant", {20, {4, 5, 8}}}

Names

GraphData[{"KC",{5,4}},"StandardName"]

GraphData[{"KC",{5,4}},"StandardNames"]

{"KC", {5, 5}}

Names

GraphData[{"KC",{5,5}},"StandardName"]

GraphData[{"KC",{5,5}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KC",{5,5}}]]

Default embedding

GraphPlot[Graph[GraphData[{"KC",{5,5}},"VertexList"],GraphData[{"KC",{5,5}},"Edges"]]]

GraphPlot[Graph[GraphData[{"KC",{5,5}},"VertexList"],GraphData[{"KC",{5,5}},"Edges"],GraphLayout->"RadialEmbedding"]]

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

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"KC",{5,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KC",{5,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KC",{5,5}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

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

Circular construction

GraphData[{"KC",{5,5}},"Hamiltonian"]

GraphData[{"KC",{5,5}},"LCF"]

GraphData[{"KC",{5,5}},"HamiltonianCycleCount"]

Planar

GraphData[{"KC",{5,5}},"Planar"]

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

MinimalCrossing

GraphData[{"KC",{5,5}},{"RCN","CN"}]

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

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"KC",{5,5}}],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"KC",{5,5}}],TimeConstraint->60])//AbsoluteTiming

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

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

(cn=CrossingNumber[GraphData[{"KC",{5,5}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"KC",{5,5}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"KC",{5,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{5,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KC",{5,5}},"V"]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{5,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KC",{5,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{5,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"KC",{5,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{5,5}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KC",{5,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{5,5}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{5,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{5,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{5,5}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{5,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"KC",{5,5}},"Circulant"]

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

Circulant construction

GraphData[{"KC",{5,5}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KC",{5,5}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KC",{5,5}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

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

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"KC",{5,5}},"Line"]

LineGraphQ[GraphData[{"KC",{5,5}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"KC",{5,5}}]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

GraphData[{"KC",{5,5}},"Halin"]

GraphData[{"KC",{5,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KC",{5,5}},"Rigid"]

GraphData[{"KC",{5,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KC",{5,5}},"Flexible"]

GraphData[{"KC",{5,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KC",{5,5}},"LCF"]

GraphData[{"KC",{5,5}},"HamiltonianCycleCount"]

GraphData[{"KC",{5,5}},"LCFSignature"]

GraphData[{"KC",{5,5}},"LCFNotations"]

GraphData[{"KC",{5,5}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"KC",{5,5}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"KC",{5,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

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"KC",{5,5}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

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

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"KC",{5,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"KC",{5,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"KC",{5,5}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"KC",{5,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

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

i=0;
gs={};
t0=AbsoluteTime[];
count=Length[order2];
Monitor[
Do[
If[!MissingQ[g=BilateralLCFGraph[LCFGraph@@order2[[i]]]],AppendTo[gs,g]],
{i,count}
],
Column[{
ProgressIndicator[i,{1,count}],
Row[{i,"/",count}],
Row[{"estimated time remaining: ",Round[(AbsoluteTime[]-t0) (count/i-1)]," s"}],
Row[{Length[gs]," bilateral graphs"}]
}]
];//Timing

UnitDistance

GraphData[{"KC",{5,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KC",{5,5}}],Debug->True]//Timing

GraphData[{"KC",{5,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"KC",{5,5}},"VertexList"],GraphData[{"KC",{5,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"KC",{5,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Select[IndexGraph/@gs,!DegenerateGraphEmbeddingQ[#]&&GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]//Timing

Matchstick

GraphData[{"KC",{5,5}},"Matchstick"]

GraphData[{"KC",{5,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KC",{5,5}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"KC",{5,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"KC",{5,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"KC",{5,5}},"Polyhedral"]

GraphData[{"KC",{5,5}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"KC",{5,5}},"Polyhedron"]}]

3D Canonical

GraphData[{"KC",{5,5}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"KC",{5,5}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"KC",{5,5}}],1]}]

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->50,MaxIterations->50000,PrecisionGoal->20,"ProgressInterval"->1000,"TangentFactor"->1/10,"PlanarFactor"->1/10,Debug->True])//Timing

SimplePolyhedronQ[can]

If[%===False,Quit[]]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

3D Canonical construction from PolyhedralEmbedding

g=GraphData[{"KC",{5,5}},"Graph","Planar"][[1]]

Show[g2=PolyhedralEmbedding[g,"Circular"->True,"Scale"->3],Boxed->True]//Quiet

With[
{faces=PlanarFaceList[Graph[EdgeList[g2]]],v=GraphEmbedding@g2},
Graphics3D[{Point[{0,0,0}],Opacity[.5],Sphere[],FaceForm[Green,Red],
poly=Polyhedron[1.2v,faces]}]]

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->100,MaxIterations->20000,PrecisionGoal->20,"ProgressInterval"->100,"TangentFactor"->1/5,"PlanarFactor"->1/5,Debug->True])//Timing

SimplePolyhedronQ[can]

If[%===False,Quit[]]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

{"KC", {5, 6}}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KC",{5,6}}]]

Default embedding

g=Graph[GraphData[{"KC",{5,6}},"VertexList"],GraphData[{"KC",{5,6}},"Edges"]]

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

RecognizeGraph@g

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData[{"KC",{5,6}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"KC",{5,6}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KC",{5,6}},"Graph","IGraph"]//StyleGraphs

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KC",{5,6}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

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

Circular construction

GraphData[{"KC",{5,6}},"Hamiltonian"]

GraphData[{"KC",{5,6}},"LCF"]

GraphData[{"KC",{5,6}},"HamiltonianCycleCount"]

Planar

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

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

MinimalCrossing

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

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

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{5,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KC",{5,6}},"V"]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{5,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KC",{5,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{5,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"KC",{5,6}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{5,6}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KC",{5,6}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KC",{5,6}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{5,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{5,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KC",{5,6}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KC",{5,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

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

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

Circulant construction

GraphData[{"KC",{5,6}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KC",{5,6}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KC",{5,6}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

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

Line graph

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

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

RootGraph

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

RootGraph[GraphData[{"KC",{5,6}}]]

RecognizeGraph[%]

Halin

GraphData[{"KC",{5,6}},"Halin"]

GraphData[{"KC",{5,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KC",{5,6}},"Rigid"]

GraphData[{"KC",{5,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KC",{5,6}},"Flexible"]

GraphData[{"KC",{5,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KC",{5,6}},"LCF"]

GraphData[{"KC",{5,6}},"HamiltonianCycleCount"]

GraphData[{"KC",{5,6}},"LCFSignature"]

GraphData[{"KC",{5,6}},"LCFNotations"]

GraphData[{"KC",{5,6}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"KC",{5,6}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"KC",{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,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"KC",{5,6}}],10^6])[[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={
{{"KC",{5,6}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"KC",{5,6}}],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={
{{"KC",{5,6}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"KC",{5,6}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"KC",{5,6}}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"KC",{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[{"KC",{5,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KC",{5,6}}],Debug->True]//Timing

GraphData[{"KC",{5,6}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"KC",{5,6}},"Matchstick"]

GraphData[{"KC",{5,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KC",{5,6}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"KC",{5,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"KC",{5,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"KC",{5,6}},"Polyhedral"]

GraphData[{"KC",{5,6}},"Graph",{"3D","Polyhedron"}]

{"KC", {5, 7}} == {"Circulant", {35, {5, 7, 14}}}

Names

GraphData[{"KC",{5,7}},"StandardName"]

GraphData[{"KC",{5,7}},"StandardNames"]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"KC",{5,7}}],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={
{{"KC",{5,6}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

{"KC", {5, 8}} == {"Circulant", {40, {5, 8, 16}}}

Names

GraphData[{"KC",{5,8}},"StandardName"]

GraphData[{"KC",{5,8}},"StandardNames"]

{"KC", {5, 9}} == {"Circulant", {45, {5, 9, 18}}}

Names

GraphData[{"KC",{5,8}},"StandardName"]

GraphData[{"KC",{5,8}},"StandardNames"]

{"KC", {6, 5}} == {"Circulant", {30, {5, 6, 10, 15}}}

Names

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

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

{"KC", {6, 7}} == {"Circulant", {42, {6, 7, 14, 21}}}

Names

GraphData[{"KC",{6,7}},"StandardName"]

GraphData[{"KC",{6,7}},"StandardNames"]

{"KC", {7, 4}} == {"Circulant", {28, {4, 7, 8, 12}}}

Names

GraphData[{"KC",{7,4}},"StandardName"]

GraphData[{"KC",{7,4}},"StandardNames"]

{"KC", {7, 5}} == {"Circulant", {35, {5, 7, 10, 15}}}

Names

GraphData[{"KC",{7,5}},"StandardName"]

GraphData[{"KC",{7,5}},"StandardNames"]

{"KC", {7, 6}} == {"Circulant", {42, {6, 7, 12, 18}}}

Names

GraphData[{"KC",{7,6}},"StandardName"]

GraphData[{"KC",{7,6}},"StandardNames"]

{"KC", {7, 8}} == {"Circulant", {56, {7, 8, 16, 24}}}

Names

GraphData[{"KC",{7,8}},"StandardName"]

GraphData[{"KC",{7,8}},"StandardNames"]

{"KC", {7, 9}} == {"Circulant", {63, {7, 9, 18, 27}}}

Names

GraphData[{"KC",{7,9}},"StandardName"]

GraphData[{"KC",{7,9}},"StandardNames"]

{"KC", {7, 10}} == {"Circulant", {70, {7, 10, 20, 30}}}

Names

GraphData[{"KC",{7,10}},"StandardName"]

GraphData[{"KC",{7,10}},"StandardNames"]

{"KC", {8, 5}} == {"Circulant", {40, {5, 8, 10, 15, 20}}}

Names

GraphData[{"KC",{8,5}},"StandardName"]

GraphData[{"KC",{8,5}},"StandardNames"]

{"KC", {8, 7}} == {"Circulant", {56, {7, 8, 14, 21, 28}}}

Names

GraphData[{"KC",{8,7}},"StandardName"]

GraphData[{"KC",{8,7}},"StandardNames"]

{"KC", {8, 9}} == {"Circulant", {72, {8, 9, 18, 27, 36}}}

Names

GraphData[{"KC",{8,9}},"StandardName"]

GraphData[{"KC",{8,9}},"StandardNames"]

{"KC", {9, 4}} == {"Circulant", {36, {4, 8, 9, 12, 16}}}

Names

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

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

{"KC", {9, 5}} == {"Circulant", {45, {5, 9, 10, 15, 20}}}

Names

GraphData[{"KC",{9,5}},"StandardName"]

GraphData[{"KC",{9,5}},"StandardNames"]

{"KC", {9, 7}} == {"Circulant", {63, {7, 9, 14, 21, 28}}}

Names

GraphData[{"KC",{9,7}},"StandardName"]

GraphData[{"KC",{9,7}},"StandardNames"]

{"KC", {9, 8}} == {"Circulant", {72, {8, 9, 16, 24, 32}}}

Names

GraphData[{"KC",{9,8}},"StandardName"]

GraphData[{"KC",{9,8}},"StandardNames"]

{"KC", {9, 10}} == {"Circulant", {90, {9, 10, 20, 30, 40}}}

Names

GraphData[{"KC",{9,10}},"StandardName"]

GraphData[{"KC",{9,10}},"StandardNames"]

{"KC", {10, 3}} == {"Circulant", {30, {3, 6, 9, 10, 12, 15}}}

Names

GraphData[{"KC",{10,3}},"StandardName"]

GraphData[{"KC",{10,3}},"StandardNames"]

{"KC", {10, 7}} == {"Circulant", {70, {7, 10, 14, 21, 28, 35}}}

Names

GraphData[{"KC",{10,7}},"StandardName"]

GraphData[{"KC",{10,7}},"StandardNames"]

{"KC", {10, 9}} == {"Circulant", {90, {9, 10, 18, 27, 36, 45}}}

Names

GraphData[{"KC",{10,9}},"StandardName"]

GraphData[{"KC",{10,9}},"StandardNames"]

GraphDataCountTable

GraphDataCountTable["KC"]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"KC"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"KC"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"KC"],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"KC"],{n,20}]

Antiprism

Entity["Graph",{"Antiprism",n}]["KC"]

seq=Table[GraphData[{"Antiprism",n},"KC"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"KC"],{n,5}]

Barbell

seq=Table[GraphData[{"Barbell",n},"KC"],{n,3,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"KC"],{n,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"KC"],{n,20}]

Book

seq=Table[GraphData[{"Book",n},"KC"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"KC"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"KC"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"KC"],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"KC"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["KC"]

seq=Table[GraphData[{"Complete",n},"KC"],{n,30}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["KC"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"KC"],{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["KC"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"KC"],
Piecewise[{{True,m==n==2}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["KC"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"KC"],{n,10}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["KC"]

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"KC"],
Piecewise[{{True,k==m==n==1}},False]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"KC"],{n,2,12}]

Crown

seq=Table[GraphData[{"Crown",n},"KC"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["KC"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"KC"],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["KC"]

seq=Table[GraphData[{"Cycle",n},"KC"],{n,3,30}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"KC"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"KC"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"KC"],{n,3,20}]

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"KC"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"KC"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["KC"]

seq=Table[GraphData[{"Empty",n},"KC"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"KC"],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"KC"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"KC"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"KC"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"KC"],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"KC"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"KC"],{n,3,20}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["KC"]

seq=Table[GraphData[{"Grid",{n,n}},"KC"],{n,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["KC"]

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"KC"],
Piecewise[{{True,m==n==2}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["KC"]

seq=Table[GraphData[{"Grid",{n,n,n}},"KC"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["KC"]

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"KC"],
Piecewise[{{True,k==m==n==2||(Min[k,m,n]==1&&Max[k,m,n]==2&&k m n==4)}},False]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"KC"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"KC"],{n,6}]

Helm

seq=Table[GraphData[{"Helm",n},"KC"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["KC"]

seq=Table[GraphData[{"Hypercube",n},"KC"],{n,0,10}]

KC

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KC",{m,n}},"KC"],
True
},{n,3,10},{m,10}],1],{_,x_,x_}]

Keller

Entity["Graph",{"Keller",n}]["KC"]

seq=Table[GraphData[{"Keller",n},"KC"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"KC"],{n,20}]

King m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"KC"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["KC"]

seq=Table[GraphData[{"Knight",{n,n}},"KC"],{n,20}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["KC"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"KC"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

KP

Select[GraphData["KP"],GraphData[#,"KC"]&]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KP",{m,n}},"KC"],
False
},{n,3,10},{m,10}],1],{_,x_,x_}]

Ladder

Entity["Graph",{"Ladder",n}]["KC"]

seq=Table[GraphData[{"Ladder",n},"KC"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"KC"],{n,20}]

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"KC"],{n,11}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"KC"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"KC"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["KC"]

seq=Table[GraphData[{"MoebiusLadder",n},"KC"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["KC"]

seq=Table[GraphData[{"Mycielski",n},"KC"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["KC"]

seq=Table[GraphData[{"Odd",n},"KC"],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"KC"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["KC"]

seq=Table[GraphData[{"Path",n},"KC"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"KC"],{n,20}]

Pell

seq=Table[GraphData[{"Pell",n},"KC"],{n,9}]

PlummerToft

seq=Table[GraphData[{"PlummerToft",n},"KC"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["KC"]

seq=Table[GraphData[{"Prism",n},"KC"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"KC"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"KC"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"KC"],{n,20}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"KC"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"KC"],{n,7}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"KC"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"KC"],{n,5}]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"KC"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"KC"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["KC"]

seq=Table[GraphData[{"Star",n},"KC"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"KC"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"KC"],{n,3,20}]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"KC"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"KC"],{n,3,20}]

Transposition

Entity["Graph",{"Transposition",n}]["KC"]

seq=Table[GraphData[{"Transposition",n},"KC"],{n,6}]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["KC"]

seq=Table[GraphData[{"Trapezohedron",n},"KC"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"KC"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"KC"],{n,0,20}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"KC"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"KC"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"KC"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"KC"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"KC"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"KC"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"KC"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["KC"]

seq=Table[GraphData[{"Wheel",n},"KC"],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"KC"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"KC"],{n,2,20}]

WhiteCamel n×n

seq=Table[GraphData[{"Bishop",{n,n}},"KC"],{n,{5}}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"KC"],{n,20}]

GraphData

GraphDataClassString

GraphDataClassString["KC"]

AddIndexedClass

<<MathWorld`Graphs`

rules=Flatten[Table[RecognizeGraph[KCGraph[n,r],"Cache"->"InternalOnly"]->{n,r},{n,30},{r,3,30}]]

addrules=DeleteCases[rules,HoldPattern[{}->_]]

AddIndexedClass["KC",addrules,"14.3"]

RenameGraphFiles[]

Rename remaining circulants not caught at generation time

circulants={{"KC",{7,10}},{"KC",{8,7}},{"KC",{8,9}},{"KC",{9,7}},{"KC",{9,8}},{"KC",{9,10}},{"KC",{10,7}},{"KC",{10,9}}};

Print[{#,CirculantIndices[GraphData[#],All]//Timing}]&/@circulants;

altstdnames={#,{0,Union[GraphData[#,"AlternateStandardNames"],{"Circulant",#}&/@#2[[2]]]}}&@@@l

PropertyReplace[altstdnames,"AlternateStandardNames","14.3"]

RenameGraphFiles[]

altnames={#,{0,Union[GraphData[#,"AlternateNames"],Function[f,ToString[f[[1]]]<>"\[Hyphen]circulant graph ("<>StringReplace[StringTake[ToString[f[[2]]],{2,-2}]," "->""]<>")"]/@#2[[2]]]}}&@@@l

PropertyReplace[altnames,"AlternateNames","14.3"]

RenameGraphFiles[]

renamingrules=Rule[#,{"Circulant",#2[[2,1]]}]&@@@l

GraphDataString

new=Cases[Flatten[Table[RecognizeGraph[KCGraph[n,r],"Cache"->"InternalOnly"]->{n,r},{n,10},{r,3,10}]],HoldPattern[{}->nr_]:>nr]

Length[new]

todo={{10,4},{10,5},{10,6},{10,7},{10,8},{10,9},{10,10}};

file=OpenAppend["~/kc.m"]

WriteString[file,
GraphDataString[KCGraph[#,#2],
"StandardName"->{"KC",{#,#2}},
"Name"->"("<>ToString[#]<>","<>ToString[#]<>")\[Hyphen]KC graph",
"Classes"->{"KC"},
"NotationRules"->{"KC"->{#,#2}},
"Information"->"KCGraph",
"Notation"->Row[{Subscript["K",#1],"\[Square]",Subscript["C",#2]}],
"Skip"->{"Arboricity","ChromaticPolynomial","ConnectedDominatingSet","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","ConstructionNumber","Cycles","CyclicEdgeConnectivity","ErdosSequence","GracefulLabeling","HadwigerNumber","HamiltonianPaths","IntersectionNumber","IrredundancePolynomial","IrredundantSets","LinklesslyEmbeddable","MatchingGeneratingPolynomial","MaximalIndependentEdgeSet","MinimumConnectedDominatingSet","MinimumEdgeCuts","MinimumPathCoverings","MinimumVertexCuts","Minors","ProjectivePlanar","QuadraticEmbeddingConstant","Skewness","Thickness","TuttePolynomial","VertexCuts"},
TimeConstraint->10
]]&@@@todo;

Close[file]