Cyclotomic Graph

Author

Eric W. Weisstein
January 16, 2024

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

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

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

Code

CubicResidues[n_]:={n,#}&/@Table[Select[Union@Mod[k Range[n]^3,n],(GCD[#,n]==1&&#<n/2&)],{k,n/2}]//Union

Definition

van Dam, E.~R.  "Graphs with Few Eigenvalues: An Interplay Between Combinatorics and Algebra."  Ph.D. dissertation.  Tilburg, Netherlands: Tilburg University, pp. 51–52, October 4, 1996.

https://web.archive.org/web/20061002160924/http://cage.rug.ac.be/geometry/Theses/30/evandam.pdf

Table

indices=Select[Range[100],Mod[#,3]==1&&PrimePowerQ[#]&]

RecognizeGraph/@CyclotomicGraph/@indices

TextGrid[{#,RecognizeGraph[CyclotomicGraph[#]]}&/@indices,Dividers->All]

Graphics

cyclotomic=SortBy[GraphData["Cyclotomic"],GraphData[#,"V"]&]

GraphicsGrid[Partition[Show[StyleGraphs@GraphData[#],PlotLabel->TextCell[Style[ToString[GraphData[#,"NotationRules","Cyclotomic"]]<>"-cyclotomic graph"<>If[MatchQ[#,{"Cyclotomic",_}],"","\n"<>GraphData[#,"Name"]],Directive[Black,Italic,FontFamily->"Times"]],PageWidth->150,TextAlignment->Center]]&/@cyclotomic,UpTo[5]],ImageSize->700,Alignment->Top,Dividers->All]

Enumeration

http://cage.rug.ac.be/geometry/Theses/30/evandam.pdf

l=Select[Range[100],PrimePowerQ[#]&&Mod[#,3]==1&]

{#,RecognizeGraph[CyclotomicGraph[#]]}&/@l

Print[{#,CirculantIndices[CyclotomicGraph[#]]}]&/@l

CirculantGraphQ[CyclotomicGraph[49]]

Print[{#,CubicResidues[#]}]&/@l

Embeddings

<<MathWorld`Graphs`

GraphData["Cyclotomic"]

{"Cyclotomic", 13}

Names

GraphData[{"Cyclotomic",13},"StandardName"]

GraphData[{"Cyclotomic",13},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Cyclotomic",13},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cyclotomic",13},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

GraphData[{"Cyclotomic",13},"Planar"]

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

MinimalCrossing

GraphData[{"Cyclotomic",13},{"RCN","CN"}]

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

MinimalCrossing construction

CrossingNumber[GraphData[{"Cyclotomic",13}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",13}],TimeConstraint->60]//AbsoluteTiming

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

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

GraphPlot@

g0=CenterGraph@GraphicsToGraph@

v=10Take[GraphEmbedding@g0,13]

Round[v]

v={{-1-1/4,3},{0,10},{1+1/4,3},{1+1/4,0},{1+1/4,-2},{-9,-6},{-3,-2},{-1,1},{1,1},{4,-2},{9,-6},{-1-1/4,-2},{-1-1/4,0}};

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

RecognizeGraph@g

RectilinearCrossingCount@g

GraphPlot@RotateGraph[,Pi/5]

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

RecognizeGraph@g

GraphPlot[MinimalCrossingGraph[GraphData[{"Cyclotomic",13}],"CrossingNumber"->7]]

Rotate[,2.07]

GraphPlot@HighlightGraph[RotateGraph[,2.07],{14,15,16,20,19,17,18}]

e[l__]:=Sequence@@Partition[{l},2,1]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

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

Circulant construction

GraphData[{"Cyclotomic",13},"NotationRules","Circulant"]

CubicResidues[13]

(ci=CirculantIndices[GraphData[{"Cyclotomic",13}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Cyclotomic",13},"StandardNames"],{"Circulant",i_}:>i]

gs=CirculantGraph1@@@%

Halin

GraphData[{"Cyclotomic",13},"Halin"]

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

LCF

GraphData[{"Cyclotomic",13},"LCF"]

GraphData[{"Cyclotomic",13},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",13},"LCFSignature"]

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

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

LCF compute

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

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

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]}]

UnitDistance

GraphData[{"Cyclotomic",13},"UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cyclotomic",13},"VertexList"],GraphData[{"Cyclotomic",13},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

{{"Cyclotomic",13},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Cyclotomic",13}],Debug->Full,TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Cyclotomic",13},"Matchstick"]

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

Default embedding

GraphPlot@GraphData[{"Cyclotomic",13},"Edges"]

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

RecognizeGraph[g]

3D default

Graph3D[GraphData[{"Cyclotomic",13},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Cyclotomic",13},"Polyhedral"]

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

{"Cyclotomic", 19}

Names

GraphData[{"Cyclotomic",19},"StandardName"]

GraphData[{"Cyclotomic",19},"StandardNames"]

Primary

GraphData[{"Cyclotomic",19}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cyclotomic",19},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Cyclotomic",19},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cyclotomic",19},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cyclotomic",19},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Cyclotomic",19},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cyclotomic",19},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cyclotomic",19},"Planar"]

GraphData[{"Cyclotomic",19},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cyclotomic",19},{"RCN","CN"}]

GraphData[{"Cyclotomic",19},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

(cn=CrossingNumber[GraphData[{"Cyclotomic",19}],TimeConstraint->300])//AbsoluteTiming

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

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

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

Table[MinimalCrossingGraph[GraphData[{"Cyclotomic",19}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cyclotomic",19},"Circulant"]

GraphData[{"Cyclotomic",19},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Cyclotomic",19},"NotationRules","Circulant"]

CubicResidues[19]

(ci=CirculantIndices[GraphData[{"Cyclotomic",19}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Cyclotomic",19},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Cyclotomic",19},"Halin"]

GraphData[{"Cyclotomic",19},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cyclotomic",19},"Rigid"]

GraphData[{"Cyclotomic",19},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cyclotomic",19},"Flexible"]

GraphData[{"Cyclotomic",19},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",19},"LCF"]

GraphData[{"Cyclotomic",19},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",19},"LCFSignature"]

GraphData[{"Cyclotomic",19},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Cyclotomic",19}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cyclotomic",19}],All])[[All,2]]]//Timing

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

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]}]

Length[gs]

Length[order1=Cases[lcf,{_,1}]]

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

≥20 bilateral graphs

UnitDistance

GraphData[{"Cyclotomic",19},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cyclotomic",19}],Debug->True]//Timing

GraphData[{"Cyclotomic",19},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cyclotomic",19},"VertexList"],GraphData[{"Cyclotomic",19},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Cyclotomic",19},"Matchstick"]

GraphData[{"Cyclotomic",19},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",19},"Edges"]]

3D All

GraphData[{"Cyclotomic",19},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",19},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",19},"Polyhedral"]

GraphData[{"Cyclotomic",19},"Graph",{"3D","Polyhedron"}]

{"Cyclotomic", 31}

Names

GraphData[{"Cyclotomic",31},"StandardName"]

GraphData[{"Cyclotomic",31},"StandardNames"]

Default

GraphData[{"Cyclotomic",31}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cyclotomic",31},"Graph","All"]//StyleGraphs

Circulant

(i=CirculantIndices[g=Graph[{"Cyclotomic",31}],All])/Timing

CubicResidues[31]

i=With[{n=31},{n,#}&/@Table[Select[Union@Mod[k Range[n]^3,n],(GCD[#,n]==1&&#<n/2&)],{k,n/2}]]//Union

GraphData[{"Cyclotomic",31},"Graph","Circulant"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Cyclotomic",31},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cyclotomic",31},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cyclotomic",31},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Cyclotomic",31},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cyclotomic",31},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cyclotomic",31},"Planar"]

GraphData[{"Cyclotomic",31},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cyclotomic",31},{"RCN","CN"}]

GraphData[{"Cyclotomic",31},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

CrossingNumber[GraphData[{"Cyclotomic",31}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",31}],TimeConstraint->60]//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Cyclotomic",31}],TimeConstraint->300])//AbsoluteTiming

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

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

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

Table[MinimalCrossingGraph[GraphData[{"Cyclotomic",31}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cyclotomic",31},"Circulant"]

GraphData[{"Cyclotomic",31},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Cyclotomic",31},"NotationRules","Circulant"]

CubicResidues[31]

(ci=CirculantIndices[GraphData[{"Cyclotomic",31}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Cyclotomic",31},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Cyclotomic",31},"Halin"]

GraphData[{"Cyclotomic",31},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cyclotomic",31},"Rigid"]

GraphData[{"Cyclotomic",31},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cyclotomic",31},"Flexible"]

GraphData[{"Cyclotomic",31},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",31},"LCF"]

GraphData[{"Cyclotomic",31},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",31},"LCFSignature"]

GraphData[{"Cyclotomic",31},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Cyclotomic",31}],All][[All,All,1]]]//Timing

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

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Cyclotomic",31},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cyclotomic",31}],Debug->True]//Timing

GraphData[{"Cyclotomic",31},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Cyclotomic",31},"Matchstick"]

GraphData[{"Cyclotomic",31},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",31},"Edges"]]

3D All

GraphData[{"Cyclotomic",31},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",31},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",31},"Polyhedral"]

GraphData[{"Cyclotomic",31},"Graph",{"3D","Polyhedron"}]

{"Cyclotomic", 37}

Names

GraphData[{"Cyclotomic",37},"StandardName"]

GraphData[{"Cyclotomic",37},"StandardNames"]

Primary

GraphData[{"Cyclotomic",37}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cyclotomic",37},"Graph","All"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Cyclotomic",37},"Edges"]

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

RecognizeGraph[g]

Circulant

GraphData[{"Cyclotomic",37},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Cyclotomic",37},"NotationRules","Circulant"]

CubicResidues[37]

(ci=CirculantIndices[GraphData[{"Cyclotomic",37}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Cyclotomic",37},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

MinimalCrossing

GraphData[{"Cyclotomic",37},{"RCN","CN"}]

GraphData[{"Cyclotomic",37},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

CrossingNumber[GraphData[{"Cyclotomic",37}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",37}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",37}],TimeConstraint->3600]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",37}],TimeConstraint->5 3600]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Cyclotomic",37}],"CrossingNumber"->-1]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Halin

GraphData[{"Cyclotomic",37},"Halin"]

GraphData[{"Cyclotomic",37},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",37},"LCF"]

GraphData[{"Cyclotomic",37},"LCFSignature"]

GraphData[{"Cyclotomic",37},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cyclotomic",37},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cyclotomic",37}],Debug->True]//Timing

GraphData[{"Cyclotomic",37},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Cyclotomic",37},"Matchstick"]

GraphData[{"Cyclotomic",37},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",37},"Edges"]]

3D All

GraphData[{"Cyclotomic",37},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",37},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",37},"Polyhedral"]

GraphData[{"Cyclotomic",37},"Graph",{"3D","Polyhedron"}]

{"Cyclotomic", 43}

Names

GraphData[{"Cyclotomic",43},"StandardName"]

GraphData[{"Cyclotomic",43},"StandardNames"]

Primary

GraphData[{"Cyclotomic",43}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cyclotomic",43},"Graph","All"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Cyclotomic",43},"Edges"]

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

RecognizeGraph[g]

Circulant

GraphData[{"Cyclotomic",43},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Cyclotomic",43},"NotationRules","Circulant"]

CubicResidues[43]

(ci=CirculantIndices[GraphData[{"Cyclotomic",43}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Cyclotomic",43},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

MinimalCrossing

GraphData[{"Cyclotomic",43},{"RCN","CN"}]

GraphData[{"Cyclotomic",43},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

CrossingNumber[GraphData[{"Cyclotomic",43}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",43}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",43}],TimeConstraint->3600]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",43}],TimeConstraint->5 3600]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Cyclotomic",43}],"CrossingNumber"->-1]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Halin

GraphData[{"Cyclotomic",43},"Halin"]

GraphData[{"Cyclotomic",43},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",43},"LCF"]

GraphData[{"Cyclotomic",43},"LCFSignature"]

GraphData[{"Cyclotomic",43},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Cyclotomic",43},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cyclotomic",43}],Debug->True]//Timing

Matchstick

GraphData[{"Cyclotomic",43},"Matchstick"]

GraphData[{"Cyclotomic",43},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",43},"Edges"]]

3D All

GraphData[{"Cyclotomic",43},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",43},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",43},"Polyhedral"]

GraphData[{"Cyclotomic",43},"Graph",{"3D","Polyhedron"}]

{"Cyclotomic", 49}

Names

GraphData[{"Cyclotomic",49},"StandardName"]

GraphData[{"Cyclotomic",49},"StandardNames"]

Primary

GraphData[{"Cyclotomic",49}]//StyleGraphs[#,ImageSize->Small]&

Configuration

GraphData[{"Cyclotomic",49},"Graph","Configuration"]//StyleGraphs

All

GraphData[{"Cyclotomic",49},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Cyclotomic",49},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cyclotomic",49},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cyclotomic",49},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cyclotomic",49},"Graph","Degenerate"]

Perspective

GraphData[{"Cyclotomic",49},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Cyclotomic",49},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cyclotomic",49},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Cyclotomic",49}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Cyclotomic",49}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

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

quad

Planar

GraphData[{"Cyclotomic",49},"Planar"]

GraphData[{"Cyclotomic",49},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cyclotomic",49},{"RCN","CN"}]

GraphData[{"Cyclotomic",49},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Cyclotomic",49}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cyclotomic",49},"Circulant"]

GraphData[{"Cyclotomic",49},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"Cyclotomic",49},"ComplementGraph","Name"]

Line graph

GraphData[{"Cyclotomic",49},"Line"]

LineGraphQ[GraphData[{"Cyclotomic",49}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cyclotomic",49}&]

RootGraph[GraphData[{"Cyclotomic",49}]]

Halin

GraphData[{"Cyclotomic",49},"Halin"]

GraphData[{"Cyclotomic",49},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cyclotomic",49},"Rigid"]

GraphData[{"Cyclotomic",49},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cyclotomic",49},"Flexible"]

GraphData[{"Cyclotomic",49},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",49},"LCF"]

GraphData[{"Cyclotomic",49},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",49},"LCFSignature"]

GraphData[{"Cyclotomic",49},"LCFNotations"]

GraphData[{"Cyclotomic",49},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Cyclotomic",49}],TimeConstraint->120]

LCF compute 10^4

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^7

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Cyclotomic",49},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cyclotomic",49}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cyclotomic",49}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

UnitDistanceGraphQ[GraphData[{"Cyclotomic",49}],Debug->True]//Timing

GraphData[{"Cyclotomic",49},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Cyclotomic",49},"VertexList"],GraphData[{"Cyclotomic",49},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Cyclotomic",49},"Matchstick"]

GraphData[{"Cyclotomic",49},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",49},"Edges"]]

3D All

GraphData[{"Cyclotomic",49},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",49},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",49},"Polyhedral"]

GraphData[{"Cyclotomic",49},"Graph",{"3D","Polyhedron"}]

{"Cyclotomic", 61}

Names

GraphData[{"Cyclotomic",61},"StandardName"]

GraphData[{"Cyclotomic",61},"StandardNames"]

Primary

GraphData[{"Cyclotomic",61}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cyclotomic",61},"Graph","All"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Cyclotomic",61},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"Cyclotomic",61},{"RCN","CN"}]

GraphData[{"Cyclotomic",61},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

CrossingNumber[GraphData[{"Cyclotomic",61}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",61}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",61}],TimeConstraint->3600]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",61}],TimeConstraint->5 3600]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Cyclotomic",61}],"CrossingNumber"->-1]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

i=With[{n=61},{"Circulant",{n,#}}&/@Table[Select[Union@Mod[k Range[n]^3,n],(GCD[#,n]==1&&#<n/2&)],{k,n/2}]]//Union

GraphData[{"Cyclotomic",61},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Cyclotomic",61},"NotationRules","Circulant"]

CubicResidues[61]

(ci=CirculantIndices[GraphData[{"Cyclotomic",61}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Cyclotomic",61},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Cyclotomic",61},"Halin"]

GraphData[{"Cyclotomic",61},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",61},"LCF"]

GraphData[{"Cyclotomic",61},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",61},"LCFSignature"]

GraphData[{"Cyclotomic",61},"LCFNotations"]

GraphData[{"Cyclotomic",61},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Cyclotomic",61}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Cyclotomic",61},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Cyclotomic",61}],Debug->True]//Timing

GraphData[{"Cyclotomic",61},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Cyclotomic",61},"Matchstick"]

GraphData[{"Cyclotomic",61},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",61},"Edges"]]

3D All

GraphData[{"Cyclotomic",61},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",61},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",61},"Polyhedral"]

GraphData[{"Cyclotomic",61},"Graph",{"3D","Polyhedron"}]

{"Cyclotomic", 64}

Names

GraphData[{"Cyclotomic",64},"StandardName"]

GraphData[{"Cyclotomic",64},"StandardNames"]

Primary

GraphData[{"Cyclotomic",64}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cyclotomic",64},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Cyclotomic",64},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Cyclotomic",64},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Cyclotomic",64},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Cyclotomic",64},"Graph","Degenerate"]

Perspective

GraphData[{"Cyclotomic",64},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Cyclotomic",64},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Cyclotomic",64},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Cyclotomic",64},"Planar"]

GraphData[{"Cyclotomic",64},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Cyclotomic",64},{"RCN","CN"}]

GraphData[{"Cyclotomic",64},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Cyclotomic",64}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cyclotomic",64},"Circulant"]

GraphData[{"Cyclotomic",64},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"Cyclotomic",64},"ComplementGraph","Name"]

Line graph

GraphData[{"Cyclotomic",64},"Line"]

LineGraphQ[GraphData[{"Cyclotomic",64}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Cyclotomic",64}&]

RootGraph[GraphData[{"Cyclotomic",64}]]

Halin

GraphData[{"Cyclotomic",64},"Halin"]

GraphData[{"Cyclotomic",64},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Cyclotomic",64},"Rigid"]

GraphData[{"Cyclotomic",64},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Cyclotomic",64},"Flexible"]

GraphData[{"Cyclotomic",64},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",64},"LCF"]

GraphData[{"Cyclotomic",64},"LCF"]

GraphData[{"Cyclotomic",64},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",64},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",64},"LCFSignature"]

GraphData[{"Cyclotomic",64},"LCFSignature"]

GraphData[{"Cyclotomic",64},"LCFNotations"]

GraphData[{"Cyclotomic",64},"LCFNotations"]

GraphData[{"Cyclotomic",64},"Graph","LCF"]//StyleGraphs

GraphData[{"Cyclotomic",64},"Graph","LCF"]

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Cyclotomic",64}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Cyclotomic",64},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cyclotomic",64}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cyclotomic",64}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

UnitDistanceGraphQ[GraphData[{"Cyclotomic",64}],Debug->True]//Timing

GraphData[{"Cyclotomic",64},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Cyclotomic",64},"Matchstick"]

GraphData[{"Cyclotomic",64},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",64},"Edges"]]

3D All

GraphData[{"Cyclotomic",64},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",64},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",64},"Polyhedral"]

GraphData[{"Cyclotomic",64},"Graph",{"3D","Polyhedron"}]

{"Cyclotomic", 67}

Names

GraphData[{"Cyclotomic",67},"StandardName"]

GraphData[{"Cyclotomic",67},"StandardNames"]

Primary

GraphData[{"Cyclotomic",67}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cyclotomic",67},"Graph","All"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Cyclotomic",67},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"Cyclotomic",67},{"RCN","CN"}]

GraphData[{"Cyclotomic",67},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

CrossingNumber[GraphData[{"Cyclotomic",67}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",67}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",67}],TimeConstraint->3600]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",67}],TimeConstraint->5 3600]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Cyclotomic",67}],"CrossingNumber"->-1]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Cyclotomic",67},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Cyclotomic",67},"NotationRules","Circulant"]

CubicResidues[67]

(ci=CirculantIndices[GraphData[{"Cyclotomic",67}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Cyclotomic",67},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Cyclotomic",67},"Halin"]

GraphData[{"Cyclotomic",67},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",67},"LCF"]

GraphData[{"Cyclotomic",67},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",67},"LCFSignature"]

GraphData[{"Cyclotomic",67},"LCFNotations"]

GraphData[{"Cyclotomic",67},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Cyclotomic",67}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Cyclotomic",67},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cyclotomic",67}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cyclotomic",67}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

UnitDistanceGraphQ[GraphData[{"Cyclotomic",67}],Debug->True]//Timing

GraphData[{"Cyclotomic",67},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Cyclotomic",67},"Matchstick"]

GraphData[{"Cyclotomic",67},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",67},"Edges"]]

3D All

GraphData[{"Cyclotomic",67},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",67},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",67},"Polyhedral"]

GraphData[{"Cyclotomic",67},"Graph",{"3D","Polyhedron"}]

{"Cyclotomic", 73}

Names

GraphData[{"Cyclotomic",73},"StandardName"]

GraphData[{"Cyclotomic",73},"StandardNames"]

Primary

GraphData[{"Cyclotomic",73}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cyclotomic",73},"Graph","All"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Cyclotomic",73},"Edges"]

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

RecognizeGraph[g]

Circulant

GraphData[{"Cyclotomic",73},"Circulant"]

GraphData[{"Cyclotomic",73},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Cyclotomic",73},"NotationRules","Circulant"]

CubicResidues[73]

(ci=CirculantIndices[GraphData[{"Cyclotomic",73}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Cyclotomic",73},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

MinimalCrossing

GraphData[{"Cyclotomic",73},{"RCN","CN"}]

GraphData[{"Cyclotomic",73},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

CrossingNumber[GraphData[{"Cyclotomic",73}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",73}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",73}],TimeConstraint->3600]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",73}],TimeConstraint->5 3600]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Cyclotomic",73}],"CrossingNumber"->-1]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Halin

GraphData[{"Cyclotomic",73},"Halin"]

GraphData[{"Cyclotomic",73},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",73},"LCF"]

GraphData[{"Cyclotomic",73},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",73},"LCFSignature"]

GraphData[{"Cyclotomic",73},"LCFNotations"]

GraphData[{"Cyclotomic",73},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Cyclotomic",73}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Cyclotomic",73},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cyclotomic",73}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cyclotomic",73}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

UnitDistanceGraphQ[GraphData[{"Cyclotomic",73}],Debug->True]//Timing

GraphData[{"Cyclotomic",73},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Cyclotomic",73},"Matchstick"]

GraphData[{"Cyclotomic",73},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",73},"Edges"]]

3D All

GraphData[{"Cyclotomic",73},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",73},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",73},"Polyhedral"]

GraphData[{"Cyclotomic",73},"Graph",{"3D","Polyhedron"}]

{"Cyclotomic", 79}

Names

GraphData[{"Cyclotomic",79},"StandardName"]

GraphData[{"Cyclotomic",79},"StandardNames"]

Primary

GraphData[{"Cyclotomic",79}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cyclotomic",79},"Graph","All"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Cyclotomic",79},"Edges"]

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

RecognizeGraph[g]

Circulant

GraphData[{"Cyclotomic",79},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Cyclotomic",79},"NotationRules","Circulant"]

CubicResidues[79]

(ci=CirculantIndices[GraphData[{"Cyclotomic",79}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Cyclotomic",79},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

MinimalCrossing

GraphData[{"Cyclotomic",79},{"RCN","CN"}]

GraphData[{"Cyclotomic",79},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

CrossingNumber[GraphData[{"Cyclotomic",79}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",79}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",79}],TimeConstraint->3600]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",79}],TimeConstraint->5 3600]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Cyclotomic",79}],"CrossingNumber"->-1]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Halin

GraphData[{"Cyclotomic",79},"Halin"]

GraphData[{"Cyclotomic",79},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",79},"LCF"]

GraphData[{"Cyclotomic",79},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",79},"LCFSignature"]

GraphData[{"Cyclotomic",79},"LCFNotations"]

GraphData[{"Cyclotomic",79},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Cyclotomic",79}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Cyclotomic",79}],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[{"Cyclotomic",79}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Cyclotomic",79},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cyclotomic",79}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cyclotomic",79}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

UnitDistanceGraphQ[GraphData[{"Cyclotomic",79}],Debug->True]//Timing

GraphData[{"Cyclotomic",79},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Cyclotomic",79},"Matchstick"]

GraphData[{"Cyclotomic",79},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",79},"Edges"]]

3D All

GraphData[{"Cyclotomic",79},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",79},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",79},"Polyhedral"]

GraphData[{"Cyclotomic",79},"Graph",{"3D","Polyhedron"}]

{"Cyclotomic", 97}

Names

GraphData[{"Cyclotomic",97},"StandardName"]

GraphData[{"Cyclotomic",97},"StandardNames"]

Primay

GraphData[{"Cyclotomic",97}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Cyclotomic",97},"Graph","All"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Cyclotomic",97},"Edges"]

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

RecognizeGraph[g]

Circulant

GraphData[{"Cyclotomic",97},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"Cyclotomic",97},"NotationRules","Circulant"]

CubicResidues[97]

(ci=CirculantIndices[GraphData[{"Cyclotomic",97}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Cyclotomic",97},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

MinimalCrossing

GraphData[{"Cyclotomic",97},{"RCN","CN"}]

GraphData[{"Cyclotomic",97},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

CrossingNumber[GraphData[{"Cyclotomic",97}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",97}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",97}],TimeConstraint->3600]//AbsoluteTiming

CrossingNumber[GraphData[{"Cyclotomic",97}],TimeConstraint->5 3600]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Cyclotomic",97}],"CrossingNumber"->-1]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Halin

GraphData[{"Cyclotomic",97},"Halin"]

GraphData[{"Cyclotomic",97},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Cyclotomic",97},"LCF"]

GraphData[{"Cyclotomic",97},"HamiltonianCycleCount"]

GraphData[{"Cyclotomic",97},"LCFSignature"]

GraphData[{"Cyclotomic",97},"LCFNotations"]

GraphData[{"Cyclotomic",97},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Cyclotomic",97}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Cyclotomic",97},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Cyclotomic",97}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Cyclotomic",97}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

UnitDistanceGraphQ[GraphData[{"Cyclotomic",97}],Debug->True]//Timing

GraphData[{"Cyclotomic",97},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Cyclotomic",97},"Matchstick"]

GraphData[{"Cyclotomic",97},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Cyclotomic",97},"Edges"]]

3D All

GraphData[{"Cyclotomic",97},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cyclotomic",97},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Cyclotomic",97},"Polyhedral"]

GraphData[{"Cyclotomic",97},"Graph",{"3D","Polyhedron"}]

Code

Quit

7

v=Table[FiniteField[7][i],{i,0,6}]

cubes=v^3//Union

edges=Select[Subsets[v,{2}],MemberQ[cubes,Subtract@@#]&]

IndexGraph@Graph[v,UndirectedEdge@@@edges]

RecognizeGraph[%]

13

v=Table[FiniteField[13][i],{i,0,12}]

cubes=v^3//Union

edges=Select[Subsets[v,{2}],MemberQ[cubes,Subtract@@#]&];//Timing

IndexGraph@Graph[v,UndirectedEdge@@@edges]

RecognizeGraph[%]

16

v=Table[FiniteField[16][i],{i,0,15}]

cubes=v^3//Union

edges=Select[Subsets[v,{2}],MemberQ[cubes,Subtract@@#]&];//Timing

IndexGraph@Graph[v,UndirectedEdge@@@edges]

RecognizeGraph[%]

19

v=Table[FiniteField[19][i],{i,0,18}]

cubes=v^3//Union

edges=Select[Subsets[v,{2}],MemberQ[cubes,Subtract@@#]&];//Timing

IndexGraph@Graph[v,UndirectedEdge@@@edges]

RecognizeGraph[%]

GraphData

GraphClassString

GraphClassString[GraphData["Cyclotomic"]]

GraphDataString

file=OpenWrite["cycl.m"]

WriteString[file,GraphDataString[CyclotomicGraph[#],
"Name"->ToString[#]<>"-cyclotomic graph",
"AlternateNames"->If[PrimeQ[#],ToString[#]<>"-circulant graph (",StringReplace[StringTake[ToString[CubicResidues[#]],{2,-2}]," "->""]<>")",{}],
"StandardName"->{"Cyclotomic",#},
"AlternateStandardNames"->If[PrimeQ[#],{"Circulant",{#,CubicResidues[#]}},{}],
"Information"->"CyclotomicGraph",
"NotationRules"->{"Cyclotomic"->#},
"Classes"->{"Cyclotomic",If[PrimeQ[#],"Circulant",Sequence@@{}]},
"Vertices"->None,
"Skip"->{"Perfect"},
TimeConstraint->60,
Debug->True
]]&/@{31,37,43,49,61,64,67,73,79,97};

Close[file]