Cyclic Group Graph

Author

Eric W. Weisstein
January 21, 2025

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

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

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

Figures

C3

SortBy[Cases[sorted,{3,9,gn_}:>gn],GraphData[#,"EdgeCount"]&]

GraphicsRow[StyleGraphs[GraphData[#],PlotLabel->Style[Row[{Style["V",Italic]," == 9, ",Style["E",Italic]," == "<>ToString[GraphData[#,"M"]]<>", |Aut| == 3"}],Directive[Black,FontFamily->"Times",14]]]&/@Table[{"C3GroupGraph",{9,i}},{i,4}],Alignment->Top,Dividers->All,ImageSize->700]

C4

C4GroupGraphs=Table[{"C4GroupGraph",{10,i}},{i,12}]

GraphicsGrid[Partition[StyleGraphs[GraphData[#],PlotLabel->Style[Row[{Style["V",Italic]," == 10, ",Style["E",Italic]," == "<>ToString[GraphData[#,"M"]]<>", |Aut| == 4"}],Directive[Black,FontFamily->"Times",14]]]&/@C4GroupGraphs,UpTo[4]],Alignment->Top,Dividers->All,ImageSize->700]

Cyclic group recognition

{g1,g2}={,};

IsomorphicGraphQ[g1,g2]

CyclicPermutationGroupQ[GraphAutomorphismGroup[#]]&/@{g1,g2}

CyclicPermutationGroupQ[GraphAutomorphismGroup[#]]&/@{,,}

Graphs with cyclic automorphism groups

All graphs up to 9 nodes

Do[Graphs[n],{n,9}];

Do[Print[{n,Select[Graphs[n],CyclicGroupGraphQ]//Timing}],{n,9}]

RecognizeGraph/@{,,,}

GraphData ;; 100, "MaxGroupOrder" -> 10^6

data=Monitor[{gn=#,Sequence@@Timing[CyclicGroupGraphQ[GraphData[gn=#]]]}&/@GraphData[;;100],gn];//Timing

Cases[data,{gn_,_,$Failed}:>gn]

TextGrid[Take[ReverseSortBy[data,#[[2]]&],10],Dividers->All]

sorted=Sort[GraphData[#,{"|Aut|","V","#"}]&/@Cases[data,{gn_,_,True}:>gn]]

TextGrid[sorted,Dividers->All,Alignment->{{{Decimal},Left}}]

GraphData ;; 250, "MaxGroupOrder" -> 10^6

data=Monitor[{gn=#,Sequence@@Timing[CyclicGroupGraphQ[GraphData[gn=#]]]}&/@GraphData[;;250],gn];//Timing

Cases[data,{gn_,_,$Failed}:>gn]

TextGrid[Take[ReverseSortBy[data,#[[2]]&],10],Dividers->All]

sorted=Sort[GraphData[#,{"|Aut|","V","#"}]&/@Cases[data,{gn_,_,True}:>gn]]

TextGrid[sorted,Dividers->All,Alignment->{{{Decimal},Left}}]

GraphData 251 ;; 500, "MaxGroupOrder" -> 10^6

<<MathWorld`Graphs`

data=Monitor[{gn=#,Sequence@@Timing[CyclicGroupGraphQ[GraphData[gn=#]]]}&/@GraphData[251;;500],gn];//Timing

Cases[data,{gn_,_,$Failed}:>gn]

TextGrid[Take[ReverseSortBy[data,#[[2]]&],10],Dividers->All]

sorted=Sort[GraphData[#,{"|Aut|","V","#"}]&/@Cases[data,{gn_,_,True}:>gn]]

TextGrid[sorted,Dividers->All,Alignment->{{{Decimal},Left}}]

GraphData 501 ;; 750, "MaxGroupOrder" -> 10^6

<<MathWorld`Graphs`

data=Monitor[{gn=#,Sequence@@Timing[CyclicGroupGraphQ[GraphData[gn=#]]]}&/@SortBy[GraphData[501;;750],GraphData[#,"V"]&],gn];//Timing

Cases[data,{gn_,_,$Failed}:>gn]

TextGrid[Take[ReverseSortBy[data,#[[2]]&],10],Dividers->All]

sorted=Sort[GraphData[#,{"|Aut|","V","#"}]&/@Cases[data,{gn_,_,True}:>gn]]

TextGrid[sorted,Dividers->All,Alignment->{{{Decimal},Left}}]

|Aut| < (10^4) and < 500 nodes

GroupElements[GraphAutomorphismGroup[GraphData["DeGreyGraph"]]] takes 32+ GB and crashes due to using 80+ GB before MemoryConstraint kicks in

Asked Jose 2025-01-22

MemoryConstrained on 2048-vertex [{"CubeConnectedCycle",8}, 30 GB] crashes after loading MathWorld

todo=Cases[GraphData[#,{"|Aut|","#"}]&/@GraphData[;;500],{_?(LessThan[10^4]),gn_}:>gn]

data=Monitor[{gn=#,Check[GraphData[#,"CyclicGroup"],Print[#]],Sequence@@Timing[MemoryConstrained[CyclicGroupGraphQ[GraphData[gn=#]],20*^9]]}&/@todo,gn];//Timing

Cases[data,{gn_,_,_,_?FailureQ}:>gn]

DeleteCases[data,{_,x_,_,x_}]

|Aut| < (10^5) and < 750 nodes

See bug(456585)

MemoryConstrained on 2048-vertex [{"CubeConnectedCycle",8}, 30 GB] crashes after loading MathWorld

Length[todo=Cases[GraphData[#,{"|Aut|","#"}]&/@GraphData[;;750],{_?(LessThan[10^5]),gn_}:>gn]]

data=Monitor[{gn=#,Check[GraphData[#,"CyclicGroup"],Print[#]],Sequence@@Timing[MemoryConstrained[CyclicGroupGraphQ[GraphData[gn=#]],20*^9]]}&/@todo,gn];//Timing

Cases[data,{gn_,_,_,_?FailureQ}:>gn]

DeleteCases[data,{_,x_,_,x_}]

|Aut| < (10^5) and 750 ≤ nodes < 1000

See bug(456585)

Length[todo=Cases[GraphData[#,{"|Aut|","#"}]&/@GraphData[750;;1000],{_?(LessThan[10^5]),gn_}:>gn]]

data=Monitor[{gn=#,Check[GraphData[#,"CyclicGroup"],Print[#]],Sequence@@Timing[MemoryConstrained[CyclicGroupGraphQ[GraphData[gn=#]],20*^9]]}&/@todo,gn];//Timing

Cases[data,{gn_,_,_,_?FailureQ}:>gn]

DeleteCases[data,{_,x_,_,x_}]

(10^6) < |Aut| < (10^10) and < 750 nodes

See bug(456585)

Length[todo=Cases[GraphData[#,{"|Aut|","#"}]&/@GraphData[;;750],{_?(10^6≤#≤10^10&),gn_}:>gn]]

todo

data=Monitor[{gn=#,Check[GraphData[#,"CyclicGroup"],Print[#]],Sequence@@Timing[MemoryConstrained[CyclicGroupGraphQ[GraphData[gn=#]],20*^9]]}&/@todo,gn];//Timing

Cases[data,{gn_,_,_,_?FailureQ}:>gn]

DeleteCases[data,{_,x_,_,x_}]

(10^6) < |Aut| < (10^10) and 750 ≤ nodes ≤ 1000

See bug(456585)

Length[todo=Cases[GraphData[#,{"|Aut|","#"}]&/@GraphData[750;;1000],{_?(10^6≤#≤10^10&),gn_}:>gn]]

todo

data=Monitor[{gn=#,Check[GraphData[#,"CyclicGroup"],Print[#]],Sequence@@Timing[MemoryConstrained[CyclicGroupGraphQ[GraphData[gn=#]],20*^9]]}&/@todo,gn];//Timing

Cases[data,{gn_,_,_,_?FailureQ}:>gn]

DeleteCases[data,{_,x_,_,x_}]

|Aut| < (10^10) and 750 ≤ nodes < 2000

See bug(456585)

Length[todo=Cases[GraphData[#,{"|Aut|","#"}]&/@GraphData[750;;2000],{_?(#≤10^10&),gn_}:>gn]]

todo

data=Print[{gn=#,GraphData[#,"CyclicGroup"],MemoryConstrained[CyclicGroupGraphQ[GraphData[gn=#]],20*^9]}//Timing]&/@todo;

Position[todo,{"Mathon",_}]

{"Mathon", 0} needs 20+ GB

data=Print[{gn=#,GraphData[#,"CyclicGroup"],MemoryConstrained[CyclicGroupGraphQ[GraphData[gn=#]],20*^9]}//Timing]&/@Take[todo,{110,111}];

data=Print[{gn=#,GraphData[#,"CyclicGroup"],MemoryConstrained[CyclicGroupGraphQ[GraphData[gn=#]],20*^9]}//Timing]&/@Drop[todo,111];

GraphData using |generators| == 1 test (does not catch all cyclic group graphs)

TextGrid[sorted=Sort[{GroupOrder[GraphAutomorphismGroup[GraphData[#]]],GraphData[#,"V"],#}&/@cyclic],Dividers->All,Alignment->{{{Decimal},Left}}]

Specific orders

Preload

Length[Graphs[8]]//Timing//AbsoluteTiming

Length[Graphs[9]]//Timing//AbsoluteTiming

Length[Graphs[10]]//Timing//AbsoluteTiming

C3 (4 on 9 nodes, 56 on 10 nodes)

All groups of prime order are cyclic

FiniteGroupCount[3]

FiniteGroupData[3]

Only group of order 3 is cyclic so don't have to check for cyclic-ness

GraphData["SmallestCyclicGroupGraph"]//StyleGraphs

Do[Print[{n,Length[pos=Flatten[Position[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","AutomorphismCount","AutomorphismCount_"<>If[n==10,"","0"]<>ToString[n]<>".m"}]],3]]],pos}],{n,10}]

g9=Graphs[9][[{159666,215668,240247,251704}]]

CyclicGroupGraphQ/@g9

RecognizeGraph/@%

Do[Print[{n,Select[Graphs[n],GroupOrder[GraphAutomorphismGroup[#]]==3&]//Timing}],{n,10}];

Do[Print[{n,Select[Graphs[n],GroupOrder[GraphAutomorphismGroup[#]]==3&]//Timing}],{n,{10}}];

Quit

RecognizeGraph/@{,,,}

Sort[{EdgeCount[#],#}&/@{,,,}]

C4 (12 on 10 nodes)

FiniteGroupData[4]

There is a group of order 4 that is not cyclic so need to check for cyclic-ness

Do[Print[{n,Length[pos=Flatten[Position[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","AutomorphismCount","AutomorphismCount_"<>If[n==10,"","0"]<>ToString[n]<>".m"}]],4]]],pos}],{n,7}]

Do[
Print[{n,Select[Graphs[n],GroupOrder[aut=GraphAutomorphismGroup[#]]==4&&CyclicPermutationGroupQ[aut]&]//Timing}],
{n,10}]

C4GroupGraphs=Sort[{EdgeCount[#],#}&/@{,,,,,,,,,,,}]

Length[C4GroupGraphs]

RecognizeGraph[#,"Cache"->"InternalOnly"]&/@C4GroupGraphs[[All,2]]

Select[C4GroupGraphs,IsomorphicGraphQ[#[[2]],SquareWithtangledHats]&]

CyclicGraphQ/@C4GroupGraphs[[All,2]]

GroupOrder[GraphAutomorphismGroup[#]]&/@C4GroupGraphs[[All,2]]

Select[C4GroupGraphs[[All,2]],Length[GroupGenerators[GraphAutomorphismGroup[#]]]==1&]

C5 (none ≤ 10 nodes)

FiniteGroupData[5]

FiniteGroupCount[5]

Only group of order 5 is cyclic

Do[Print[{n,Length[pos=Flatten[Position[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","AutomorphismCount","AutomorphismCount_"<>If[n==10,"","0"]<>ToString[n]<>".m"}]],5]]],pos}],{n,10}]

C6 XXX

FiniteGroupCount[6]

FiniteGroupData[6]

There is a group of order6 that is not cyclic so need to check for cyclic-ness

Do[Print[{n,Length[pos=Flatten[Position[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","AutomorphismCount","AutomorphismCount_"<>If[n==10,"","0"]<>ToString[n]<>".m"}]],6]]],pos}],{n,8}]

Do[
Print[{n,Select[Graphs[n],GroupOrder[aut=GraphAutomorphismGroup[#]]==6&&CyclicPermutationGroupQ[aut]&]//Timing}],
{n,10}]

C4GroupGraphs=Sort[{EdgeCount[#],#}&/@{}]

Length[C4GroupGraphs]

RecognizeGraph[#,"Cache"->"InternalOnly"]&/@C4GroupGraphs[[All,2]]

Select[C4GroupGraphs,IsomorphicGraphQ[#[[2]],SquareWithtangledHats]&]

CyclicGraphQ/@C4GroupGraphs[[All,2]]

GroupOrder[GraphAutomorphismGroup[#]]&/@C4GroupGraphs[[All,2]]

Select[C4GroupGraphs[[All,2]],Length[GroupGenerators[GraphAutomorphismGroup[#]]]==1&]

GraphicsGrid[Partition[StyleGraphs[#2,PlotLabel->Style[Row[{Style["V",Italic]," == 10, ",Style["E",Italic]," == "<>ToString[#]<>", |Aut| == 4"}],Directive[Black,FontFamily->"Times",14]]]&@@@C4GroupGraphs,UpTo[4]],Alignment->Top,Dividers->All,ImageSize->700]

C6 or higher (none on ≤ 10 nodes)

Do[
Print[{n,Select[Graphs[n],GroupOrder[aut=GraphAutomorphismGroup[#]]>5&&CyclicPermutationGroupQ[aut]&]//Timing}],
{n,10}]

C7 (none ≤ 10 nodes)

FiniteGroupData[7]

FiniteGroupCount[7]

Only group of order 7 is cyclic

Do[Print[{n,Length[pos=Flatten[Position[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","AutomorphismCount","AutomorphismCount_"<>If[n==10,"","0"]<>ToString[n]<>".m"}]],7]]],pos}],{n,10}]

Embeddings

<<MathWorld`Graphs`

{"C3GroupGraph", {9, 1}}

Names

GraphData[{"C3GroupGraph",{9,1}},"StandardName"]

GraphData[{"C3GroupGraph",{9,1}},"StandardNames"]

Primary

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

All

Quit

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C3GroupGraph",{9,1}}]]

Default embedding

GraphPlot[Graph[GraphData[{"C3GroupGraph",{9,1}},"VertexList"],GraphData[{"C3GroupGraph",{9,1}},"Edges"]]]

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

RecognizeGraph@g

Degenerate

GraphData[{"C3GroupGraph",{9,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C3GroupGraph",{9,1}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"C3GroupGraph",{9,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C3GroupGraph",{9,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C3GroupGraph",{9,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C3GroupGraph",{9,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C3GroupGraph",{9,1}},"Hamiltonian"]

GraphData[{"C3GroupGraph",{9,1}},"LCF"]

GraphData[{"C3GroupGraph",{9,1}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C3GroupGraph",{9,1}},"Planar"]

GraphData[{"C3GroupGraph",{9,1}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"C3GroupGraph",{9,1}}]],10]

PlanarGraphEmbeddings

GraphData[{"C3GroupGraph",{9,1}},"PlanarEmbeddingCount"]

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

Length[plemb]

MinimalCrossing

GraphData[{"C3GroupGraph",{9,1}},{"RCN","CN"}]

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

MinimalLocalCrossing

GraphData[{"C3GroupGraph",{9,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C3GroupGraph",{9,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C3GroupGraph",{9,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C3GroupGraph",{9,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"C3GroupGraph",{9,1}},"Circulant"]

GraphData[{"C3GroupGraph",{9,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C3GroupGraph",{9,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C3GroupGraph",{9,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C3GroupGraph",{9,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C3GroupGraph",{9,1}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C3GroupGraph",{9,1}},"Line"]

LineGraphQ[GraphData[{"C3GroupGraph",{9,1}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C3GroupGraph",{9,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"C3GroupGraph",{9,1}},"Halin"]

GraphData[{"C3GroupGraph",{9,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C3GroupGraph",{9,1}},"Rigid"]

GraphData[{"C3GroupGraph",{9,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C3GroupGraph",{9,1}},"Flexible"]

GraphData[{"C3GroupGraph",{9,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C3GroupGraph",{9,1}},"LCF"]

GraphData[{"C3GroupGraph",{9,1}},"HamiltonianCycleCount"]

GraphData[{"C3GroupGraph",{9,1}},"LCFSignature"]

GraphData[{"C3GroupGraph",{9,1}},"LCFNotations"]

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

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

UnitDistance

GraphData[{"C3GroupGraph",{9,1}},"UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"C3GroupGraph",{9,1}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"C3GroupGraph",{9,1}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"C3GroupGraph",{9,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"C3GroupGraph",{9,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"C3GroupGraph",{9,1}},"Polyhedral"]

GraphData[{"C3GroupGraph",{9,1}},"Graph",{"3D","Polyhedron"}]

{"C3GroupGraph", {9, 2}} == {"Configuration", {{9, 3}, 1}}

Names

GraphData[{"C3GroupGraph",{9,2}},"StandardName"]

GraphData[{"C3GroupGraph",{9,2}},"StandardNames"]

{"C3GroupGraph", {9, 3}}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C3GroupGraph",{9,3}}]]

Default embedding

GraphPlot[RotateGraph[Graph[GraphData[{"C3GroupGraph",{9,3}},"VertexList"],GraphData[{"C3GroupGraph",{9,3}},"Edges"],GraphLayout->"HighDimensionalEmbedding"],-.35]]

GraphPlot@RotateGraph[GraphicsToGraph@,Pi/2]

Mean[{{-1,0},{1,0},{0,Sqrt[3]}}]

v={{-1,0},{1,0},{0,Sqrt[3]}};
v=Join[v,Mean/@Partition[v,2,1,1],CirclePoints[{0,(1/(Sqrt[3]))},{1/2,q},3]];

FullSimplify[RegionDistance[Line[v[[{2,8}]]],v[[9]]],q>0]

Solve[ 35+24 Cos[q]+16 Cos[2 q]-8 (Sqrt[3]) (1+4 Cos[q]) Sin[q]==0,q]//FullSimplify

ArcTan[(Sqrt[3]) (1-(4/(3+(Sqrt[61]))))]//N

ArcTan[(1/13) (Sqrt[3]) (16+(Sqrt[61]))]//N

v={{-1,0},{1,0},{0,Sqrt[3]}};
v=Join[v,Mean/@Partition[v,2,1,1],CirclePoints[{0,(1/(Sqrt[3]))},{1/2,ArcTan[(1/13) (Sqrt[3]) (16+(Sqrt[61]))]},3]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,4,2,5,3,6,1,8,7,6,4,5,6],e[4,8,9,2],{9,5},e[3,7,9]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

v={{-1,0},{1,0},{0,Sqrt[3]}};
v=Join[v,Mean/@Partition[v,2,1,1],CirclePoints[{0,(1/(Sqrt[3]))},{1/2,Pi/2},3]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,4,2,5,3,6,1,8,7,6,4,5,6],e[4,8,9,2],{9,5},e[3,7,9]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

gs=UnlabelGraph/@{,,,,,}

Degenerate

GraphData[{"C3GroupGraph",{9,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C3GroupGraph",{9,3}},"Graph","Degenerate"]

Configuration

GetGraphData[{"C3GroupGraph",{9,3}},"File"]

GraphData[{"C3GroupGraph",{9,3}},"Configuration"]

GraphData[{"C3GroupGraph",{9,3}},"Graph","Configuration"]//StyleGraphs

Configuration...

config=%[[1]]

(alledges=AddAllConfigurationEdges[config])//Timing

RecognizeGraph@alledges

ConfigurationDiagram[config,.2]

lines=ConfigurationLines[config]

ConfigurationNotation[lines]

GraphData[{"C3GroupGraph",{9,3}},"IncidenceLines"]

levi=LeviGraph[lines]

RecognizeGraph[levi]

GraphData[{"C3GroupGraph",{9,3}},"LeviGraph","Name"]

FirstCase[GraphData[{"C3GroupGraph",{9,3}},"StandardNames"],{"Incidence",_}]

Cases[GraphData[{"C3GroupGraph",{9,3}},"StandardNames"],_String?(StringMatchQ[#,"*Configuration*"]&)]

GraphData[{"C3GroupGraph",{9,3}},"OrdinaryLineGraphName"]

(ordinarylinegraph=OrdinaryLineGraph[config])//Timing

RecognizeGraph@ordinarylinegraph

Incidence

GetGraphData[{"C3GroupGraph",{9,3}},"File"]

GraphData[{"C3GroupGraph",{9,3}},"Incidence"]

Select[GraphData[All],GraphData[#,"LeviGraph","Name"]==={"C3GroupGraph",{9,3}}&]

lines=GraphData[{"C3GroupGraph",{9,3}},"IncidenceLines"]

ConfigurationNotation[lines]

levi=LeviGraph[lines]

RecognizeGraph@levi

GeneralizedPetersen

GraphData[{"C3GroupGraph",{9,3}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C3GroupGraph",{9,3}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C3GroupGraph",{9,3}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C3GroupGraph",{9,3}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C3GroupGraph",{9,3}},"Hamiltonian"]

GraphData[{"C3GroupGraph",{9,3}},"LCF"]

GraphData[{"C3GroupGraph",{9,3}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C3GroupGraph",{9,3}},"Planar"]

GraphData[{"C3GroupGraph",{9,3}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"C3GroupGraph",{9,3}}]],10]

PlanarGraphEmbeddings

GraphData[{"C3GroupGraph",{9,3}},"PlanarEmbeddingCount"]

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

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"C3GroupGraph",{9,3}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"C3GroupGraph",{9,3}}],"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  3 #1

GraphPlot@

v=Join[CirclePoints[3],CirclePoints[{1/2,Pi/2-Pi/20},3],CirclePoints[{a,Pi/2+Pi/20},3]];

FullSimplify[RegionDistance[Line@v[[{5,4}]],v[[7]]],a>0]

Solve[(Sqrt[3])-a (-1+(Sqrt[5])+4 Cos[(π/15)])==0,a]//FullSimplify

N[%]

v=Join[CirclePoints[3],CirclePoints[{1/2,Pi/2-Pi/20},3],CirclePoints[{((Sqrt[3])/(-1+(Sqrt[5])+4 Cos[(π/15)])),Pi/2+Pi/20},3]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[9,1,2,3,1,6,9,4,7,5,8,6],e[5,3,8,7,2,4],e[8,9,7]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Tutte embedding construction  3 #2

GraphPlot@

v=Join[CirclePoints[3],CirclePoints[{2/5,Pi/2},6]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph[g]

MinimalCrossing

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

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

MinimalLocalCrossing

GraphData[{"C3GroupGraph",{9,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C3GroupGraph",{9,3}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C3GroupGraph",{9,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C3GroupGraph",{9,3}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"C3GroupGraph",{9,3}},"Circulant"]

GraphData[{"C3GroupGraph",{9,3}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C3GroupGraph",{9,3}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C3GroupGraph",{9,3}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C3GroupGraph",{9,3}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C3GroupGraph",{9,3}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C3GroupGraph",{9,3}},"Line"]

LineGraphQ[GraphData[{"C3GroupGraph",{9,3}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C3GroupGraph",{9,3}}]]

RecognizeGraph[%]

Halin

GraphData[{"C3GroupGraph",{9,3}},"Halin"]

GraphData[{"C3GroupGraph",{9,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C3GroupGraph",{9,3}},"Rigid"]

GraphData[{"C3GroupGraph",{9,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C3GroupGraph",{9,3}},"Flexible"]

GraphData[{"C3GroupGraph",{9,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C3GroupGraph",{9,3}},"LCF"]

GraphData[{"C3GroupGraph",{9,3}},"HamiltonianCycleCount"]

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

GraphData[{"C3GroupGraph",{9,3}},"LCFNotations"]

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

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

UnitDistance

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

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C3GroupGraph",{9,3}},"Matchstick"]

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

3D default

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

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"C3GroupGraph",{9,3}},"Polyhedral"]

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

Graphics3D[{FaceForm[Green,Red],GraphData[{"C3GroupGraph",{9,3}},"Polyhedron"]}]

3D Canonical

GraphData[{"C3GroupGraph",{9,3}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"C3GroupGraph",{9,3}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"C3GroupGraph",{9,3}}],-1]}]

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

SimplePolyhedronQ[can]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

{"C3GroupGraph", {9, 4}}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C3GroupGraph",{9,4}}]]

Default embedding

GraphPlot[Graph[GraphData[{"C3GroupGraph",{9,4}},"VertexList"],GraphData[{"C3GroupGraph",{9,4}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]]

v=CirclePoints[3];
v=Join[v,#1+(#2-#1)2/3&@@@Partition[v,2,1,1],CirclePoints[{1/4,q},3]];

FullSimplify[RegionDistance[Line[v[[{2,6}]]],v[[7]]]^2,q>0]

Solve[(1/448) (30+13 Cos[2 q]+6 (Sqrt[3]) Cos[q] (-4+Sin[q])-8 Sin[q])==0,q,PositiveReals]//FullSimplify

N[%]

v=CirclePoints[3];
v=Join[v,#1+(#2-#1)2/3&@@@Partition[v,2,1,1],CirclePoints[{1/4,2 (ArcTan[(1/11) (14-5 (Sqrt[3]))])},3]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,4,2,5,3,6,1,9,5,4,7,9,6,4,8,3],{5,6},e[5,8,7,6],{7,2},{8,9}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

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

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

Configuration

GetGraphData[{"C3GroupGraph",{9,4}},"File"]

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

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

Configuration...

config=%[[1]]

(alledges=AddAllConfigurationEdges[config])//Timing

RecognizeGraph@alledges

ConfigurationDiagram[config,.2]

lines=ConfigurationLines[config]

ConfigurationNotation[lines]

GraphData[{"C3GroupGraph",{9,4}},"IncidenceLines"]

levi=LeviGraph[lines]

RecognizeGraph[levi]

GraphData[{"C3GroupGraph",{9,4}},"LeviGraph","Name"]

FirstCase[GraphData[{"C3GroupGraph",{9,4}},"StandardNames"],{"Incidence",_}]

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

GraphData[{"C3GroupGraph",{9,4}},"OrdinaryLineGraphName"]

(ordinarylinegraph=OrdinaryLineGraph[config])//Timing

RecognizeGraph@ordinarylinegraph

Incidence

GetGraphData[{"C3GroupGraph",{9,4}},"File"]

GraphData[{"C3GroupGraph",{9,4}},"Incidence"]

Select[GraphData[All],GraphData[#,"LeviGraph","Name"]==={"C3GroupGraph",{9,4}}&]

lines=GraphData[{"C3GroupGraph",{9,4}},"IncidenceLines"]

ConfigurationNotation[lines]

levi=LeviGraph[lines]

RecognizeGraph@levi

GeneralizedPetersen

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

IGraph

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

Bilateral

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

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

Circular

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

Circular construction

GraphData[{"C3GroupGraph",{9,4}},"Hamiltonian"]

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

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

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

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

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

MinimalCrossing

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

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

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"C3GroupGraph",{9,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"C3GroupGraph",{9,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction

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

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

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

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

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

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

Circulant

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

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

Circulant construction

GraphData[{"C3GroupGraph",{9,4}},"NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

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

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

RootGraph

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

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

RecognizeGraph[%]

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

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

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

3D default

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

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"C4GroupGraph", {10, 1}}

Names

GraphData[{"C4GroupGraph",{10,1}},"StandardName"]

GraphData[{"C4GroupGraph",{10,1}},"StandardNames"]

Primary

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

All

GraphData[{"C4GroupGraph",{10,1}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,1}}]]

Default embedding

GraphPlot[RotateGraph[Graph[GraphData[{"C4GroupGraph",{10,1}},"VertexList"],GraphData[{"C4GroupGraph",{10,1}},"Edges"],GraphLayout->"SpringEmbedding"],Pi/2]]

v=Join[CirclePoints[{1,Pi/2},6]];
v=Join[v,Subdivide[v[[3]],v[[5]],3][[2;;-2]],{#/3,4/6-1/12}&/@{-1,1}];
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs={,};

Degenerate

GraphData[{"C4GroupGraph",{10,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C4GroupGraph",{10,1}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"C4GroupGraph",{10,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C4GroupGraph",{10,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C4GroupGraph",{10,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C4GroupGraph",{10,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C4GroupGraph",{10,1}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,1}},"LCF"]

GraphData[{"C4GroupGraph",{10,1}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,1}},"Planar"]

GraphData[{"C4GroupGraph",{10,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"C4GroupGraph",{10,1}},{"RCN","CN"}]

GraphData[{"C4GroupGraph",{10,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

GraphPlot@RotateGraph[,-4Pi/5]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

GraphPlot@RotateGraph[,3Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

GraphPlot@RotateGraph[,4Pi/3]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

GraphPlot@RotateGraph[,2Pi/3]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

gs=UnlabelGraph/@{,,,}

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

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

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

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

GraphData[{"C4GroupGraph",{10,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"C4GroupGraph",{10,1}},"Circulant"]

GraphData[{"C4GroupGraph",{10,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C4GroupGraph",{10,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C4GroupGraph",{10,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C4GroupGraph",{10,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C4GroupGraph",{10,1}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,1}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,1}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,1}},"Halin"]

GraphData[{"C4GroupGraph",{10,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C4GroupGraph",{10,1}},"Rigid"]

GraphData[{"C4GroupGraph",{10,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C4GroupGraph",{10,1}},"Flexible"]

GraphData[{"C4GroupGraph",{10,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C4GroupGraph",{10,1}},"LCF"]

GraphData[{"C4GroupGraph",{10,1}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,1}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,1}},"LCFNotations"]

GraphData[{"C4GroupGraph",{10,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"C4GroupGraph",{10,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"C4GroupGraph",{10,1}}],Debug->True]//Timing

GraphData[{"C4GroupGraph",{10,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,1}},"Matchstick"]

GraphData[{"C4GroupGraph",{10,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,1}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"C4GroupGraph",{10,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"C4GroupGraph",{10,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"C4GroupGraph",{10,1}},"Polyhedral"]

GraphData[{"C4GroupGraph",{10,1}},"Graph",{"3D","Polyhedron"}]

{"C4GroupGraph", {10, 2}}

Names

GraphData[{"C4GroupGraph",{10,2}},"StandardName"]

GraphData[{"C4GroupGraph",{10,2}},"StandardNames"]

Primary

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

All

GraphData[{"C4GroupGraph",{10,2}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,2}}]]

Default embedding

GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,2}},"VertexList"],GraphData[{"C4GroupGraph",{10,2}},"Edges"]]]

RotateGraph[GraphicsToGraph@,Pi]

v=Join[CirclePoints[6],Subdivide[{-1/2,1/4},{1/2,1/4},2],{{0,-1/2}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

DegenerateGraphEmbeddingTypes[g]

RecognizeGraph@g

Deg

v={{0,0},{1,0},{1,1},{0,1},{0,1/4},{1/2,1/4},{1,1/4},{1/4,3/4},{1/2,3/4},{3/4,3/4}};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs={,};

Degenerate

GraphData[{"C4GroupGraph",{10,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C4GroupGraph",{10,2}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"C4GroupGraph",{10,2}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C4GroupGraph",{10,2}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C4GroupGraph",{10,2}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C4GroupGraph",{10,2}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C4GroupGraph",{10,2}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,2}},"LCF"]

GraphData[{"C4GroupGraph",{10,2}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,2}},"Planar"]

GraphData[{"C4GroupGraph",{10,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"C4GroupGraph",{10,2}},{"RCN","CN"}]

GraphData[{"C4GroupGraph",{10,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

GraphPlot@RotateGraph[,-3Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

GraphPlot@RotateGraph[,-2Pi/3]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

gs=UnlabelGraph/@{,}

MinimalLocalCrossing

GraphData[{"C4GroupGraph",{10,2}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,2}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,2}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,2}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"C4GroupGraph",{10,2}},"Circulant"]

GraphData[{"C4GroupGraph",{10,2}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C4GroupGraph",{10,2}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C4GroupGraph",{10,2}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C4GroupGraph",{10,2}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C4GroupGraph",{10,2}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,2}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,2}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,2}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,2}},"Halin"]

GraphData[{"C4GroupGraph",{10,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C4GroupGraph",{10,2}},"Rigid"]

GraphData[{"C4GroupGraph",{10,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C4GroupGraph",{10,2}},"Flexible"]

GraphData[{"C4GroupGraph",{10,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C4GroupGraph",{10,2}},"LCF"]

GraphData[{"C4GroupGraph",{10,2}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,2}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,2}},"LCFNotations"]

GraphData[{"C4GroupGraph",{10,2}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"C4GroupGraph",{10,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"C4GroupGraph",{10,2}}],Debug->True]//Timing

GraphData[{"C4GroupGraph",{10,2}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,2}},"Matchstick"]

GraphData[{"C4GroupGraph",{10,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,2}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"C4GroupGraph",{10,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"C4GroupGraph",{10,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"C4GroupGraph",{10,2}},"Polyhedral"]

GraphData[{"C4GroupGraph",{10,2}},"Graph",{"3D","Polyhedron"}]

{"C4GroupGraph", {10, 3}}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,3}}]]

House of Graphs

https://houseofgraphs.org/graphs/49350

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

RecognizeGraph@g

Default embedding

GraphPlot[RotateGraph[Graph[GraphData[{"C4GroupGraph",{10,3}},"VertexList"],GraphData[{"C4GroupGraph",{10,3}},"Edges"]],Pi/2]]

v={{0,0},{1/2,0},{1,0},{1,1/3},{1,1},{1/2,1},{0,1},{0,1/3},{1/4,2/3},{3/4,2/3}};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

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

RecognizeGraph@g

GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,3}},"VertexList"],GraphData[{"C4GroupGraph",{10,3}},"Edges"],GraphLayout->"RadialEmbedding"]]

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

RecognizeGraph@g

gs=UnlabelGraph/@{,}

StackExchange embedding

https://mathematica.stackexchange.com/questions/310123/graph-layout-graph-embedding-challenge-for-minimal-graph-with-mathbbz-4-sy

Import["https://i.sstatic.net/MU4utfpB.png"]

g0=GraphData["SquareWithFourTriangles","Graph","Labeled"]

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

DegenerateGraphEmbeddingTypes@g

RecognizeGraph@g

Degenerate

GraphData[{"C4GroupGraph",{10,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C4GroupGraph",{10,3}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"C4GroupGraph",{10,3}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C4GroupGraph",{10,3}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C4GroupGraph",{10,3}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C4GroupGraph",{10,3}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C4GroupGraph",{10,3}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,3}},"LCF"]

GraphData[{"C4GroupGraph",{10,3}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,3}},"Planar"]

GraphData[{"C4GroupGraph",{10,3}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"C4GroupGraph",{10,3}}]],10]

PlanarGraphEmbeddings

GraphData[{"C4GroupGraph",{10,3}},"PlanarEmbeddingCount"]

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

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"C4GroupGraph",{10,3}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"C4GroupGraph",{10,3}}],"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 4

GraphPlot[]

v={{0,0},{5,0},{4,1},{1,2},{2,2},{3,2},{2,3},{2,4},{0,5},{5,5}}/5;
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph[g]

MinimalCrossing

GraphData[{"C4GroupGraph",{10,3}},{"RCN","CN"}]

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

MinimalLocalCrossing

GraphData[{"C4GroupGraph",{10,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,3}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,3}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"C4GroupGraph",{10,3}},"Circulant"]

GraphData[{"C4GroupGraph",{10,3}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C4GroupGraph",{10,3}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C4GroupGraph",{10,3}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C4GroupGraph",{10,3}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C4GroupGraph",{10,3}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,3}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,3}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,3}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,3}},"Halin"]

GraphData[{"C4GroupGraph",{10,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C4GroupGraph",{10,3}},"Rigid"]

GraphData[{"C4GroupGraph",{10,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C4GroupGraph",{10,3}},"Flexible"]

GraphData[{"C4GroupGraph",{10,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C4GroupGraph",{10,3}},"LCF"]

GraphData[{"C4GroupGraph",{10,3}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,3}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,3}},"LCFNotations"]

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

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

UnitDistance

GraphData[{"C4GroupGraph",{10,3}},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,3}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,3}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"C4GroupGraph",{10,3}},"Polyhedral"]

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

Graphics3D[{FaceForm[Green,Red],GraphData[{"C4GroupGraph",{10,3}},"Polyhedron"]}]

3D Canonical

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

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

3D Canonical construction

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

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

SimplePolyhedronQ[can]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

{"C4GroupGraph", {10, 4}}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

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

Default embedding

GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,4}},"VertexList"],GraphData[{"C4GroupGraph",{10,4}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]]

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

GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,4}},"VertexList"],GraphData[{"C4GroupGraph",{10,4}},"Edges"],GraphLayout->"SpringEmbedding"]]

RotateGraph[,Pi/2]

v={{0,0},{1/2,0},{1,0},{1,2/3},{1,1},{1/2,1},{0,1},{0,2/3},{1/3,1/2},{2/3,1/2}};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

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

RecognizeGraph@g

gs=UnlabelGraph/@{,}

Degenerate

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

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

GeneralizedPetersen

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

IGraph

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

Bilateral

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

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

Circular

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

Circular construction

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

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

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

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

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

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

MinimalCrossing

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

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

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

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

MinimaRectilinearlLocalCrossing construction

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

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

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

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

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

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

Circulant

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

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

Circulant construction

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

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

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

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

RootGraph

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

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

RecognizeGraph[%]

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

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

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

3D default

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

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"C4GroupGraph", {10, 5}}

Names

GraphData[{"C4GroupGraph",{10,5}},"StandardName"]

GraphData[{"C4GroupGraph",{10,5}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,5}}]]

Default embedding

ScaleGraph@RotateGraph[Graph[GraphData[{"C4GroupGraph",{10,5}},"VertexList"],GraphData[{"C4GroupGraph",{10,5}},"Edges"]],-Pi/2]

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

RecognizeGraph@g

Degenerate

GraphData[{"C4GroupGraph",{10,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C4GroupGraph",{10,5}},"Graph","Degenerate"]

GeneralizedPetersen

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

IGraph

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

Bilateral

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

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

Circular

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

Circular construction

GraphData[{"C4GroupGraph",{10,5}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,5}},"LCF"]

GraphData[{"C4GroupGraph",{10,5}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,5}},"Planar"]

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

MinimalCrossing

GraphData[{"C4GroupGraph",{10,5}},{"RCN","CN"}]

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

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"C4GroupGraph",{10,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction

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

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

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

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

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

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

Circulant

GraphData[{"C4GroupGraph",{10,5}},"Circulant"]

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

Circulant construction

GraphData[{"C4GroupGraph",{10,5}},"NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,5}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,5}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,5}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,5}},"Halin"]

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

Rigid

GraphData[{"C4GroupGraph",{10,5}},"Rigid"]

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

Flexible

GraphData[{"C4GroupGraph",{10,5}},"Flexible"]

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

LCF

GraphData[{"C4GroupGraph",{10,5}},"LCF"]

GraphData[{"C4GroupGraph",{10,5}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,5}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,5}},"LCFNotations"]

GraphData[{"C4GroupGraph",{10,5}},"Graph","LCF"]//StyleGraphs

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

Unit Distance

GraphData[{"C4GroupGraph",{10,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"C4GroupGraph",{10,5}}],Debug->True]//Timing

GraphData[{"C4GroupGraph",{10,5}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,5}},"Matchstick"]

GraphData[{"C4GroupGraph",{10,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,5}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"C4GroupGraph",{10,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"C4GroupGraph",{10,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"C4GroupGraph",{10,5}},"Polyhedral"]

GraphData[{"C4GroupGraph",{10,5}},"Graph",{"3D","Polyhedron"}]

{"C4GroupGraph", {10, 6}}

Names

GraphData[{"C4GroupGraph",{10,6}},"StandardName"]

GraphData[{"C4GroupGraph",{10,6}},"StandardNames"]

Primary

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

All

GraphData[{"C4GroupGraph",{10,6}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,6}}]]

Default embedding

RotateGraph[GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,6}},"VertexList"],GraphData[{"C4GroupGraph",{10,6}},"Edges"]]],Pi/2]

GraphReplot@

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

v={{0,0},{1/2,0},{1,0},{1,1/2},{1,1},{1/2,1},{0,1},{0,1/2},{1/3,3/8},{2/3,3/8}};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs={,}

Degenerate

GraphData[{"C4GroupGraph",{10,6}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C4GroupGraph",{10,6}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"C4GroupGraph",{10,6}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C4GroupGraph",{10,6}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C4GroupGraph",{10,6}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C4GroupGraph",{10,6}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C4GroupGraph",{10,6}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,6}},"LCF"]

GraphData[{"C4GroupGraph",{10,6}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,6}},"Planar"]

GraphData[{"C4GroupGraph",{10,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"C4GroupGraph",{10,6}},{"RCN","CN"}]

GraphData[{"C4GroupGraph",{10,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"C4GroupGraph",{10,6}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,6}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,6}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,6}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

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

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

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

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

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

Circulant

GraphData[{"C4GroupGraph",{10,6}},"Circulant"]

GraphData[{"C4GroupGraph",{10,6}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C4GroupGraph",{10,6}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C4GroupGraph",{10,6}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C4GroupGraph",{10,6}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C4GroupGraph",{10,6}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,6}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,6}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,6}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,6}},"Halin"]

GraphData[{"C4GroupGraph",{10,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C4GroupGraph",{10,6}},"Rigid"]

GraphData[{"C4GroupGraph",{10,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C4GroupGraph",{10,6}},"Flexible"]

GraphData[{"C4GroupGraph",{10,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C4GroupGraph",{10,6}},"LCF"]

GraphData[{"C4GroupGraph",{10,6}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,6}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,6}},"LCFNotations"]

GraphData[{"C4GroupGraph",{10,6}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"C4GroupGraph",{10,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"C4GroupGraph",{10,6}}],Debug->True]//Timing

GraphData[{"C4GroupGraph",{10,6}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceGraphEmbeddingQ[%]

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,6}},"Matchstick"]

GraphData[{"C4GroupGraph",{10,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,6}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"C4GroupGraph",{10,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"C4GroupGraph",{10,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"C4GroupGraph",{10,6}},"Polyhedral"]

GraphData[{"C4GroupGraph",{10,6}},"Graph",{"3D","Polyhedron"}]

{"C4GroupGraph", {10, 7}}

Names

GraphData[{"C4GroupGraph",{10,7}},"StandardName"]

GraphData[{"C4GroupGraph",{10,7}},"StandardNames"]

Primary

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

All

GraphData[{"C4GroupGraph",{10,7}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,7}}]]

Default embedding

RotateGraph[GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,7}},"VertexList"],GraphData[{"C4GroupGraph",{10,7}},"Edges"]]],Pi/2]

v=Join[CirclePoints[6],{{0,-1/2},{0,3/4},{-1/2,1/4},{1/2,1/4}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

v={{0,0},{1,0},{1,1/2},{1,1},{0,1},{0,1/2},{1/2,1/4},{1/3,5/8},{2/3,5/8},{1/2,7/8}};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs=UnlabelGraph/@{,}

Degenerate

GraphData[{"C4GroupGraph",{10,7}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C4GroupGraph",{10,7}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"C4GroupGraph",{10,7}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C4GroupGraph",{10,7}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C4GroupGraph",{10,7}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C4GroupGraph",{10,7}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C4GroupGraph",{10,7}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,7}},"LCF"]

GraphData[{"C4GroupGraph",{10,7}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,7}},"Planar"]

GraphData[{"C4GroupGraph",{10,7}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"C4GroupGraph",{10,7}},{"RCN","CN"}]

GraphData[{"C4GroupGraph",{10,7}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

GraphPlot@RotateGraph[,Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"C4GroupGraph",{10,7}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,7}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,7}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,7}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

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

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

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

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

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

Circulant

GraphData[{"C4GroupGraph",{10,7}},"Circulant"]

GraphData[{"C4GroupGraph",{10,7}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C4GroupGraph",{10,7}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C4GroupGraph",{10,7}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C4GroupGraph",{10,7}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C4GroupGraph",{10,7}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,7}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,7}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,7}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,7}},"Halin"]

GraphData[{"C4GroupGraph",{10,7}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C4GroupGraph",{10,7}},"Rigid"]

GraphData[{"C4GroupGraph",{10,7}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C4GroupGraph",{10,7}},"Flexible"]

GraphData[{"C4GroupGraph",{10,7}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C4GroupGraph",{10,7}},"LCF"]

GraphData[{"C4GroupGraph",{10,7}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,7}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,7}},"LCFNotations"]

GraphData[{"C4GroupGraph",{10,7}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"C4GroupGraph",{10,7}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"C4GroupGraph",{10,7}}],Debug->True]//Timing

GraphData[{"C4GroupGraph",{10,7}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,7}},"Matchstick"]

GraphData[{"C4GroupGraph",{10,7}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,7}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"C4GroupGraph",{10,7}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"C4GroupGraph",{10,7}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"C4GroupGraph",{10,7}},"Polyhedral"]

GraphData[{"C4GroupGraph",{10,7}},"Graph",{"3D","Polyhedron"}]

{"C4GroupGraph", {10, 8}}

Names

GraphData[{"C4GroupGraph",{10,8}},"StandardName"]

GraphData[{"C4GroupGraph",{10,8}},"StandardNames"]

Primary

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

All

GraphData[{"C4GroupGraph",{10,8}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,8}}]]

Default embedding

GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,8}},"VertexList"],GraphData[{"C4GroupGraph",{10,8}},"Edges"]]]

v={{0,0},{1/2,0},{1,0},{1/3,1/4},{2/3,1/4},{0,1/2},{1,1/2},{0,1},{1/2,1},{1,1}};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"C4GroupGraph",{10,8}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C4GroupGraph",{10,8}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"C4GroupGraph",{10,8}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C4GroupGraph",{10,8}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C4GroupGraph",{10,8}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C4GroupGraph",{10,8}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C4GroupGraph",{10,8}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,8}},"LCF"]

GraphData[{"C4GroupGraph",{10,8}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,8}},"Planar"]

GraphData[{"C4GroupGraph",{10,8}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"C4GroupGraph",{10,8}},{"RCN","CN"}]

GraphData[{"C4GroupGraph",{10,8}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"C4GroupGraph",{10,8}}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union)//Timing

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

GraphPlot@RotateGraph[,Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"C4GroupGraph",{10,8}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,8}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,8}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,8}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

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

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

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

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

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

Circulant

GraphData[{"C4GroupGraph",{10,8}},"Circulant"]

GraphData[{"C4GroupGraph",{10,8}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C4GroupGraph",{10,8}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C4GroupGraph",{10,8}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C4GroupGraph",{10,8}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C4GroupGraph",{10,8}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,8}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,8}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,8}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,8}},"Halin"]

GraphData[{"C4GroupGraph",{10,8}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C4GroupGraph",{10,8}},"Rigid"]

GraphData[{"C4GroupGraph",{10,8}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C4GroupGraph",{10,8}},"Flexible"]

GraphData[{"C4GroupGraph",{10,8}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C4GroupGraph",{10,8}},"LCF"]

GraphData[{"C4GroupGraph",{10,8}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,8}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,8}},"LCFNotations"]

GraphData[{"C4GroupGraph",{10,8}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"C4GroupGraph",{10,8}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"C4GroupGraph",{10,8}}],Debug->True]//Timing

GraphData[{"C4GroupGraph",{10,8}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,8}},"Matchstick"]

GraphData[{"C4GroupGraph",{10,8}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,8}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"C4GroupGraph",{10,8}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"C4GroupGraph",{10,8}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"C4GroupGraph",{10,8}},"Polyhedral"]

GraphData[{"C4GroupGraph",{10,8}},"Graph",{"3D","Polyhedron"}]

{"C4GroupGraph", {10, 9}}

Names

GraphData[{"C4GroupGraph",{10,9}},"StandardName"]

GraphData[{"C4GroupGraph",{10,9}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,9}}]]

Default embedding

RotateGraph[GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,9}},"VertexList"],GraphData[{"C4GroupGraph",{10,9}},"Edges"]]],-Pi/2]

GraphReplot@

GraphReplot@

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

v={{0,0},{1,0},{1,1/2},{1,1},{0,1},{0,1/2},{1/2,1/6},{1/2,3/4},{1/3,1/3},{2/3,1/3}};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

DegenerateGraphEmbeddingTypes@g

gs=UnlabelGraph/@{,}

Degenerate

GraphData[{"C4GroupGraph",{10,9}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C4GroupGraph",{10,9}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"C4GroupGraph",{10,9}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C4GroupGraph",{10,9}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C4GroupGraph",{10,9}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C4GroupGraph",{10,9}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C4GroupGraph",{10,9}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,9}},"LCF"]

GraphData[{"C4GroupGraph",{10,9}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,9}},"Planar"]

GraphData[{"C4GroupGraph",{10,9}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"C4GroupGraph",{10,9}},{"RCN","CN"}]

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

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"C4GroupGraph",{10,9}}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union)//Timing

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"C4GroupGraph",{10,9}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,9}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,9}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

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

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

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

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

Circulant

GraphData[{"C4GroupGraph",{10,9}},"Circulant"]

GraphData[{"C4GroupGraph",{10,9}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C4GroupGraph",{10,9}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C4GroupGraph",{10,9}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C4GroupGraph",{10,9}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C4GroupGraph",{10,9}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,9}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,9}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,9}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,9}},"Halin"]

GraphData[{"C4GroupGraph",{10,9}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C4GroupGraph",{10,9}},"Rigid"]

GraphData[{"C4GroupGraph",{10,9}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C4GroupGraph",{10,9}},"Flexible"]

GraphData[{"C4GroupGraph",{10,9}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C4GroupGraph",{10,9}},"LCF"]

GraphData[{"C4GroupGraph",{10,9}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,9}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,9}},"LCFNotations"]

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

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

UnitDistance

GraphData[{"C4GroupGraph",{10,9}},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,9}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,9}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"C4GroupGraph",{10,9}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"C4GroupGraph",{10,9}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"C4GroupGraph",{10,9}},"Polyhedral"]

GraphData[{"C4GroupGraph",{10,9}},"Graph",{"3D","Polyhedron"}]

{"C4GroupGraph", {10, 10}}

Names

GraphData[{"C4GroupGraph",{10,10}},"StandardName"]

GraphData[{"C4GroupGraph",{10,10}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,10}}]]

Default embedding

RotateGraph[GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,10}},"VertexList"],GraphData[{"C4GroupGraph",{10,10}},"Edges"]]],-Pi/2]

v={{0,0},{1,0},{1,1/2},{1,1},{0,1},{0,1/2},{1/2,1/6},{1/4,1/3},{3/4,1/3},{1/2,3/4}};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

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

g=RotateGraph[FindCorrespondingGraph[,v],Pi]

RecognizeGraph@g

gs={,}

Degenerate

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

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

GeneralizedPetersen

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

IGraph

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

Bilateral

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

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

Circular

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

Circular construction

GraphData[{"C4GroupGraph",{10,10}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,10}},"LCF"]

GraphData[{"C4GroupGraph",{10,10}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,10}},"Planar"]

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

MinimalCrossing

GraphData[{"C4GroupGraph",{10,10}},{"RCN","CN"}]

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

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

GraphPlot@RotateGraph[,-Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

gs={,}

MinimalLocalCrossing

GraphData[{"C4GroupGraph",{10,10}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,10}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction

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

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

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

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

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

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

GraphPlot@

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

RecognizeGraph@g

RectilinearCrossingCount@g

RectilinearLocalCrossingCount@g

Circulant

GraphData[{"C4GroupGraph",{10,10}},"Circulant"]

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

Circulant construction

GraphData[{"C4GroupGraph",{10,10}},"NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,10}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,10}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,10}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,10}},"Halin"]

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

Rigid

GraphData[{"C4GroupGraph",{10,10}},"Rigid"]

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

Flexible

GraphData[{"C4GroupGraph",{10,10}},"Flexible"]

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

LCF

GraphData[{"C4GroupGraph",{10,10}},"LCF"]

GraphData[{"C4GroupGraph",{10,10}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,10}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,10}},"LCFNotations"]

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

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

UnitDistance

GraphData[{"C4GroupGraph",{10,10}},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,10}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,10}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"C4GroupGraph",{10,10}},"Polyhedral"]

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

{"C4GroupGraph", {10, 11}}

Names

GraphData[{"C4GroupGraph",{10,11}},"StandardName"]

GraphData[{"C4GroupGraph",{10,11}},"StandardNames"]

Primary

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

All

GraphData[{"C4GroupGraph",{10,11}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,11}}]]

Default embedding

GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,11}},"VertexList"],GraphData[{"C4GroupGraph",{10,11}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]]

RotateGraph[,Pi/2]

v={{0,0},{1,0},{1,1},{1/2,1},{0,1},{1/3,1/4},{1/2,1/4},{2/3,1/4},{1/3,3/4},{2/3,3/4}};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"C4GroupGraph",{10,11}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C4GroupGraph",{10,11}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"C4GroupGraph",{10,11}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C4GroupGraph",{10,11}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C4GroupGraph",{10,11}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C4GroupGraph",{10,11}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C4GroupGraph",{10,11}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,11}},"LCF"]

GraphData[{"C4GroupGraph",{10,11}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,11}},"Planar"]

GraphData[{"C4GroupGraph",{10,11}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"C4GroupGraph",{10,11}},{"RCN","CN"}]

GraphData[{"C4GroupGraph",{10,11}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"C4GroupGraph",{10,11}}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union)//Timing

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

GraphPlot@RotateGraph[,-2Pi/3]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"C4GroupGraph",{10,11}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,11}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,11}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

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

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

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

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

Circulant

GraphData[{"C4GroupGraph",{10,11}},"Circulant"]

GraphData[{"C4GroupGraph",{10,11}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C4GroupGraph",{10,11}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C4GroupGraph",{10,11}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C4GroupGraph",{10,11}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C4GroupGraph",{10,11}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,11}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,11}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,11}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,11}},"Halin"]

GraphData[{"C4GroupGraph",{10,11}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C4GroupGraph",{10,11}},"Rigid"]

GraphData[{"C4GroupGraph",{10,11}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C4GroupGraph",{10,11}},"Flexible"]

GraphData[{"C4GroupGraph",{10,11}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C4GroupGraph",{10,11}},"LCF"]

GraphData[{"C4GroupGraph",{10,11}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,11}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,11}},"LCFNotations"]

GraphData[{"C4GroupGraph",{10,11}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"C4GroupGraph",{10,11}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"C4GroupGraph",{10,11}}],Debug->True]//Timing

GraphData[{"C4GroupGraph",{10,11}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,11}},"Matchstick"]

GraphData[{"C4GroupGraph",{10,11}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,11}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"C4GroupGraph",{10,11}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"C4GroupGraph",{10,11}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"C4GroupGraph",{10,11}},"Polyhedral"]

GraphData[{"C4GroupGraph",{10,11}},"Graph",{"3D","Polyhedron"}]

{"C4GroupGraph", {10, 12}}

Names

GraphData[{"C4GroupGraph",{10,12}},"StandardName"]

GraphData[{"C4GroupGraph",{10,12}},"StandardNames"]

Primary

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

All

GraphData[{"C4GroupGraph",{10,12}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"C4GroupGraph",{10,12}}]]

Default embedding

GraphPlot[Graph[GraphData[{"C4GroupGraph",{10,12}},"VertexList"],GraphData[{"C4GroupGraph",{10,12}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]]

v={{0,0},{1,0},{1,1},{0,1},{1/2,1/4},{1/4,1/2},{3/4,1/2},{1/2,3/4},{5/8,7/16},{5/8,9/16}};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

DegenerateGraphEmbeddingTypes@g

Degenerate

GraphData[{"C4GroupGraph",{10,12}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"C4GroupGraph",{10,12}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"C4GroupGraph",{10,12}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"C4GroupGraph",{10,12}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"C4GroupGraph",{10,12}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"C4GroupGraph",{10,12}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"C4GroupGraph",{10,12}},"Hamiltonian"]

GraphData[{"C4GroupGraph",{10,12}},"LCF"]

GraphData[{"C4GroupGraph",{10,12}},"HamiltonianCycleCount"]

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

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

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

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

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

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

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"C4GroupGraph",{10,12}},"Planar"]

GraphData[{"C4GroupGraph",{10,12}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"C4GroupGraph",{10,12}},{"RCN","CN"}]

GraphData[{"C4GroupGraph",{10,12}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"C4GroupGraph",{10,12}}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union)//Timing

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"C4GroupGraph",{10,12}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"C4GroupGraph",{10,12}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"C4GroupGraph",{10,12}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

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

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

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

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

Circulant

GraphData[{"C4GroupGraph",{10,12}},"Circulant"]

GraphData[{"C4GroupGraph",{10,12}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"C4GroupGraph",{10,12}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"C4GroupGraph",{10,12}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"C4GroupGraph",{10,12}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"C4GroupGraph",{10,12}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"C4GroupGraph",{10,12}},"Line"]

LineGraphQ[GraphData[{"C4GroupGraph",{10,12}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"C4GroupGraph",{10,12}}]]

RecognizeGraph[%]

Halin

GraphData[{"C4GroupGraph",{10,12}},"Halin"]

GraphData[{"C4GroupGraph",{10,12}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"C4GroupGraph",{10,12}},"Rigid"]

GraphData[{"C4GroupGraph",{10,12}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"C4GroupGraph",{10,12}},"Flexible"]

GraphData[{"C4GroupGraph",{10,12}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"C4GroupGraph",{10,12}},"LCF"]

GraphData[{"C4GroupGraph",{10,12}},"HamiltonianCycleCount"]

GraphData[{"C4GroupGraph",{10,12}},"LCFSignature"]

GraphData[{"C4GroupGraph",{10,12}},"LCFNotations"]

GraphData[{"C4GroupGraph",{10,12}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"C4GroupGraph",{10,12}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"C4GroupGraph",{10,12}}],Debug->True]//Timing

GraphData[{"C4GroupGraph",{10,12}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"C4GroupGraph",{10,12}},"Matchstick"]

GraphData[{"C4GroupGraph",{10,12}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"C4GroupGraph",{10,12}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"C4GroupGraph",{10,12}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"C4GroupGraph",{10,12}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"C4GroupGraph",{10,12}},"Polyhedral"]

GraphData[{"C4GroupGraph",{10,12}},"Graph",{"3D","Polyhedron"}]

"Square with tangled hats" graph

https://houseofgraphs.org/graphs/49350

Smallest C4 Graph

Smallest graph whose automorphism group is the cyclic group of order 4. (Source: Arlinghaus, The Classification of Minimal Graphs with Given Abelian Automorphism Group, Figure 4.8a)

https://mathematica.stackexchange.com/questions/310123/graph-layout-graph-embedding-challenge-for-minimal-graph-with-mathbbz-4-sy

The minimal simple, connected graph with ℤ4 symmetry, aka 'square with tangled hats' graph

That seems to be wrong; commented Jan 14, 2025

SquareWithtangledHats=ImportString["I?deLStUg","Graph6"]

RecognizeGraph@SquareWithtangledHats

GraphData[{"C4GroupGraph",{10,3}},"Graph","Planar"]

GroupOrder[aut=GraphAutomorphismGroup[SquareWithtangledHats]]==4&&Length[GroupElements[aut]]==4

GraphIndex[SquareWithtangledHats]

Through[{VertexCount,EdgeCount}[]]

aut=GraphAutomorphismGroup[SquareWithtangledHats]

GroupOrder[aut]

CyclicGroupGraphQ[SquareWithtangledHats]

Enumeration

cyclicgroup=SortBy[GraphData["CyclicGroup"],GraphData[#,"V"]&]

AllTrue[cyclicgroup,CyclicGroupGraphQ[GraphData[#]]&]//Timing

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"CyclicGroup"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"CyclicGroup"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"CyclicGroup"],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"CyclicGroup"],{n,20}]

Antiprism

Entity["Graph",{"Antiprism",n}]["CyclicGroup"]

seq=Table[GraphData[{"Antiprism",n},"CyclicGroup"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"CyclicGroup"],{n,5}]

Barbell

seq=Table[GraphData[{"Barbell",n},"CyclicGroup"],{n,3,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"CyclicGroup"],{n,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"CyclicGroup"],{n,20}]

Book

seq=Table[GraphData[{"Book",n},"CyclicGroup"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"CyclicGroup"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"CyclicGroup"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"CyclicGroup"],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"CyclicGroup"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["CyclicGroup"]

seq=Table[GraphData[{"Complete",n},"CyclicGroup"],{n,30}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["CyclicGroup"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"CyclicGroup"],{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["CyclicGroup"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"CyclicGroup"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["CyclicGroup"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"CyclicGroup"],{n,10}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["CyclicGroup"]

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"CyclicGroup"],
False
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"CyclicGroup"],{n,2,12}]

Crown

seq=Table[GraphData[{"Crown",n},"CyclicGroup"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["CyclicGroup"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"CyclicGroup"],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["CyclicGroup"]

seq=Table[GraphData[{"Cycle",n},"CyclicGroup"],{n,3,30}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"CyclicGroup"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"CyclicGroup"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"CyclicGroup"],{n,3,20}]

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"CyclicGroup"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"CyclicGroup"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["CyclicGroup"]

seq=Table[GraphData[{"Empty",n},"CyclicGroup"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"CyclicGroup"],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"CyclicGroup"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"CyclicGroup"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"CyclicGroup"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"CyclicGroup"],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"CyclicGroup"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"CyclicGroup"],{n,3,20}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["CyclicGroup"]

seq=Table[GraphData[{"Grid",{n,n}},"CyclicGroup"],{n,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["CyclicGroup"]

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"CyclicGroup"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["CyclicGroup"]

seq=Table[GraphData[{"Grid",{n,n,n}},"CyclicGroup"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["CyclicGroup"]

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"CyclicGroup"],
False
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"CyclicGroup"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"CyclicGroup"],{n,6}]

Helm

seq=Table[GraphData[{"Helm",n},"CyclicGroup"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["CyclicGroup"]

seq=Table[GraphData[{"Hypercube",n},"CyclicGroup"],{n,0,10}]

KC

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KC",{m,n}},"CyclicGroup"],
False
},{n,3,10},{m,10}],1],{_,x_,x_}]

Keller

Entity["Graph",{"Keller",n}]["CyclicGroup"]

seq=Table[GraphData[{"Keller",n},"CyclicGroup"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"CyclicGroup"],{n,20}]

King m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"CyclicGroup"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["CyclicGroup"]

seq=Table[GraphData[{"Knight",{n,n}},"CyclicGroup"],{n,20}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["CyclicGroup"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"CyclicGroup"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

KP

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KP",{m,n}},"CyclicGroup"],
False
},{n,10},{m,10}],1],{_,x_,x_}]

Ladder

Entity["Graph",{"Ladder",n}]["CyclicGroup"]

seq=Table[GraphData[{"Ladder",n},"CyclicGroup"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"CyclicGroup"],{n,20}]

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"CyclicGroup"],{n,11}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"CyclicGroup"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"CyclicGroup"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["CyclicGroup"]

seq=Table[GraphData[{"MoebiusLadder",n},"CyclicGroup"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["CyclicGroup"]

seq=Table[GraphData[{"Mycielski",n},"CyclicGroup"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["CyclicGroup"]

seq=Table[GraphData[{"Odd",n},"CyclicGroup"],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"CyclicGroup"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["CyclicGroup"]

seq=Table[GraphData[{"Path",n},"CyclicGroup"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"CyclicGroup"],{n,20}]

Pell

seq=Table[GraphData[{"Pell",n},"CyclicGroup"],{n,9}]

PlummerToft

seq=Table[GraphData[{"PlummerToft",n},"CyclicGroup"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["CyclicGroup"]

seq=Table[GraphData[{"Prism",n},"CyclicGroup"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"CyclicGroup"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"CyclicGroup"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"CyclicGroup"],{n,20}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"CyclicGroup"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"CyclicGroup"],{n,7}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"CyclicGroup"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"CyclicGroup"],{n,5}]

StackedBook m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedBook",{m,n}},"CyclicGroup"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

StackedBook n×n

seq=Table[GraphData[{"StackedBook",{n,n}},"CyclicGroup"],{n,10}]

StackedPrism m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"StackedPrism",{m,n}},"CyclicGroup"],
False
},{m,3,8},{n,5}],1],{_,x_,x_}]

StackedPrism n×n

seq=Table[GraphData[{"StackedPrism",{n,n}},"CyclicGroup"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["CyclicGroup"]

seq=Table[GraphData[{"Star",n},"CyclicGroup"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"CyclicGroup"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"CyclicGroup"],{n,3,20}]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"CyclicGroup"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"CyclicGroup"],{n,3,20}]

Transposition

Entity["Graph",{"Transposition",n}]["CyclicGroup"]

seq=Table[GraphData[{"Transposition",n},"CyclicGroup"],{n,6}]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["CyclicGroup"]

seq=Table[GraphData[{"Trapezohedron",n},"CyclicGroup"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"CyclicGroup"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"CyclicGroup"],{n,0,20}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"CyclicGroup"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"CyclicGroup"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"CyclicGroup"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"CyclicGroup"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"CyclicGroup"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"CyclicGroup"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"CyclicGroup"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["CyclicGroup"]

seq=Table[GraphData[{"Wheel",n},"CyclicGroup"],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"CyclicGroup"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"CyclicGroup"],{n,2,20}]

WhiteCamel n×n

seq=Table[GraphData[{"Bishop",{n,n}},"CyclicGroup"],{n,{5}}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"CyclicGroup"],{n,20}]

GraphData

GraphDataClassString

GraphDataClassString["CyclicGroup"]

GraphDataString

file=OpenWrite["~/smallest-cyclic.m"]

C3GroupGraphs9=If[PlanarGraphQ[#],PlanarGraph[#],#]&/@{,,,}

Do[WriteString[file,GraphDataString[C3GroupGraphs9[[i]],
"StandardName"->{"C3GroupGraph",{9,i}},
"AlternateStandardNames"->{{"Z3GroupGraph",{9,i}}},
"Name"->"C3 group graph (9,"<>ToString[i]<>")",
"AlternateNames"->{"Z3 group graph (9,"<>ToString[i]<>")"},
"Information"->"GraphAutomorphism",
"Skip"->{"ConstructionNumber","CyclicEdgeCuts","EdgeCuts","GracefulLabelings","Minors","QuadraticEmbeddingConstant"}
]],{i,3,4}]

Close[file]

file=OpenWrite["~/smallest-cyclic.m"]

C4GroupGraphs10=If[PlanarGraphQ[#],PlanarGraph[#],#]&/@{,,}

file=OpenWrite["~/smallest-cyclic.m"]

Do[WriteString[file,GraphDataString[C4GroupGraphs[[i]][[2]],
"StandardName"->{"C4GroupGraph",{10,i}},
"AlternateStandardNames"->{If[i==3,"SquareWithTangledHatsGraph",Nothing],{"Z4GroupGraph",{10,i}}},
"Name"->"C4 group graph (10,"<>ToString[i]<>")",
"AlternateNames"->{If[i==3,"square with tangled hats graph",Nothing],"Z4 group graph (10,"<>ToString[i]<>")"},
"Information"->"CyclicGroupGraph",
"Skip"->{"ConstructionNumber","CyclicEdgeCuts","EdgeCuts","ErdosSequence","GracefulLabelings","Minors","PinnacleSets","QuadraticEmbeddingConstant"}
]],{i,12}]

Close[file]