k-Cyclic Graph

Author

Eric W. Weisstein
October 25, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/k-CyclicGraph.nb.

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

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

Lengths

Table[Length[KCyclicGraphs[k]],{k,17}]//Timing

Figure

bug(453260): GraphicsGrid[..., ImageSize -> 250, Alignment -> Top] cuts off labels and fails to display content

GraphicsGrid[
Flatten[Partition[#,UpTo[6]]&/@Map[Show[StyleGraphs@GraphData[#],PlotLabel->TextCell[Style[StringReplace[GraphData[#,"Name"],"\[Hyphen]"->"-"],Black,Italic,FontFamily->"Times"],PageWidth->600/6,TextAlignment->Center]]&,Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,7}],{2}],1],Dividers->All,ImageSize->600,Alignment->Top
]

Embeddings

GraphData["KCyclic*"]

<<MathWorld`Graphs`

{"KCyclic", {9, 56}}

Names

GraphData[{"KCyclic",{9,56}},"StandardName"]

GraphData[{"KCyclic",{9,56}},"StandardNames"]

Primary

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

All

GraphData[{"KCyclic",{9,56}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KCyclic",{9,56}}]]

Default embedding

GraphPlot[Graph[GraphData[{"KCyclic",{9,56}},"VertexList"],GraphData[{"KCyclic",{9,56}},"Edges"]]]

s=Sqrt[3]/2;
v=CirclePoints[{1,-Pi/2},6];
v={#,-#2}&@@@Join[v,v[[4]]+{#/2,s}&/@{-1,1}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[{1,6},1],e[4,8,7,4]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

GraphData[{"KCyclic",{9,56}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"KCyclic",{9,56}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"KCyclic",{9,56}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KCyclic",{9,56}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"KCyclic",{9,56}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"KCyclic",{9,56}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"KCyclic",{9,56}},"Hamiltonian"]

GraphData[{"KCyclic",{9,56}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"KCyclic",{9,56}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"KCyclic",{9,56}}],#]&/@hc);//Timing

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

Tally[sym[[All,-1]]]

DeleteCases[sym,{_,TransformationGroup[{}]}]

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

gs=bilat

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

quad

Planar

GraphData[{"KCyclic",{9,56}},"Planar"]

GraphData[{"KCyclic",{9,56}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"KCyclic",{9,56}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"KCyclic",{9,56}}]],10]

PlanarGraphEmbeddings

GraphData[{"KCyclic",{9,56}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"KCyclic",{9,56}}],Debug->True])//Timing

Length[plemb]

MinimalCrossing

GraphData[{"KCyclic",{9,56}},{"RCN","CN"}]

GraphData[{"KCyclic",{9,56}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

(cn=CrossingNumber[GraphData[{"KCyclic",{9,56}}],TimeConstraint->86400])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"KCyclic",{9,56}},"V"]&]

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KCyclic",{9,56}},"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[{"KCyclic",{9,56}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KCyclic",{9,56}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KCyclic",{9,56}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KCyclic",{9,56}},"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[{"KCyclic",{9,56}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"KCyclic",{9,56}},"Circulant"]

GraphData[{"KCyclic",{9,56}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"KCyclic",{9,56}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KCyclic",{9,56}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KCyclic",{9,56}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KCyclic",{9,56}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

gs={,,,};

Line graph

GraphData[{"KCyclic",{9,56}},"Line"]

LineGraphQ[GraphData[{"KCyclic",{9,56}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"KCyclic",{9,56}}]]

RecognizeGraph[%]

Halin

GraphData[{"KCyclic",{9,56}},"Halin"]

GraphData[{"KCyclic",{9,56}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KCyclic",{9,56}},"Rigid"]

GraphData[{"KCyclic",{9,56}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KCyclic",{9,56}},"Flexible"]

GraphData[{"KCyclic",{9,56}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KCyclic",{9,56}},"LCF"]

GraphData[{"KCyclic",{9,56}},"HamiltonianCycleCount"]

GraphData[{"KCyclic",{9,56}},"LCFSignature"]

GraphData[{"KCyclic",{9,56}},"LCFNotations"]

GraphData[{"KCyclic",{9,56}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"KCyclic",{9,56}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KCyclic",{9,56}}],Debug->True]//Timing

GraphData[{"KCyclic",{9,56}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

gs={,RotateGraph[,Pi],RotateGraph[,Pi],}

Matchstick

GraphData[{"KCyclic",{9,56}},"Matchstick"]

GraphData[{"KCyclic",{9,56}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KCyclic",{9,56}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"KCyclic",{9,56}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"KCyclic",{9,56}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"KCyclic",{9,56}},"Polyhedral"]

GraphData[{"KCyclic",{9,56}},"Graph",{"3D","Polyhedron"}]

{"KCyclic", {9, 57}}

Names

GraphData[{"KCyclic",{9,57}},"StandardName"]

GraphData[{"KCyclic",{9,57}},"StandardNames"]

Primary

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

All

GraphData[{"KCyclic",{9,57}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KCyclic",{9,57}}]]

Default embedding

GraphPlot[Graph[GraphData[{"KCyclic",{9,57}},"VertexList"],GraphData[{"KCyclic",{9,57}},"Edges"]]]

RecognizeGraph@g

Degenerate

GraphData[{"KCyclic",{9,57}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"KCyclic",{9,57}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"KCyclic",{9,57}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KCyclic",{9,57}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"KCyclic",{9,57}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"KCyclic",{9,57}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"KCyclic",{9,57}},"Hamiltonian"]

GraphData[{"KCyclic",{9,57}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"KCyclic",{9,57}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"KCyclic",{9,57}}],#]&/@hc);//Timing

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

Tally[sym[[All,-1]]]

DeleteCases[sym,{_,TransformationGroup[{}]}]

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

gs=bilat

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

quad

Planar

GraphData[{"KCyclic",{9,57}},"Planar"]

GraphData[{"KCyclic",{9,57}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"KCyclic",{9,57}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"KCyclic",{9,57}}]],10]

PlanarGraphEmbeddings

GraphData[{"KCyclic",{9,57}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"KCyclic",{9,57}}],Debug->True])//Timing

Length[plemb]

MinimalCrossing

GraphData[{"KCyclic",{9,57}},{"RCN","CN"}]

GraphData[{"KCyclic",{9,57}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

(cn=CrossingNumber[GraphData[{"KCyclic",{9,57}}],TimeConstraint->86400])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"KCyclic",{9,57}},"V"]&]

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KCyclic",{9,57}},"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[{"KCyclic",{9,57}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KCyclic",{9,57}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KCyclic",{9,57}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KCyclic",{9,57}},"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[{"KCyclic",{9,57}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"KCyclic",{9,57}},"Circulant"]

GraphData[{"KCyclic",{9,57}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"KCyclic",{9,57}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KCyclic",{9,57}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KCyclic",{9,57}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KCyclic",{9,57}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"KCyclic",{9,57}},"Line"]

LineGraphQ[GraphData[{"KCyclic",{9,57}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"KCyclic",{9,57}}]]

RecognizeGraph[%]

Halin

GraphData[{"KCyclic",{9,57}},"Halin"]

GraphData[{"KCyclic",{9,57}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KCyclic",{9,57}},"Rigid"]

GraphData[{"KCyclic",{9,57}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KCyclic",{9,57}},"Flexible"]

GraphData[{"KCyclic",{9,57}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KCyclic",{9,57}},"LCF"]

GraphData[{"KCyclic",{9,57}},"HamiltonianCycleCount"]

GraphData[{"KCyclic",{9,57}},"LCFSignature"]

GraphData[{"KCyclic",{9,57}},"LCFNotations"]

GraphData[{"KCyclic",{9,57}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"KCyclic",{9,57}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KCyclic",{9,57}}],Debug->True]//Timing

GraphData[{"KCyclic",{9,57}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

gs=LabelGraph/@{RotateGraph[,{19,21}],,,}

Matchstick

GraphData[{"KCyclic",{9,57}},"Matchstick"]

GraphData[{"KCyclic",{9,57}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KCyclic",{9,57}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"KCyclic",{9,57}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"KCyclic",{9,57}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"KCyclic",{9,57}},"Polyhedral"]

GraphData[{"KCyclic",{9,57}},"Graph",{"3D","Polyhedron"}]

{"KCyclic", {11, 208}}

Names

GraphData[{"KCyclic",{11,208}},"StandardName"]

GraphData[{"KCyclic",{11,208}},"StandardNames"]

Primary

GraphData[{"KCyclic",{11,208}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"KCyclic",{11,208}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KCyclic",{11,208}}]]

Default embedding

GraphPlot[Graph[GraphData[{"KCyclic",{11,208}},"VertexList"],GraphData[{"KCyclic",{11,208}},"Edges"]]]

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

RecognizeGraph@g

Degenerate

GraphData[{"KCyclic",{11,208}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"KCyclic",{11,208}},"Graph","Degenerate"]

Configuration

GetGraphData[{"KCyclic",{11,208}},"File"]

GraphData[{"KCyclic",{11,208}},"Configuration"]

GraphData[{"KCyclic",{11,208}},"Graph","Configuration"]//StyleGraphs

Configuration...

config=%[[1]]

(alledges=AddAllConfigurationEdges[config])//Timing

RecognizeGraph@alledges

ConfigurationDiagram[config,.2]

lines=ConfigurationLines[config]

ConfigurationNotation[lines]

GraphData[{"KCyclic",{11,208}},"IncidenceLines"]

levi=LeviGraph[lines]

RecognizeGraph[levi]

GraphData[{"KCyclic",{11,208}},"LeviGraph","Name"]

FirstCase[GraphData[{"KCyclic",{11,208}},"StandardNames"],{"Incidence",_}]

Cases[GraphData[{"KCyclic",{11,208}},"StandardNames"],_String?(StringMatchQ[#,"*Configuration*"]&)]

GraphData[{"KCyclic",{11,208}},"OrdinaryLineGraphName"]

(ordinarylinegraph=OrdinaryLineGraph[config])//Timing

RecognizeGraph@ordinarylinegraph

Incidence

GetGraphData[{"KCyclic",{11,208}},"File"]

GraphData[{"KCyclic",{11,208}},"Incidence"]

Select[GraphData[All],GraphData[#,"LeviGraph","Name"]==={"KCyclic",{11,208}}&]

lines=GraphData[{"KCyclic",{11,208}},"IncidenceLines"]

ConfigurationNotation[lines]

levi=LeviGraph[lines]

RecognizeGraph@levi

Stereographic projection construction

gs=PolyhedronProjectionGraph[GraphData[{"KCyclic",{11,208}},"Polyhedron"],#]&/@{3/2,4}//StyleGraphs

Perspective

GraphData[{"KCyclic",{11,208}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"KCyclic",{11,208}},"Polyhedron"]

PolyhedronGraph[GraphData[{"KCyclic",{11,208}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"KCyclic",{11,208}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"KCyclic",{11,208}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"KCyclic",{11,208}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"KCyclic",{11,208}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"KCyclic",{11,208}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"KCyclic",{11,208}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"KCyclic",{11,208}},"Polyhedron"],{1,0,1},-Pi/2]

PolyhedronProjectionGraph[GraphData[{"KCyclic",{11,208}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"KCyclic",{11,208}},"NotationRules","HoneycombToroidal"]

HoneycombToroidal construction...

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"KCyclic",{11,208}}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"KCyclic",{11,208}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KCyclic",{11,208}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"KCyclic",{11,208}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"KCyclic",{11,208}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"KCyclic",{11,208}},"Hamiltonian"]

GraphData[{"KCyclic",{11,208}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"KCyclic",{11,208}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"KCyclic",{11,208}}],#]&/@hc);//Timing

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

Tally[sym[[All,-1]]]

DeleteCases[sym,{_,TransformationGroup[{}]}]

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

gs=bilat

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

quad

Planar

GraphData[{"KCyclic",{11,208}},"Planar"]

GraphData[{"KCyclic",{11,208}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"KCyclic",{11,208}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"KCyclic",{11,208}}]],10]

PlanarGraphEmbeddings

GraphData[{"KCyclic",{11,208}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"KCyclic",{11,208}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"KCyclic",{11,208}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"KCyclic",{11,208}}],"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[{"KCyclic",{11,208}},{"RCN","CN"}]

GraphData[{"KCyclic",{11,208}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"KCyclic",{11,208}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KCyclic",{11,208}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KCyclic",{11,208}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KCyclic",{11,208}}],TimeConstraint->3600])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"KCyclic",{11,208}}],TimeConstraint->86400])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"KCyclic",{11,208}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"KCyclic",{11,208}},"V"]&]

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KCyclic",{11,208}},"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[{"KCyclic",{11,208}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KCyclic",{11,208}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KCyclic",{11,208}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KCyclic",{11,208}},"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[{"KCyclic",{11,208}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"KCyclic",{11,208}},"Circulant"]

GraphData[{"KCyclic",{11,208}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"KCyclic",{11,208}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KCyclic",{11,208}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KCyclic",{11,208}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KCyclic",{11,208}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"KCyclic",{11,208}},"Line"]

LineGraphQ[GraphData[{"KCyclic",{11,208}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"KCyclic",{11,208}}&]

RootGraph[GraphData[{"KCyclic",{11,208}}]]

RecognizeGraph[%]

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

gs=LineGraph/@%

Halin

GraphData[{"KCyclic",{11,208}},"Halin"]

GraphData[{"KCyclic",{11,208}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KCyclic",{11,208}},"Rigid"]

GraphData[{"KCyclic",{11,208}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KCyclic",{11,208}},"Flexible"]

GraphData[{"KCyclic",{11,208}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KCyclic",{11,208}},"LCF"]

GraphData[{"KCyclic",{11,208}},"HamiltonianCycleCount"]

GraphData[{"KCyclic",{11,208}},"LCFSignature"]

GraphData[{"KCyclic",{11,208}},"LCFNotations"]

GraphData[{"KCyclic",{11,208}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"KCyclic",{11,208}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"KCyclic",{11,208}}],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={
{{"KCyclic",{11,208}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

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

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"KCyclic",{11,208}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"KCyclic",{11,208}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"KCyclic",{11,208}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"KCyclic",{11,208}},".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[{"KCyclic",{11,208}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KCyclic",{11,208}}],Debug->True]//Timing

GraphData[{"KCyclic",{11,208}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"KCyclic",{11,208}},"VertexList"],GraphData[{"KCyclic",{11,208}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"KCyclic",{11,208}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"KCyclic",{11,208}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"KCyclic",{11,208}},"Matchstick"]

GraphData[{"KCyclic",{11,208}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KCyclic",{11,208}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"KCyclic",{11,208}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"KCyclic",{11,208}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"KCyclic",{11,208}},"Polyhedral"]

GraphData[{"KCyclic",{11,208}},"Graph",{"3D","Polyhedron"}]

{"KCyclic",{11,210}}

Names

GraphData[{"KCyclic",{11,210}},"StandardName"]

GraphData[{"KCyclic",{11,210}},"StandardNames"]

Primary

GraphData[{"KCyclic",{11,210}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"KCyclic",{11,210}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KCyclic",{11,210}}]]

Default embedding

GraphPlot[Graph[GraphData[{"KCyclic",{11,210}},"VertexList"],GraphData[{"KCyclic",{11,210}},"Edges"]]]

RecognizeGraph@g

Degenerate

GraphData[{"KCyclic",{11,210}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"KCyclic",{11,210}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"KCyclic",{11,210}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KCyclic",{11,210}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"KCyclic",{11,210}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"KCyclic",{11,210}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"KCyclic",{11,210}},"Hamiltonian"]

GraphData[{"KCyclic",{11,210}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"KCyclic",{11,210}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"KCyclic",{11,210}}],#]&/@hc);//Timing

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

Tally[sym[[All,-1]]]

DeleteCases[sym,{_,TransformationGroup[{}]}]

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

gs=bilat

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

quad

Planar

GraphData[{"KCyclic",{11,210}},"Planar"]

GraphData[{"KCyclic",{11,210}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"KCyclic",{11,210}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"KCyclic",{11,210}}]],10]

PlanarGraphEmbeddings

GraphData[{"KCyclic",{11,210}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"KCyclic",{11,210}}],Debug->True])//Timing

Length[plemb]

MinimalCrossing

GraphData[{"KCyclic",{11,210}},{"RCN","CN"}]

GraphData[{"KCyclic",{11,210}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"KCyclic",{11,210}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KCyclic",{11,210}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KCyclic",{11,210}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KCyclic",{11,210}}],TimeConstraint->3600])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"KCyclic",{11,210}}],TimeConstraint->86400])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"KCyclic",{11,210}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"KCyclic",{11,210}},"V"]&]

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KCyclic",{11,210}},"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[{"KCyclic",{11,210}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KCyclic",{11,210}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KCyclic",{11,210}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KCyclic",{11,210}},"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[{"KCyclic",{11,210}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"KCyclic",{11,210}},"Circulant"]

GraphData[{"KCyclic",{11,210}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"KCyclic",{11,210}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KCyclic",{11,210}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KCyclic",{11,210}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KCyclic",{11,210}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

gs={,,,};

Line graph

GraphData[{"KCyclic",{11,210}},"Line"]

LineGraphQ[GraphData[{"KCyclic",{11,210}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"KCyclic",{11,210}}&]

RootGraph[GraphData[{"KCyclic",{11,210}}]]

RecognizeGraph[%]

Halin

GraphData[{"KCyclic",{11,210}},"Halin"]

GraphData[{"KCyclic",{11,210}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KCyclic",{11,210}},"Rigid"]

GraphData[{"KCyclic",{11,210}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KCyclic",{11,210}},"Flexible"]

GraphData[{"KCyclic",{11,210}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KCyclic",{11,210}},"LCF"]

GraphData[{"KCyclic",{11,210}},"HamiltonianCycleCount"]

GraphData[{"KCyclic",{11,210}},"LCFSignature"]

GraphData[{"KCyclic",{11,210}},"LCFNotations"]

GraphData[{"KCyclic",{11,210}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"KCyclic",{11,210}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KCyclic",{11,210}}],Debug->True]//Timing

GraphData[{"KCyclic",{11,210}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"KCyclic",{11,210}},"VertexList"],GraphData[{"KCyclic",{11,210}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"KCyclic",{11,210}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"KCyclic",{11,210}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"KCyclic",{11,210}},"Matchstick"]

GraphData[{"KCyclic",{11,210}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KCyclic",{11,210}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"KCyclic",{11,210}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"KCyclic",{11,210}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"KCyclic",{11,210}},"Polyhedral"]

GraphData[{"KCyclic",{11,210}},"Graph",{"3D","Polyhedron"}]

By k

3

KCyclicGraphs[3]

4

c4=KCyclicGraphs[4]

RecognizeGraph/@c4

5

GraphicsGrid[Partition[c5=KCyclicGraphs[5],5,5,{1,1},{}]]

r5=RecognizeGraph/@c5

6

GraphicsGrid[Partition[c6=KCyclicGraphs[6],5,5,{1,1},{}]]

r6=RecognizeGraph/@c6

GraphicsGrid[Partition[GraphData/@r6,5,5,{1,1},{}]]

7

GraphicsGrid[Partition[c7=KCyclicGraphs[7],5,5,{1,1},{}]]

r7=RecognizeGraph/@c7

GraphicsGrid[Partition[GraphData/@r7,5,5,{1,1},{}]]

8+

Select[RecognizeGraph[#,"Cache"->"InternalOnly","StandardName"->False]&/@Select[KCyclicGraphs[8],VertexCount[#]>7&],Quiet[Head[GraphData[#,"#"]]]===GraphData&]

Select[RecognizeGraph[#,"Cache"->"InternalOnly","StandardName"->False]&/@Select[KCyclicGraphs[9],VertexCount[#]>7&],Quiet[Head[GraphData[#,"#"]]]===GraphData&]

Sort@Select[RecognizeGraph[#,"Cache"->"InternalOnly","StandardName"->False]&/@Select[KCyclicGraphs[10],VertexCount[#]>7&],Quiet[Head[GraphData[#,"#"]]]===GraphData&]

Tally[%[[All,1]]]

Select[RecognizeGraph[#,"Cache"->"CanonicalGraph"]&/@Select[KCyclicGraphs[11],VertexCount[#]>7&],Quiet[Head[GraphData[#,"#"]]]===GraphData&]

Tally[%[[All,1]]]

Select[RecognizeGraph[#,"Cache"->"CanonicalGraph"]&/@Select[KCyclicGraphs[12],VertexCount[#]>7&],Quiet[Head[GraphData[#,"#"]]]===GraphData&]

Tally[%[[All,1]]]

k-Cyclic

Counts of connected graphs

Number of connected graphs on n nodes: 1, 1, 1, 2, 6, 21, 112, 853, 11117,

A001349

8

all8=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,8}],1]]

Length[all8]

Count[all8,{}]

9

all9=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,9}],1]]

Length[all9]

Sort@Select[Tally[GraphData[#,"V"]&/@all9],FreeQ[#,GraphData]&]//Quiet

Count[all9,{}]

10

all10=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,10}],1]]

Length[all10]

Sort@Select[Tally[GraphData[#,"V"]&/@all10],FreeQ[#,GraphData]&]//Quiet

Count[all10,{}]

12

Length[all12=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,12}],1]]]//Timing

Sort@Select[Tally[GraphData[#,"V"]&/@all12],FreeQ[#,GraphData]&]//Quiet

13

Length[all13=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,13}],1]]]//Timing

Sort@Select[Tally[GraphData[#,"V"]&/@all13],FreeQ[#,GraphData]&]//Quiet

14

Length[all14=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,14}],1]]]//Timing

Sort@Select[Tally[GraphData[#,"V"]&/@all14],FreeQ[#,GraphData]&]//Quiet

15

Length[all15=Union[Flatten[Table[RecognizeGraph/@KCyclicGraphs[n],{n,3,15}],1]]]//Timing

Sort@Select[Tally[GraphData[#,"V"]&/@all15],FreeQ[#,GraphData]&]//Quiet

16

Length[all16=Union[Flatten[Table[RecognizeGraph[#,"Cache"->"CanonicalGraph","StandardName"->False]&/@KCyclicGraphs[n],{n,3,16}],1]]]//Timing

Sort@Tally[all16[[All,1]]]

17

Length[all17=Union[Flatten[Table[RecognizeGraph[#,"Cache"->"CanonicalGraph","StandardName"->False]&/@KCyclicGraphs[n],{n,17}],1]]]//Timing

Sort@Tally[all17[[All,1]]]

con6=Sort[Cases[GraphData[#,"StandardNames"],{6,_}][[1]]&/@GraphData["Connected",6]]

Complement[con6,Cases[all17,{6,_}]]

GraphData[{6,156},"#"]

GraphData

Existing

Length/@(gs=Table[KCyclicGraphs[n],{n,17}])//Timing

data=Sort@DeleteCases[
Flatten[
Monitor[MapIndexed[{RecognizeGraph[gn=#,"Cache"->"InternalOnly"],{"KCyclic",#2}}&,gs,{2}],gn],
1
],
{{},_}
];//Timing

Length[data]

AlternateStandardNames

Length[l={#[[1,1]],{0,SortBy[Union[DeleteCases[GraphData[#[[1,1]],"AlternateStandardNames"],{"KCyclic",_}],Complement[#[[All,2]],{#[[1,1]]}]],Function[f,First[Flatten[{f}]]]]}}&/@SplitBy[data,First]]

l2=Select[l,#[[2,2]]=!=GraphData[#[[1]],"AlternateStandardNames"]&]

PropertyReplace[l2,"AlternateStandardNames",Select[$Subdirs,ToExpression[#]>=13.3&]]

RenameGraphFiles[]

KCyclicIndices

l={#[[1,1]],{0,#[[All,2]][[All,2]]}}&/@SplitBy[data,First];

GraphData[{"KCyclic",{9,56}},"KCyclicIndices"]

l2=Select[l,#[[2,2]]=!=GraphData[#[[1]],"KCyclicIndices"]&]

PropertyReplace[l2,"KCyclicIndices",Select[$Subdirs,ToExpression[#]>=13.3&]]

RenameGraphFiles[]

Add up to (Subscript[C, 10])-cyclic

Length[gs=Table[KCyclicGraphs[n],{n,10}]]

Cases[Flatten[MapIndexed[{#,RecognizeGraph[#,"Cache"->"InternalOnly"],{"KCyclic",#2}}&,gs,{2}],1],{_,{},_}]

Add up to (Subscript[C, 11])-cyclic

Length[gs=Table[KCyclicGraphs[n],{n,11}]]

new=SortBy[{#[[1,1]],#[[All,-1]]}&/@SplitBy[SortBy[Cases[Flatten[MapIndexed[{CanonicalGraph@#,RecognizeGraph[#,"Cache"->"InternalOnly"],{"KCyclic",#2}}&,gs,{2}],1],{_,{},_}],First],First],#[[2,1]]&]

Put[new,"~/graphs.m"]

Tally[VertexCount/@new[[All,1]]]//Sort

Add

Length[new=Get["~/graphs.m"]]

RecognizeGraph[LineGraph[new[[43,1]]]]//Timing

file=OpenAppend["~/kcyclic.m"]

p=FirstPosition[new[[All,2]],{"KCyclic",{11,252}},{0}][[1]]

WriteString[file,GraphDataString[#,
"StandardName"->First[#2],
"AlternateStandardNames"->Rest[#2],
"Name"->ToString[#2[[1,2,1]]]<>"\[Hyphen]cyclic graph "<>ToString[#2[[1,2,2]]],
"KCyclicIndices"->#2[[All,2]],
Debug->True,
TimeConstraint->60,
"Skip"->{"DistinguishingNumber"}
]]&@@@Drop[new,p]

Close[file]