Cubic Vertex-Transitive Graph

Author

Eric W. Weisstein
March 3, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/CubicVertex-TransitiveGraph.nb.

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

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

Read and Wilson

Import["/Users/eww/Downloads/Untitled 3.pdf"]

{,,}

Counts

l={First[#],Length[#]}&/@Split[Sort[GraphData[#,"VertexCount"]&/@GraphData["CubicVertexTransitive"]]]

l2=Take[l,{2,14}]

-Subtract@@@Partition[First/@l2,2,1]

Last/@l2

Figures

New

ct="Ct"<>ToString[#]&/@Range[81]

GraphicsGrid[Partition[Show[GraphData[#],PlotLabel->TextCell["Ct"<>ToString["Ct"/.GraphData[#,"NotationRules"]]<>"\n"<>GraphData[#,"Name"],PageWidth->90,TextAlignment->Center],BaseStyle->{FontSlant->"Italic"}]&/@Take[ct,25],5,5,{1,1},{}],ImageSize->500]

Old

l=Select[GraphData["CubicVertexTransitive"],StringQ[s="CubicVertexTransitive"/.GraphData[#,"NotationRules"]]&&StringTake[s,2]=="Ct"&]

g=DeleteCases[Sort[{GraphData[#,"VertexCount"],GraphData[#,"FullName"],"CubicVertexTransitive"/.GraphData[#,"NotationRules"],GraphData[#,"Name"]}&/@l,ToExpression[StringDrop[#1[[3]],2]]<=ToExpression[StringDrop[#2[[3]],2]]&],{0,__}]

Show[GraphicsArray[Partition[Block[{$DisplayFunction=Identity},ShowGraph[CombinatoricaGraph[#[[2]]],AspectRatio->Automatic,PlotLabel->ToString[#[[1]]]<>" "<>#[[3]]]&/@Take[g,40]],8,8,{1,1},{}]],GraphicsSpacing->{0,.1},PlotRange->All]

Show[GraphicsArray[Partition[Block[{$DisplayFunction=Identity},ShowGraph[CombinatoricaGraph[#[[2]]],AspectRatio->Automatic,PlotLabel->ToString[#[[1]]]<>" "<>#[[3]]]&/@Take[g,{41,-1}]],8,8,{1,1},{}]],GraphicsSpacing->{-.1,.1},PlotRange->All]

Table

DeleteCases[Sort[("Ct"/.GraphData[#,"NotationRules"])&/@GraphData[{"Connected","Cubic","VertexTransitive"}]],"Ct"|None]

Complement[Range[80],%]

TableForm[Reverse/@Sort[{"Ct"/.GraphData[#,"NotationRules"],GraphData[#,"Name"],GraphData[#,"V"]}&/@GraphData[{"Connected","Cubic","VertexTransitive"},;;34]],TableDepth->2]

Construction

<<MathWorld`Graphs`

Table[n->RecognizeGraph@CubicVertexTransitiveGraph[n],{n,8,40,2}]

And@@IsomorphicGraphQ@@@Table[{HoneycombToroidalGraph[1,n,5],CubicVertexTransitiveGraph[n]},{n,8,40,2}]

{"CubicTransitive", 1} == "TetrahedralGraph"

GraphData[{"CubicTransitive",1},"StandardName"]

{"CubicTransitive", 2} == {"Prism", 3}

GraphData[{"CubicTransitive",2},"StandardName"]

{"CubicTransitive", 3} = "UtilityGraph"

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

{"CubicTransitive", 4} == "WagnerGraph"

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

{"CubicTransitive", 5} == "CubicalGraph"

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

{"CubicTransitive", 6} == {"Prism", 5 }

GraphData[{"CubicTransitive",6},"StandardName"]

{"CubicTransitive", 7} == {"MoebiusLadder", 5}

GraphData[{"CubicTransitive",7},"StandardName"]

{"CubicTransitive", 8} == "PetersenGraph"

GraphData[{"CubicTransitive",8},"StandardName"]

{"CubicTransitive", 9} == {"Prism", 6}

GraphData[{"CubicTransitive",9},"StandardName"]

{"CubicTransitive", 10} == {"MoebiusLadder", 6}

GraphData[{"CubicTransitive",10},"StandardName"]

{"CubicTransitive", 11} == "TruncatedTetrahedralGraph"

GraphData[{"CubicTransitive",11},"StandardName"]

{"CubicTransitive", 12} == "FranklinGraph"

GraphData[{"CubicTransitive",12},"StandardName"]

{"CubicTransitive", 13} == {"Prism", 7}

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

{"CubicTransitive", 14} == {"MoebiusLadder", 7}

GraphData[{"CubicTransitive",14},"StandardName"]

{"CubicTransitive", 15} == "HeawoodGraph"

GraphData[{"CubicTransitive",15},"StandardName"]

{"CubicTransitive", 16} == {"Prism", 8}

GraphData[{"CubicTransitive",16},"StandardName"]

{"CubicTransitive", 17} == {"MoebiusLadder", 8}

GraphData[{"CubicTransitive",17},"StandardName"]

{"CubicTransitive", 18} == "MoebiusKantorGraph"

GraphData[{"CubicTransitive",18},"StandardName"]

{"CubicTransitive", 19} == {"CrossedPrism", 8}

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

{"CubicTransitive", 20}

Names

GraphData[{"CubicTransitive",20},"StandardName"]

GraphData[{"CubicTransitive",20},"StandardNames"]

Primary

GraphData[{"CubicTransitive",20}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

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

RecognizeGraph@g

All

GraphData[{"CubicTransitive",20},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",20},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",20},"Edges"]

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

RecognizeGraph@g

Graph[GraphData[{"CubicTransitive",20},"Edges"]]

CVT construction

GraphPlot[GraphData[{"CubicTransitive",20},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

g=CubicVertexTransitiveGraph[18]

RecognizeGraph@g

GeneralizedHoneycombGraph construction

With[{n=18},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",20}}]]//Timing

gs=GeneralizedHoneycombGraph[18,#]&/@{3,5,7}

RecognizeGraph/@gs

Degenerate

GraphData[{"CubicTransitive",20},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",20},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicTransitive",20},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",20},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",20},"Planar"]

GraphData[{"CubicTransitive",20},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",20},{"RCN","CN"}]

GraphData[{"CubicTransitive",20},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

GraphPlot@

GraphPlot@HighlightGraph[RotateGraph[GraphicsToGraph@,.1],{19,20,21}]

RegionIntersection[InfiniteLine@v[[{11,12}]],Line@v[[{7,9}]]][[1,1]]

v=Join[c=CirclePoints[3],Mean/@Partition[c,2,1,1],CirclePoints[2/3,3],c2=CirclePoints[1/3,3],Mean/@Partition[c2,2,1,1]];
v=Join[v,Table[RotationMatrix[2Pi i/3].{-(2/(3 (Sqrt[3]))),-(1/3)},{i,0,2}]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,4,2,5,3,6,1,7,17,8,18,9,16,7],{6,15},{4,13},{5,14},e[16,12,14,11],e[18,11,13,10],e[12,15,10,17],{2,8},{3,9}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

RectilinearCrossingCount@g

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",20},"Circulant"]

GraphData[{"CubicTransitive",20},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",20},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",20}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",20}&]

RootGraph[GraphData[{"CubicTransitive",20}]]

Halin

GraphData[{"CubicTransitive",20},"Halin"]

GraphData[{"CubicTransitive",20},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",20},"Rigid"]

GraphData[{"CubicTransitive",20},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",20},"Flexible"]

GraphData[{"CubicTransitive",20},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",20},"LCF"]

GraphData[{"CubicTransitive",20},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",20},"LCFSignature"]

GraphData[{"CubicTransitive",20},"LCFNotations"]

GraphData[{"CubicTransitive",20},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",20}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

UnitDistance

GraphData[{"CubicTransitive",20},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",20}],Debug->True]//Timing

GraphData[{"CubicTransitive",20},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",20},"VertexList"],GraphData[{"CubicTransitive",20},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",20},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",20}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",20},"Matchstick"]

GraphData[{"CubicTransitive",20},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",20},"Edges"]]

3D All

GraphData[{"CubicTransitive",20},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",20},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",20},"Polyhedral"]

{"CubicTransitive", 21} == {"Prism", 9}

GraphData[{"CubicTransitive",21},"StandardName"]

{"CubicTransitive", 22} == {"MoebiusLadder",  9}

GraphData[{"CubicTransitive",22},"StandardName"]

{"CubicTransitive", 23}

Names

GraphData[{"CubicTransitive",23},"StandardName"]

GraphData[{"CubicTransitive",23},"StandardNames"]

Primary

GraphData[{"CubicTransitive",23}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

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

RecognizeGraph@g

All

GraphData[{"CubicTransitive",23},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",23},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",23},"Edges"]

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

RecognizeGraph[g]

GraphPlot[GraphData[{"CubicTransitive",23},"Edges"],GraphLayout->"SpringEmbedding"]

Degenerate

GraphData[{"CubicTransitive",23},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",23},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicTransitive",23},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",23},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",23},"Planar"]

GraphData[{"CubicTransitive",23},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",23},{"RCN","CN"}]

GraphData[{"CubicTransitive",23},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

GraphPlot@RotateGraph[,-Pi/2]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@RotateGraph[,-3Pi/7]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@RotateGraph[,Pi/5]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@

1/2/3+1/4

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

gs=UnlabelGraph/@{,,,}

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",23},"Circulant"]

GraphData[{"CubicTransitive",23},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",23},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",23}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",23}&]

RootGraph[GraphData[{"CubicTransitive",23}]]

GraphData[{"EdgeTransitive",{15,3}},"Graph","All"]

Halin

GraphData[{"CubicTransitive",23},"Halin"]

GraphData[{"CubicTransitive",23},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",23},"Rigid"]

GraphData[{"CubicTransitive",23},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",23},"Flexible"]

GraphData[{"CubicTransitive",23},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",23},"LCF"]

GraphData[{"CubicTransitive",23},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",23},"LCFSignature"]

GraphData[{"CubicTransitive",23},"LCFNotations"]

GraphData[{"CubicTransitive",23},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",23}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

UnitDistance

GraphData[{"CubicTransitive",23},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",23}],Debug->True]//Timing

GraphData[{"CubicTransitive",23},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",23},"VertexList"],GraphData[{"CubicTransitive",23},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

gs={,RotateGraph[,{5,8}]}

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",23},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",23}],TimeConstraint->300,"Results"->All]//Timing}

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

gs={,,,,,,};

Matchstick

GraphData[{"CubicTransitive",23},"Matchstick"]

GraphData[{"CubicTransitive",23},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",23},"Edges"]]

3D All

GraphData[{"CubicTransitive",23},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",23},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",23},"Polyhedral"]

{"CubicTransitive", 24} == "PappusGraph"

GraphData[{"CubicTransitive",24},"StandardName"]

{"CubicTransitive", 25}

Names

GraphData[{"CubicTransitive",25},"StandardName"]

GraphData[{"CubicTransitive",25},"StandardNames"]

Primary

GraphData[{"CubicTransitive",25}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

All

GraphData[{"CubicTransitive",25},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",25},"EdgeList"]]

Default embedding

GraphPlot[GraphData[{"CubicTransitive",25},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph[g]

GraphPlot[GraphData[{"CubicTransitive", 25},"EdgeList"]]

GraphPlot@GraphData[{"CubicTransitive",25},"Edges"]

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

RecognizeGraph[g]

GraphPlot@RotateGraph[GraphicsToGraph@,Pi/2]

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

RecognizeGraph[g]

gs=UnlabelGraph/@{,,}

CVT construction

GraphPlot[GraphData[{"CubicTransitive",25},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

g=CubicVertexTransitiveGraph[20]

RecognizeGraph[g]

GeneralizedHoneycombGraph construction

With[{n=20},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",_}}]]//Timing

g=GeneralizedHoneycombGraph[20,3]

RecognizeGraph@g

Degenerate

GraphData[{"CubicTransitive",25},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",25},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicTransitive",25},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",25},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",25},"Planar"]

GraphData[{"CubicTransitive",25},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",25},{"RCN","CN"}]

GraphData[{"CubicTransitive",25},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

GraphPlot@RotateGraph[,-Pi/7]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",25}],"CrossingNumber"->4]

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",25}],"CrossingNumber"->cn,RandomSeed->i],{i,250}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",25},"Circulant"]

GraphData[{"CubicTransitive",25},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",25},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",25}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",25}&]

RootGraph[GraphData[{"CubicTransitive",25}]]

Halin

GraphData[{"CubicTransitive",25},"Halin"]

GraphData[{"CubicTransitive",25},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",25},"Rigid"]

GraphData[{"CubicTransitive",25},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",25},"Flexible"]

GraphData[{"CubicTransitive",25},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",25},"LCF"]

GraphData[{"CubicTransitive",25},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",25},"LCFSignature"]

GraphData[{"CubicTransitive",25},"LCFNotations"]

GraphData[{"CubicTransitive",25},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",25}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",25},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",25}],Debug->True]//Timing

GraphData[{"CubicTransitive",25},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",25},"VertexList"],GraphData[{"CubicTransitive",25},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

GraphPlot@

GraphicsToGraph@

UnitDistanceEmbeddingRefine[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",25},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",25}],TimeConstraint->300,"Results"->All]//Timing}

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

gs={,};

Matchstick

GraphData[{"CubicTransitive",25},"Matchstick"]

GraphData[{"CubicTransitive",25},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",25},"Edges"]]

3D All

GraphData[{"CubicTransitive",25},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",25},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",25},"Polyhedral"]

{"CubicTransitive", 26} == "DesarguesGraph"

GraphData[{"CubicTransitive",26},"StandardName"]

{"CubicTransitive", 27} == "DodecahedralGraph"

GraphData[{"CubicTransitive",27},"StandardName"]

{"CubicTransitive", 28}

Names

GraphData[{"CubicTransitive",28},"StandardName"]

GraphData[{"CubicTransitive",28},"StandardNames"]

Primary

GraphData[{"CubicTransitive",28}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

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

RecognizeGraph@g

All

GraphData[{"CubicTransitive",28},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",28},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",28},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",28},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",28},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicTransitive",28},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",28},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",28},"Planar"]

GraphData[{"CubicTransitive",28},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",28},{"RCN","CN"}]

GraphData[{"CubicTransitive",28},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",28}],"CrossingNumber"->cn,RandomSeed->i],{i,250}]//Union

GraphPlot@RotateGraph[,-Pi/2]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",28}],"CrossingNumber"->4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",28},"Circulant"]

GraphData[{"CubicTransitive",28},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",28},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",28}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",28}&]

RootGraph[GraphData[{"CubicTransitive",28}]]

Halin

GraphData[{"CubicTransitive",28},"Halin"]

GraphData[{"CubicTransitive",28},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",28},"Rigid"]

GraphData[{"CubicTransitive",28},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",28},"Flexible"]

GraphData[{"CubicTransitive",28},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",28},"LCF"]

GraphData[{"CubicTransitive",28},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",28},"LCFSignature"]

GraphData[{"CubicTransitive",28},"LCFNotations"]

GraphData[{"CubicTransitive",28},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",28}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",28},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",28}],Debug->True]//Timing

GraphData[{"CubicTransitive",28},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",28},"VertexList"],GraphData[{"CubicTransitive",28},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

LabelGraph@

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",28},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",28}],TimeConstraint->300,"Results"->All]//Timing}

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

gs={};

Matchstick

GraphData[{"CubicTransitive",28},"Matchstick"]

GraphData[{"CubicTransitive",28},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",28},"Edges"]]

3D All

GraphData[{"CubicTransitive",28},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",28},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",28},"Polyhedral"]

{"CubicTransitive", 29} == {"CrossedPrism", 10}

GraphData[{"CubicTransitive",29},"StandardName"]

{"CubicTransitive", 30} == {"Prism", 10}

GraphData[{"CubicTransitive",30},"StandardName"]

{"CubicTransitive", 31} == {"MoebiusLadder", 10}

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

{"CubicTransitive", 32}

Names

GraphData[{"CubicTransitive",32},"StandardName"]

GraphData[{"CubicTransitive",32},"StandardNames"]

Primary

GraphData[{"CubicTransitive",32}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

All

GraphData[{"CubicTransitive",32},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",32},"EdgeList"]]

Default embedding

GraphData[{"CubicTransitive",32},"V"]

GraphPlot[GraphData[{"CubicTransitive",32},"Edges"]]

GraphPlot@RotateGraph[GraphicsToGraph@,Pi/2]

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

RecognizeGraph@g

Degenerate

GraphData[{"CubicTransitive",32},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",32},"Graph","Degenerate"]

CVT construction

g=CubicVertexTransitiveGraph[22]

RecognizeGraph@g

GeneralizedHoneycombGraph construction

With[{n=22},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",_}}]]//Timing

gs=GeneralizedHoneycombGraph[22,#]&/@{3,5,9}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",32},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",32},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",32},"Planar"]

GraphData[{"CubicTransitive",32},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",32},{"RCN","CN"}]

GraphData[{"CubicTransitive",32},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

GraphPlot@RotateGraph[,-3Pi/8]

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

RecognizeGraph@g

RectilinearCrossingCount@g

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

GraphPlot@RotateGraph[,5Pi/7]

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

RecognizeGraph[g]

gs=UnlabelGraph/@{,}

RectilinearCrossingCount[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",32},"Circulant"]

GraphData[{"CubicTransitive",32},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",32},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",32}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",32}&]

RootGraph[GraphData[{"CubicTransitive",32}]]

Halin

GraphData[{"CubicTransitive",32},"Halin"]

GraphData[{"CubicTransitive",32},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",32},"Rigid"]

GraphData[{"CubicTransitive",32},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",32},"Flexible"]

GraphData[{"CubicTransitive",32},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",32},"LCF"]

GraphData[{"CubicTransitive",32},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",32},"LCFSignature"]

GraphData[{"CubicTransitive",32},"LCFNotations"]

GraphData[{"CubicTransitive",32},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",32}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

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

UnitDistance

GraphData[{"CubicTransitive",32},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",32}],Debug->True]//Timing

GraphData[{"CubicTransitive",32},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",32},"VertexList"],GraphData[{"CubicTransitive",32},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",32},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",32}],TimeConstraint->300,"Results"->All]//Timing}

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

gs={,,,};

Matchstick

GraphData[{"CubicTransitive",32},"Matchstick"]

GraphData[{"CubicTransitive",32},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",32},"Edges"]]

3D All

GraphData[{"CubicTransitive",32},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",32},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",32},"Polyhedral"]

{"CubicTransitive", 33} == {"MoebiusLadder", 11}

GraphData[{"CubicTransitive",33},"StandardName"]

{"CubicTransitive", 34} == {"Prism", 11}

GraphData[{"CubicTransitive",34},"StandardName"]

{"CubicTransitive", 35}

Names

GraphData[{"CubicTransitive",35},"StandardName"]

GraphData[{"CubicTransitive",35},"StandardNames"]

Primary

GraphData[{"CubicTransitive",35}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

All

GraphData[{"CubicTransitive",35},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",35},"EdgeList"]]

Default embedding

GraphData[{"CubicTransitive",35},"V"]

GraphPlot@GraphData[{"CubicTransitive",35},"Edges"]

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

RecognizeGraph[g]

GraphPlot[GraphData[{"CubicTransitive",35},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

Degenerate

GraphData[{"CubicTransitive",35},"Graph","Degenerate"]//StyleGraphs

GeneralizedHoneycombGraph construction

With[{n=24},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",35}}]]//Timing

gs=GeneralizedHoneycombGraph[24,#]&/@{7,9}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",35},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",35},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",35},"Planar"]

GraphData[{"CubicTransitive",35},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",35},{"RCN","CN"}]

GraphData[{"CubicTransitive",35},"Graph","MinimalCrossing"]//StyleGraphs[#,VertexSize->{"Scaled",.02}]&

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

GraphPlot@

GraphData[{"CubicTransitive",35},"V"]

v=Join[CirclePoints[6],CirclePoints[{r,q},3]];

RegionDistance[Line@v[[{8,3}]],v[[7]]]

FullSimplify[SquaredEuclideanDistance@@v[[{5,8}]]==SquaredEuclideanDistance@@v[[{5,9}]]/4^2,0<r<1]

FullSimplify[Solve[(1/2) (Sqrt[3]) (Sqrt[(((r^2) (((r-2 Cos[q]))^2))/(1+(r^2)-r Cos[q]+(Sqrt[3]) r Sin[q]))])==0&&((Abs[r Cos[(π/6)-q]])^2)+((Abs[-1+r Sin[(π/6)-q]])^2)==16 (((Abs[r Cos[(π/6)+q]])^2)+((Abs[-1+r Sin[(π/6)+q]])^2))&&0<r<1,{q,r}]]

N[ArcTan[(5/(Sqrt[3]))]]

N[%]

5Pi/12.

v[[9]]+(v[[5]]-v[[8]])//FullSimplify

v=Join[CirclePoints[6],CirclePoints[{(Sqrt[(3/7)]),ArcTan[(5/(Sqrt[3]))]},3],Table[RotationMatrix[2Pi/3 i].{(1/14),-((3 (Sqrt[3]))/14)},{i,0,2}],CirclePoints[{1/4,x},3]];

RegionDistance[Line@v[[{2,15}]],v[[13]]]

Solve[(1/8) (Sqrt[3]) (Sqrt[((33-8 Cos[x]-16 Cos[2 x]-8 (Sqrt[3]) Sin[x]+16 (Sqrt[3]) Sin[2 x])/(17+4 Cos[x]-4 (Sqrt[3]) Sin[x]))])==0&&0<x<2π,x]//FullSimplify

N[%]

v=Join[CirclePoints[6],CirclePoints[{(Sqrt[(3/7)]),ArcTan[(5/(Sqrt[3]))]},3],Table[RotationMatrix[2Pi/3 i].{(1/14),-((3 (Sqrt[3]))/14)},{i,0,2}],CirclePoints[{1/4,2 (π+ArcTan[(NumericalApproximation[Root, (RowDefault["-0.202", FEExpressionsNumericalApproximationElider]), Root[9-222 ((#1)^2)+25 ((#1)^4)&,2], ])])},3],CirclePoints[{1/6,x},3]];

RegionDistance[Line@v[[{13,15}]],v[[18]]]

Solve[((Sqrt[(((-3 (Sqrt[3])+4 Cos[(π/6)-x+2 ArcTan[(NumericalApproximation[Root, (RowDefault["-0.202", FEExpressionsNumericalApproximationElider]), Root[9-222 ((#1)^2)+25 ((#1)^4)&,2], ])]]+4 Sin[x-2 ArcTan[(NumericalApproximation[Root, (RowDefault["-0.202", FEExpressionsNumericalApproximationElider]), Root[9-222 ((#1)^2)+25 ((#1)^4)&,2], ])]]))^2)])/(24 (Sqrt[3])))==0&&0<x<2π,x,Reals]//FullSimplify

N[%]

v=Join[CirclePoints[6],CirclePoints[{(Sqrt[(3/7)]),ArcTan[(5/(Sqrt[3]))]},3],Table[RotationMatrix[2Pi/3 i].{(1/14),-((3 (Sqrt[3]))/14)},{i,0,2}],CirclePoints[{1/4,2 (π+ArcTan[(NumericalApproximation[Root, (RowDefault["-0.202", FEExpressionsNumericalApproximationElider]), Root[9-222 ((#1)^2)+25 ((#1)^4)&,2], ])])},3],CirclePoints[{1/6,2 (π-ArcCot[8 (Sqrt[3])+5 (Sqrt[7])])},3],CirclePoints[{1/12,q},3]];

RegionDistance[Line@v[[{18,20}]],v[[21]]]

RegionDistance[Line@v[[{18,20}]],v[[21]]]

FindRoot[((27-8 Cos[q+2 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]-8 Cos[2 q+4 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]-16 Sin[(π/6)-2 q-4 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]+8 Sin[(π/6)-q-2 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]-16 Sin[(π/6)+q+2 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]+8 Sin[(π/6)+2 q+4 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]])),{q,0}]

Numerator[Together@TrigExpand[((27-8 Cos[q+2 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]-8 Cos[2 q+4 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]-16 Sin[(π/6)-2 q-4 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]+8 Sin[(π/6)-q-2 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]-16 Sin[(π/6)+q+2 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]+8 Sin[(π/6)+2 q+4 ArcCot[8 (Sqrt[3])+5 (Sqrt[7])]]))]]//FullSimplify

Solve[%96==0&&0<q<2π,q]//FullSimplify

N[%99]

5.938-2π

v=Join[CirclePoints[6],CirclePoints[{(Sqrt[(3/7)]),ArcTan[(5/(Sqrt[3]))]},3],Table[RotationMatrix[2Pi/3 i].{(1/14),-((3 (Sqrt[3]))/14)},{i,0,2}],CirclePoints[{1/4,2 (π+ArcTan[(NumericalApproximation[Root, (RowDefault["-0.202", FEExpressionsNumericalApproximationElider]), Root[9-222 ((#1)^2)+25 ((#1)^4)&,2], ])])},3],CirclePoints[{1/6,2 (π-ArcCot[8 (Sqrt[3])+5 (Sqrt[7])])},3],c=CirclePoints[{1/12,2 (π+ArcTan[(NumericalApproximation[Root, (RowDefault["-0.174", FEExpressionsNumericalApproximationElider]), Root[25-830 ((#1)^2)+169 ((#1)^4)&,2], ])])},3],Mean/@Partition[c,2,1,1]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,3,4,5,6,1,9,11,7],e[3,7,12,8],e[5,8,10,9],{4,14},{6,15},{2,13},e[15,17,14],e[15,18,13],e[14,16,13],e[18,21,23,20],e[17,20,22,19],e[21,24,19,16],{12,23},{22,11},{10,24}},VertexCoordinates->v,VertexLabels->None,VertexSize->Automatic]

RecognizeGraph@g

((EuclideanDistance@@v[[{5,9}]])/(EuclideanDistance@@v[[{5,8}]]))//N

Circulant

GraphData[{"CubicTransitive",35},"Circulant"]

GraphData[{"CubicTransitive",35},"NotationRules","Circulant"]

GraphData[{"CubicTransitive",35},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",35},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",35}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",35}&]

RootGraph[GraphData[{"CubicTransitive",35}]]

Halin

GraphData[{"CubicTransitive",35},"Halin"]

GraphData[{"CubicTransitive",35},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",35},"Rigid"]

GraphData[{"CubicTransitive",35},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",35},"Flexible"]

GraphData[{"CubicTransitive",35},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",35},"LCF"]

GraphData[{"CubicTransitive",35},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",35},"LCFSignature"]

GraphData[{"CubicTransitive",35},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",35}],All][[All,All,1]]]//Timing

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

gs=LCFGraph@@@lcf//StyleGraphs

gs=Join[With[{g=BilateralLCFEmbedding[#]},If[MissingQ[g],#,g]]&/@LCFGraph@@@DeleteCases[lcf,{_,1}],DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]]

UnitDistance

GraphData[{"CubicTransitive",35},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",35}],Debug->True]//Timing

GraphData[{"CubicTransitive",35},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",35},"VertexList"],GraphData[{"CubicTransitive",35},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"CubicTransitive",35},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",35},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",35}],TimeConstraint->300,"Results"->All]//Timing}

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

gs={}

Matchstick

GraphData[{"CubicTransitive",35},"Matchstick"]

GraphData[{"CubicTransitive",35},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",35},"Edges"]]

3D All

GraphData[{"CubicTransitive",35},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",35},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",35},"Polyhedral"]

GraphData[{"CubicTransitive",35},"Graph",{"3D","Polyhedron"}]

{"CubicTransitive", 36}

Names

GraphData[{"CubicTransitive",36},"StandardName"]

GraphData[{"CubicTransitive",36},"StandardNames"]

Primary

GraphData[{"CubicTransitive",36}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

All

GraphData[{"CubicTransitive",36},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",36},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",36},"Edges"]

GraphData[{"CubicTransitive",36},"V"]

Degenerate

GraphData[{"CubicTransitive",36},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",36},"Graph","Degenerate"]

CVT construction

GraphPlot[GraphData[{"CubicTransitive",36},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

g=CubicVertexTransitiveGraph[24]

RecognizeGraph[g]

GeneralizedHoneycombGraph construction

With[{n=24},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",36}}]]//Timing

gs=GeneralizedHoneycombGraph[24,#]&/@{3,5}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",36},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",36},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",36},"Planar"]

GraphData[{"CubicTransitive",36},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",36},{"RCN","CN"}]

GraphData[{"CubicTransitive",36},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",36}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",36}],"CrossingNumber"->4]

v[[21,2]]/v[[4,2]]//FullSimplify

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",36},"Circulant"]

GraphData[{"CubicTransitive",36},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",36},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",36}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",36}&]

RootGraph[GraphData[{"CubicTransitive",36}]]

Halin

GraphData[{"CubicTransitive",36},"Halin"]

GraphData[{"CubicTransitive",36},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",36},"Rigid"]

GraphData[{"CubicTransitive",36},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",36},"Flexible"]

GraphData[{"CubicTransitive",36},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",36},"LCF"]

GraphData[{"CubicTransitive",36},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",36},"LCFSignature"]

GraphData[{"CubicTransitive",36},"LCFNotations"]

GraphData[{"CubicTransitive",36},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",36}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",36},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",36}],Debug->True]//Timing

GraphData[{"CubicTransitive",36},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",36},"VertexList"],GraphData[{"CubicTransitive",36},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",36},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",36}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",36},"Matchstick"]

GraphData[{"CubicTransitive",36},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",36},"Edges"]]

3D All

GraphData[{"CubicTransitive",36},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",36},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",36},"Polyhedral"]

{"CubicTransitive", 37}

Names

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

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

Primary

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

Read and Wilson

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

RecognizeGraph@g

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",37},"EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

GraphPlot[GraphData[{"CubicTransitive",37},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

Degenerate

GraphData[{"CubicTransitive",37},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",37},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicTransitive",37},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",37},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",37},"Planar"]

GraphData[{"CubicTransitive",37},"Graph","Planar"]//StyleGraphs

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

GraphData[{"CubicTransitive",37},"V"]

GraphPlot@RotateGraph[,3Pi/5]

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

RecognizeGraph@g

RectilinearCrossingCount@g

GraphPlot@RotateGraph[,Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

gs=UnlabelGraph/@{,}

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",37}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",37}],"CrossingNumber"->6]

GraphPlot@HighlightGraph[RotateGraph[GraphicsToGraph@,{10,7}],Range[25,28]]

v={If[#>3,#-1,#],#2}&@@@{{0,0},{8,0},{8,7},{0,7},{1,1},{2,1},{6,1},{7,1},{2,2},{4,2},{6,2},{2,3},{3,3},{5,3},{6,3},{2,4},{3,4},{5,4},{6,4},{2,5},{4,5},{6,5},{1,6},{2,6},{6,6},{7,6}};
g=EdgeAdd[VertexDelete[Graph[Range[Length[v]],UndirectedEdge@@@{e[1,7,11,15,26,3,24,20,16,5,1,4,25,26],e[5,6,9,12,23,4],{23,24},e[25,22,19,8,2,6],{7,8},e[10,14,18,21,17,13,10],e[9,10,11],e[20,21,22],{2,3},{16,17},{18,19},{12,13},{14,15}},VertexCoordinates->v,VertexLabels->Automatic],{10,21}],UndirectedEdge@@@{{18,20},{17,22},{13,11},{9,14}}]

RecognizeGraph[g]

Circulant

GraphData[{"CubicTransitive",37},"Circulant"]

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

Line graph

GraphData[{"CubicTransitive",37},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",37}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",37}&]

RootGraph[GraphData[{"CubicTransitive",37}]]

Halin

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

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

Rigid

GraphData[{"CubicTransitive",37},"Rigid"]

GraphData[{"CubicTransitive",37},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",37},"Flexible"]

GraphData[{"CubicTransitive",37},"Graph","Flexible"]//StyleGraphs

LCF

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

GraphData[{"CubicTransitive",37},"HamiltonianCycleCount"]

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

GraphData[{"CubicTransitive",37},"LCFNotations"]

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

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",37}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

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

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",37},"VertexList"],GraphData[{"CubicTransitive",37},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

LabelGraph/@{,,,,}

GraphPlot@

g=GraphicsToGraph@

UnitDistanceEmbeddingRefine@g

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",37},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",37}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

{"CubicTransitive", 38}

GraphData[{"CubicTransitive",38},"StandardName"]

Primary

GraphData[{"CubicTransitive",38}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

All

GraphData[{"CubicTransitive",38},"Graph","All"]//StyleGraphs

Bilateral

GraphData[{"CubicTransitive",38},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",38},"Graph","Circular"]//StyleGraphs

Circulant

GraphData[{"CubicTransitive",38},"Circulant"]

GraphData[{"CubicTransitive",38},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CubicTransitive",38},"Halin"]

GraphData[{"CubicTransitive",38},"Graph","Halin"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",38},{"RCN","CN"}]

GraphData[{"CubicTransitive",38},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

GraphData[{"CubicTransitive",38},"V"]

GraphPlot@

v={2+Which[#==0,#-2,#==8,#+2,True,#],#2}&@@@{{4,0},{4,1},{1,2},{3,2},{4,2},{5,2},{7,2},{0,3},{2,3},{4,3},{6,3},{8,3},{2,4},{3,4},{4,4},{5,4},{6,4},{4,5},{0,5},{1,5},{4,6},{7,5},{8,5},{4,7}}

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

RecognizeGraph@g

GraphPlot@RotateGraph[,Pi/6]

v[[9]]/Sqrt[2]//Norm

N[%]

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

RecognizeGraph@g

RectilinearCrossingCount@g

gs=UnlabelGraph/@{,}

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",38}],"CrossingNumber"->6]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

LCF

GraphData[{"CubicTransitive",38},"LCF"]

GraphData[{"CubicTransitive",38},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",38},"LCFSignature"]

GraphData[{"CubicTransitive",38},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",38}],All][[All,All,1]]]//Timing

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

gs=LCFGraph@@@lcf//StyleGraphs

gs=Join[With[{g=BilateralLCFEmbedding[#]},If[MissingQ[g],#,g]]&/@LCFGraph@@@DeleteCases[lcf,{_,1}],DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]]

UnitDistance

GraphData[{"CubicTransitive",38},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",38}],Debug->True]//Timing

GraphData[{"CubicTransitive",38},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance construction

g=RotateGraph[,{1,21}]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",38},"VertexList"],GraphData[{"CubicTransitive",38},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"CubicTransitive",38},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",38},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",38}],TimeConstraint->300,"Results"->All]//Timing}

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

gs={,,,,,};

Matchstick

GraphData[{"CubicTransitive",38},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",38},"Edges"]]

3D All

GraphData[{"CubicTransitive",38},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",38},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",38},"Polyhedral"]

GraphData[{"CubicTransitive",38},"Graph",{"3D","Polyhedron"}]

{"CubicTransitive", 39} == "NauruGraph"

GraphData[{"CubicTransitive",39},"StandardName"]

{"CubicTransitive", 40} == "TruncatedOctahedralGraph"

GraphData[{"CubicTransitive",40},"StandardName"]

{"CubicTransitive", 41}

Names

GraphData[{"CubicTransitive",41},"StandardName"]

GraphData[{"CubicTransitive",41},"StandardNames"]

Primary

GraphData[{"CubicTransitive",41}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

g=Graph[Range[24],UndirectedEdge@@@(Sort/@Join[
Partition[6+{14,17,15,18,13,16},2,1,1],
Join@@(Partition[#,2,1]&/@(#[[{1,3,2,4}]]&/@{{23,17,14,20},{19,13,16,22},{24,18,15,21}})),
{#,#+6}&/@Range[6],
Join@@(Partition[#,2,1]&/@{{17,9,4,5,12,13},{14,8,1,6,11,18},{15,10,3,2,7,16}})
]),VertexCoordinates->Join@@{
3/10Through[{Cos,Sin}[2π#/6]]&/@Range[0,5],
5/10Through[{Cos,Sin}[2π#/6]]&/@Range[0,5],
7/10Through[{Cos,Sin}[2π(#-1/15)/3-π/6]]&/@Range[0,2],
7/10Through[{Cos,Sin}[2π(#+1/15)/3-π/6]]&/@Range[0,2],
Through[{Cos,Sin}[2π(#-1/10)/3-π/6]]&/@Range[0,2],
Through[{Cos,Sin}[2π(#+1/10)/3-π/6]]&/@Range[0,2]
},VertexLabels->Automatic]

EuclideanDistance@@v[[{8,11}]]

g0=CenterGraph@;

v=Join[GraphEmbedding[g0]];
v=Join[v,v[[#]]+v[[#2]]-v[[#3]]&@@@{{9,12,15},{12,9,6},{18,16,13},{16,18,17},{1,2,4},{2,1,3}}];
edges=Join[EdgeList[g0],UndirectedEdge@@@{e[20,19,23,24,22,21,20],{1,24},{2,23},{16,21},{18,22},{9,20},{12,19},{3,8},{5,6},{14,15},{11,17},{4,10},{7,13}}];
g=EdgeDelete[Graph[Range@Length@v,edges,VertexCoordinates->v,VertexLabels->Automatic],{7\[UndirectedEdge]10,11\[UndirectedEdge]14,5\[UndirectedEdge]8}]

RecognizeGraph@g

All

GraphData[{"CubicTransitive",41},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",41},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",41},"Edges"]

GraphPlot[GraphData[{"CubicTransitive",41},"Edges"],GraphLayout->"SpringEmbedding"]

RotateGraph[GraphicsToGraph@,-2Pi/12]

v=Delete[Join[CirclePoints[12],CirclePoints[3/4,12]],List/@{18,19,14,15,23,22}];
v=Join[v,CirclePoints[x,6]];

FullSimplify[((RegionDistance[Line@v[[{6,11}]],v[[22]]])^2),x>0]

Solve[(1/4) (2-(Sqrt[3])+x (-3 (Sqrt[2])+(Sqrt[6])+3 x))==0,x,PositiveReals]//FullSimplify//Union

N[%]

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

RecognizeGraph@g

Degenerate

GraphData[{"CubicTransitive",41},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",41},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicTransitive",41},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",41},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",41},"Planar"]

GraphData[{"CubicTransitive",41},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",41},{"RCN","CN"}]

GraphData[{"CubicTransitive",41},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

GraphPlot@RotateGraph[,2Pi/6]

GraphPlot@RotateGraph[,2Pi/6]

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

RecognizeGraph@g

RectilinearCrossingCount@g

GraphPlot@RotateGraph[,Pi/9]

{#,If[#2>5,#2+1,#2]}&@@@{{0,0},{6,0},{9,0},{3,1},{3,2},{6,2},{0,3},{1,3},{2,3},{4,3},{5,3},{7,3},{8,3},{9,3},{3,4},{6,4},{0,5},{1,5},{8,5},{9,5},{3,6},{6,6},{0,7},{9,7}}

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",41}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@

cn

GraphPlot@RotateGraph[,-Pi/6]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphData[{"CubicTransitive",41},"V"]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",41}],"CrossingNumber"->5]

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

RecognizeGraph@g

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",41},"Circulant"]

GraphData[{"CubicTransitive",41},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",41},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",41}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",41}&]

RootGraph[GraphData[{"CubicTransitive",41}]]

Halin

GraphData[{"CubicTransitive",41},"Halin"]

GraphData[{"CubicTransitive",41},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",41},"Rigid"]

GraphData[{"CubicTransitive",41},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",41},"Flexible"]

GraphData[{"CubicTransitive",41},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",41},"LCF"]

GraphData[{"CubicTransitive",41},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",41},"LCFSignature"]

GraphData[{"CubicTransitive",41},"LCFNotations"]

GraphData[{"CubicTransitive",41},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",41}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",41},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",41}],Debug->True]//Timing

GraphData[{"CubicTransitive",41},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",41},"VertexList"],GraphData[{"CubicTransitive",41},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",41},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",41}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",41},"Matchstick"]

GraphData[{"CubicTransitive",41},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",41},"Edges"]]

3D All

GraphData[{"CubicTransitive",41},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",41},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",41},"Polyhedral"]

{"CubicTransitive", 42} == {"CrossedPrism", 12}

GraphData[{"CubicTransitive",42},"StandardName"]

{"CubicTransitive", 43} == {"Prism", 12}

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

{"CubicTransitive", 44} == {"MoebiusLadder", 12}

GraphData[{"CubicTransitive",44},"StandardName"]

{"CubicTransitive", 45} == "TruncatedCubicalGraph"

GraphData[{"CubicTransitive",45},"StandardName"]

{"CubicTransitive", 46} == "Foster026A"

GraphData[{"CubicTransitive",46},"StandardName"]

{"CubicTransitive", 47}

Names

GraphData[{"CubicTransitive",47},"StandardName"]

GraphData[{"CubicTransitive",47},"StandardNames"]

Primary

GraphData[{"CubicTransitive",47}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

All

GraphData[{"CubicTransitive",47},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",47},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",47},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",47},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",47},"Graph","Degenerate"]

CVT construction

g=CubicVertexTransitiveGraph[26]

RecognizeGraph@g

GeneralizedHoneycombGraph construction

With[{n=26},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",_}}]]//Timing

gs=GeneralizedHoneycombGraph[26,#]&/@{3,5,7}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",47},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",47},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",47},"Planar"]

GraphData[{"CubicTransitive",47},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",47},{"RCN","CN"}]

GraphData[{"CubicTransitive",47},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",47}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@RotateGraph[,-7Pi/9]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",47}],"CrossingNumber"->5]

GraphPlot@HighlightGraph[RotateGraph[GraphicsToGraph@,{17,21}],Range[26+1,26+5]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",47},"Circulant"]

GraphData[{"CubicTransitive",47},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",47},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",47}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",47}&]

RootGraph[GraphData[{"CubicTransitive",47}]]

Halin

GraphData[{"CubicTransitive",47},"Halin"]

GraphData[{"CubicTransitive",47},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",47},"Rigid"]

GraphData[{"CubicTransitive",47},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",47},"Flexible"]

GraphData[{"CubicTransitive",47},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",47},"LCF"]

GraphData[{"CubicTransitive",47},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",47},"LCFSignature"]

GraphData[{"CubicTransitive",47},"LCFNotations"]

GraphData[{"CubicTransitive",47},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",47}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",47},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",47}],Debug->True]//Timing

GraphData[{"CubicTransitive",47},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",47},"VertexList"],GraphData[{"CubicTransitive",47},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",47},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",47}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",47},"Matchstick"]

GraphData[{"CubicTransitive",47},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",47},"Edges"]]

3D All

GraphData[{"CubicTransitive",47},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",47},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",47},"Polyhedral"]

{"CubicTransitive", 48} == {"GeneralizedPetersen", {13, 5}}

GraphData[{"CubicTransitive",48},"StandardName"]

{"CubicTransitive", 49} == {"MoebiusLadder", 13}

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

{"CubicTransitive", 50} == {"Prism", 13}

GraphData[{"CubicTransitive",50},"StandardName"]

{"CubicTransitive", 51}

Names

GraphData[{"CubicTransitive",51},"StandardName"]

GraphData[{"CubicTransitive",51},"StandardNames"]

Primary

GraphData[{"CubicTransitive",51}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

All

GraphData[{"CubicTransitive",51},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",51},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",51},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",51},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",51},"Graph","Degenerate"]

GeneralizedHoneycombGraph construction

With[{n=28},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",51}}]]//Timing

g=GeneralizedHoneycombGraph[28,5]

RecognizeGraph@g

Bilateral

GraphData[{"CubicTransitive",51},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",51},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",51},"Planar"]

GraphData[{"CubicTransitive",51},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",51},{"RCN","CN"}]

GraphData[{"CubicTransitive",51},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",51}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@RotateGraph[,π+4Pi/7]

v={#/9,#2/6}&@@@{{0,0},{9,0},{1,1},{3,1},{6,1},{8,1},{3,2},{6,2},{1,3},{2,3},{3,3},{4,3},{5,3},{6,3},{7,3},{8,3},{0,4},{2,4},{3,4},{4,4},{5,4},{6,4},{7,4},{9,4},{1,5},{8,5},{0,6},{9,6}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,5,6,2,4,3,1,17,27,28,24,2],e[3,9,25,22],e[6,16,26,19],e[{17,24}],e[{9,12}],e[{13,16}],e[4,7,11],e[5,8,14],{25,27},{26,28},{10,20},{12,18},{13,23},{15,21},{7,13},{12,8}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphData[{"CubicTransitive",51},"V"]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",51}],"CrossingNumber"->7]

v={#/9,#2/8}&@@@{{0,0},{9,0},{2,1},{8,1},{4,2},{6,2},{7,2},{8,2},{2,3},{6,3},{2,4},{4,4},{6,4},{8,4},{0,5},{1,5},{3,5},{4,5},{5,5},{6,5},{3,6},{7,6},{2,7},{5,7},{8,7},{0,8},{3,8},{9,8}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,14,25,28,27,26,15,1,9,11,23,26],e[23,24,25],e[15,16,17,18,19,20,22,21],e[16,3,4,2],e[3,5,12,18],{9,10},{11,12},{13,14},e[4,8,28],e[5,6,7,8],{7,22},e[6,10,13,20],{19,24},e[17,21,27]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",51},"Circulant"]

GraphData[{"CubicTransitive",51},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",51},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",51}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",51}&]

RootGraph[GraphData[{"CubicTransitive",51}]]

Halin

GraphData[{"CubicTransitive",51},"Halin"]

GraphData[{"CubicTransitive",51},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",51},"Rigid"]

GraphData[{"CubicTransitive",51},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",51},"Flexible"]

GraphData[{"CubicTransitive",51},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",51},"LCF"]

GraphData[{"CubicTransitive",51},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",51},"LCFSignature"]

GraphData[{"CubicTransitive",51},"LCFNotations"]

GraphData[{"CubicTransitive",51},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",51}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",51},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",51}],Debug->True]//Timing

GraphData[{"CubicTransitive",51},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",51},"VertexList"],GraphData[{"CubicTransitive",51},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",51},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",51}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",51},"Matchstick"]

GraphData[{"CubicTransitive",51},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",51},"Edges"]]

3D All

GraphData[{"CubicTransitive",51},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",51},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",51},"Polyhedral"]

{"CubicTransitive", 52}

Names

GraphData[{"CubicTransitive",52},"StandardName"]

GraphData[{"CubicTransitive",52},"StandardNames"]

Primary

GraphData[{"CubicTransitive",52}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

edges=Sort/@Join[
Partition[Range[14],2,1,1],
Partition[Range[15,28],2,1,1],
{{4,20},{7,19},{5,17},{6,22},{18,2},{3,15},{1,27},{8,24},{23,11},{9,21},{12,28},{25,13},{26,10},{14,16}}
]

v=-Join[
Through[{Cos,Sin}[Pi/14+2π(#-10/20)/14]]&/@Range[0,13],
Flatten[Transpose[{2Through[{Cos,Sin}[Pi/14+2π(#-7/100)/7]]&/@Range[0,6],
2Through[{Cos,Sin}[Pi/14+2π(#+7/100)/7]]&/@Range[0,6]}],1]
]

g=Graph[Range[28],UndirectedEdge@@@edges,VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

v=Join[CirclePoints[14],CirclePoints[x,14]];
FullSimplify[((RegionDistance[Line@v[[{8,13}]],v[[24]]])^2),x>0]

Solve[(-x Cos[(π/14)]+Sin[(π/7)])==0,x,PositiveReals]

v=Join[CirclePoints[14],CirclePoints[Sec[(π/14)] Sin[(π/7)],14]];
g=Graph[Range@Length@v,UndirectedEdge@@@edges,VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

All

GraphData[{"CubicTransitive",52},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",52},"EdgeList"]]

Default embedding

GraphPlot[GraphData[{"CubicTransitive",52},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",52},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",52},"Graph","Degenerate"]

CVT construction

GraphPlot[GraphData[{"CubicTransitive",52},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

g=CubicVertexTransitiveGraph[28]

RecognizeGraph@g

GeneralizedHoneycombGraph construction

With[{n=28},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",52}}]]//Timing

gs=GeneralizedHoneycombGraph[28,#]&/@{3,11}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",52},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",52},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",52},"Planar"]

GraphData[{"CubicTransitive",52},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",52},{"RCN","CN"}]

GraphData[{"CubicTransitive",52},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

GraphPlot@RotateGraph[,Pi/9]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@RotateGraph[,Pi/9]

v={#/9,#2/6}&@@@{{0,0},{9,0},{1,1},{8,1},{0,2},{3,2},{4,2},{5,2},{6,2},{9,2},{0,3},{1,3},{2,3},{3,3},{6,3},{7,3},{8,3},{9,3},{0,4},{3,4},{4,4},{5,4},{6,4},{9,4},{2,5},{7,5},{0,6},{9,6}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,10,18,24,28,27,19,11,5,1,4,8,7,3,2],{3,12},{4,17},e[5,6,7],e[8,9,10],e[6,14,20],e[9,15,23],e[11,12,13,14],e[15,16,17,18],e[{19,24}],{13,25},{16,26},e[27,25,22],e[21,26,28]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

gs=UnlabelGraph/@{,}

Circulant

GraphData[{"CubicTransitive",52},"Circulant"]

GraphData[{"CubicTransitive",52},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",52},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",52}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",52}&]

RootGraph[GraphData[{"CubicTransitive",52}]]

Halin

GraphData[{"CubicTransitive",52},"Halin"]

GraphData[{"CubicTransitive",52},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",52},"Rigid"]

GraphData[{"CubicTransitive",52},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",52},"Flexible"]

GraphData[{"CubicTransitive",52},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",52},"LCF"]

GraphData[{"CubicTransitive",52},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",52},"LCFSignature"]

GraphData[{"CubicTransitive",52},"LCFNotations"]

GraphData[{"CubicTransitive",52},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",52}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",52},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",52}],Debug->True]//Timing

GraphData[{"CubicTransitive",52},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",52},"VertexList"],GraphData[{"CubicTransitive",52},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",52},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",52}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",52},"Matchstick"]

GraphData[{"CubicTransitive",52},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",52},"Edges"]]

3D All

GraphData[{"CubicTransitive",52},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",52},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",52},"Polyhedral"]

{"CubicTransitive", 53} == "CoxeterGraph"

GraphData[{"CubicTransitive",53},"StandardName"]

{"CubicTransitive", 54} == {"CrossedPrism", 14}

GraphData[{"CubicTransitive",54},"StandardName"]

{"CubicTransitive", 55} == {"Prism", 14}

GraphData[{"CubicTransitive",55},"StandardName"]

{"CubicTransitive", 56} == {"MoebiusLadder", 14}

GraphData[{"CubicTransitive",56},"StandardName"]

{"CubicTransitive", 57}

Names

GraphData[{"CubicTransitive",57},"StandardName"]

GraphData[{"CubicTransitive",57},"StandardNames"]

Primary

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

Read and Wilson

g=Graph[Range[30],UndirectedEdge@@@{{1,2},{1,3},{1,4},{2,5},{2,11},{3,7},{3,10},{4,6},{4,17},{5,8},{5,9},{6,7},{6,12},{7,24},{8,13},{8,14},{9,10},{9,16},{10,22},{11,14},{11,20},{12,18},{12,19},{13,15},{13,19},{14,27},{15,16},{15,18},{16,21},{17,20},{17,23},{18,23},{19,25},{20,29},{21,22},{21,26},{22,28},{23,26},{24,25},{24,28},{25,27},{26,29},{27,30},{28,30},{29,30}},VertexCoordinates->(10^(-4)){{7168,-10906},{8833,-16037},{8913,-5530},{9854,-11780},{10494,-13750},{10727,-9092},{11599,-6404},{12779,-15411},{13275,-5186},{13275,-2359},{13403,-19359},{13413,-9965},{14439,-13125},{15064,-17073},{16099,-8012},{16099,-5186},{17134,-17073},{17759,-13125},{18785,-9965},{18794,-19359},{18923,-5186},{18923,-2359},{19419,-15411},{20599,-6404},{21471,-9092},{21704,-13750},{22344,-11780},{23285,-5530},{23364,-16037},{25030,-10906}}]

RecognizeGraph@g

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",57},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",57},"Edges"]

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

RecognizeGraph[g]

v=Join[CirclePoints[10],CirclePoints[2/3,15],CirclePoints[1/3,5]];
Do[v[[i]]=Mean[v[[{i-1,i+1}]]],{i,12,24,3}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[{1,10},1,11,12,13,2],e[3,14,15,16,4],e[5,17,18,19,6],e[7,20,21,22,8],e[9,23,24,25,10],e[30,27,29,26,28,30],{24,30},{12,26},{15,27},{18,28},{21,29},{23,19},{20,16},{22,11},{25,14},{13,17}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Planar

GraphData[{"CubicTransitive",57},"Planar"]

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

MinimalCrossing

GraphData[{"CubicTransitive",57},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

GraphPlot@RotateGraph[]

v={#/12,#2/6}&@@@{{0,0},{12,0},{1,1},{11,1},{0,2},{2,2},{3,2},{4,2},{5,2},{7,2},{8,2},{9,2},{10,2},{12,2},{2,3},{4,3},{8,3},{10,3},{0,4},{1,4},{5+1/2,4},{6,4},{7-1/2,4},{11,4},{12,4},{2,5},{10,5},{0,6},{6,6},{12,6}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,14,25,30,29,28,19,5,1,3,20],e[24,4,2],e[{5,14}],e[{19,25}],e[6,15,26,27,18,13],{26,28},{27,30},{22,29},e[15,16,17,18],{3,12},{7,4},{8,16},{11,17},{9,23},{10,21}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",57}],"CrossingNumber"->9]

v={{8,-3},{1,1},{2,1},{5,1},{1,2},{4,2},{5,2},{7,2},{-4,3},{1,3},{4,3},{6,3},{4,4},{5,4},{7,4},{12,4},{1,5},{2,5},{3,5},{5,5},{6,5},{7,5},{1,6},{3,6},{4,6},{0,7},{7,7},{8,7},{9,7},{1,8}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{{1,15},e[26,27,28,29],e[4,16,29,30,26,9,1],e[2,3,4],e[5,6,7,8],{9,10},e[2,5,10,17,23,30],e[17,18,19,20,21,22],e[13,14,15],{6,11},{8,12},{11,12},{11,18},e[23,24,25,16],{19,24},e[25,13,3],{14,20},{12,21},{8,28},{1,2},e[15,22,27],{4,7}},VertexCoordinates->v,VertexLabels->Automatic]

RectilinearCrossingCount[g]

RecognizeGraph[g]

Circulant

GraphData[{"CubicTransitive",57},"Circulant"]

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

Line graph

GraphData[{"CubicTransitive",57},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",57}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",57}&]

RootGraph[GraphData[{"CubicTransitive",57}]]

Halin

GraphData[{"CubicTransitive",57},"Halin"]

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

Rigid

GraphData[{"CubicTransitive",57},"Rigid"]

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

Flexible

GraphData[{"CubicTransitive",57},"Flexible"]

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

LCF

GraphData[{"CubicTransitive",57},"LCF"]

GraphData[{"CubicTransitive",57},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",57},"LCFSignature"]

GraphData[{"CubicTransitive",57},"LCFNotations"]

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

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",57}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

UnitDistance

GraphData[{"CubicTransitive",57},"UnitDistance"]

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

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

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

GraphPlot@

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"CubicTransitive",57},"Matchstick"]

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

3D default

Graph3D[GraphData[{"CubicTransitive",57},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"CubicTransitive",57},"Polyhedral"]

{"CubicTransitive", 58}

Names

GraphData[{"CubicTransitive",58},"StandardName"]

GraphData[{"CubicTransitive",58},"StandardNames"]

Primary

GraphData[{"CubicTransitive",58}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

All

GraphData[{"CubicTransitive",58},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",58},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",58},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",58},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",58},"Graph","Degenerate"]

GeneralizedHoneycombGraph construction

With[{n=30},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",58}}]]//Timing

gs=GeneralizedHoneycombGraph[30,#]&/@{5,9,11}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",58},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",58},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",58},"Planar"]

GraphData[{"CubicTransitive",58},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",58},{"RCN","CN"}]

GraphData[{"CubicTransitive",58},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",58}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@RotateGraph[,2Pi/6]

GraphData[{"CubicTransitive",58},"V"]

v={#/9,#2/10}&@@@{{0,0},{9,0},{1,1},{2,1},{7,1},{1,2},{3,2},{7,2},{2,3},{3,3},{4,3},{8,3},{1,4},{5,4},{7,4},{4,5},{6,5},{2,6},{4,6},{4,7},{5,7},{6,7},{1,8},{4,8},{2,9},{4,9},{6,9},{7,9},{0,10},{9,10}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,5,8,15,28,27,26,25,30,2,4,3,1,29,28],e[3,6,13,23,24],e[6,7,8],e[2,12,11,10,9],{5,12},e[4,9,18,25],{7,10},e[11,16,19,20,24,26],{18,19},e[13,14,15],{14,21},e[17,22,27],e[20,21,22],e[16,17,30],{23,29}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",58}],"CrossingNumber"->9]

v={{4,0},{-1,1},{1,1},{2,1},{8,1},{12,1},{2,2},{7,2},{2,3},{3,3},{5,3},{6,3},{4,4},{5,4},{3,5},{4,5},{5,5},{12,5},{-1,6},{4,6},{5,6},{6,6},{3,7},{1,8},{2,8},{4,8},{7,8},{8,8},{4,9},{4,12}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,6,18,30,19,2,1],e[2,3,4,5,6],e[3,24,29,30],e[29,28,5],e[24,25,26,27,28],e[19,20,21,22,12,8,7],e[4,7,9,25],e[9,10,11,12],e[1,13,16,20],e[10,15,23,26],{8,27},{22,23},e[11,14,17,21],{13,14},e[15,16],e[17,18]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",58},"Circulant"]

GraphData[{"CubicTransitive",58},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",58},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",58}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",58}&]

RootGraph[GraphData[{"CubicTransitive",58}]]

Halin

GraphData[{"CubicTransitive",58},"Halin"]

GraphData[{"CubicTransitive",58},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",58},"Rigid"]

GraphData[{"CubicTransitive",58},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",58},"Flexible"]

GraphData[{"CubicTransitive",58},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",58},"LCF"]

GraphData[{"CubicTransitive",58},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",58},"LCFSignature"]

GraphData[{"CubicTransitive",58},"LCFNotations"]

GraphData[{"CubicTransitive",58},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",58}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",58},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",58}],Debug->True]//Timing

GraphData[{"CubicTransitive",58},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",58},"VertexList"],GraphData[{"CubicTransitive",58},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",58},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",58}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",58},"Matchstick"]

GraphData[{"CubicTransitive",58},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",58},"Edges"]]

3D All

GraphData[{"CubicTransitive",58},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",58},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",58},"Polyhedral"]

{"CubicTransitive", 59}

Names

GraphData[{"CubicTransitive",59},"StandardName"]

GraphData[{"CubicTransitive",59},"StandardNames"]

Primary

GraphData[{"CubicTransitive",59}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

All

GraphData[{"CubicTransitive",59},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",59},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",59},"Edges"]

GraphPlot@

GraphData[{"CubicTransitive",59},"V"]

v=Join[
Flatten[Subdivide[#,#2,3]&@@@Transpose[{CirclePoints[{1,-Pi/2},10],CirclePoints[{1/2,-Pi/2},10]}][[2;;All;;2]],1],
CirclePoints[{1,-Pi/2},10][[1;;All;;2]],CirclePoints[{1/2,-Pi/2},10][[1;;All;;2]]
];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,22,5,23,9,24,13,25,17,21,1,2,3,4,27,8,28,12,29,16,30,20,26,21],e[{17,20}],e[{13,16}],e[{9,12}],e[{5,8}],{4,26},{19,2},{15,18},{3,6},{14,11},{7,10},{22,27},{23,28},{24,29},{25,30}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",59},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",59},"Graph","Degenerate"]

CVT construction

GraphPlot[GraphData[{"CubicTransitive",59},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

g=CubicVertexTransitiveGraph[30]

RecognizeGraph@g

GeneralizedHoneycombGraph construction

With[{n=30},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",59}}]]//Timing

gs=GeneralizedHoneycombGraph[30,#]&/@{3,7}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",59},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",59},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",59},"Planar"]

GraphData[{"CubicTransitive",59},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",59},{"RCN","CN"}]

GraphData[{"CubicTransitive",59},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",59}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@

v={#/6,#2/8}&@@@{{0,0},{3,0},{6,0},{1,1},{2,1},{5,1},{2,2},{3,2},{4,2},{5,2},{0,3},{2,3},{4,3},{6,3},{5,4},{6,4},{1,5},{2,5},{4,5},{5,5},{2,6},{3,6},{4,6},{6,6},{1,7},{3,7},{5,7},{0,8},{2,8},{6,8}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,14,16,24,30,29,28,11,1,4,5,6,3],e[28,25,26,27,30],{11,12},{13,14},{19,20},{17,18},e[4,17,25],e[5,7,12,18,21,29],{22,26},e[7,8,9,10],e[6,10,15,20,27],e[21,22,23,24],e[9,13,19,23],{2,8},{15,16}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[gn],"CrossingNumber"->cn]

v=Join[CirclePoints[{1,-Pi/2},10],CirclePoints[{1/2,-Pi/2},10],CirclePoints[{3/4,-Pi/2},15]];
g=VertexDelete[Graph[Range[Length[v]],UndirectedEdge@@@Sort[Sort/@Join[Partition[Range[10],2,1,1],Partition[Range[11,20],2,1,1],Partition[Range[21,35],2,1,1],Table[{i,i+10},{i,1,9,2}],Table[{i,i+2},{i,23,32,3}],Table[{i,2i-(i/2-5)},{i,12,20,2}],Table[{i,20+i+(i-2)/2},{i,2,10,2}],{{22,35}}]],VertexCoordinates->v,VertexLabels->Automatic],Range[21,33,3]]

RecognizeGraph[g]

RectilinearCrossingCount[g]

v=Join[CirclePoints[{1,-Pi/2},10],CirclePoints[{1/2,-Pi/2},10],CirclePoints[{3/4,-4Pi/10},10]];
g=Graph[Range[Length[v]],UndirectedEdge@@@Sort[Sort/@Join[Partition[Range[10],2,1,1],Partition[Range[11,20],2,1,1],Table[{i,i+10},{i,1,10,2}],Partition[Range[21,30],2,1,1],Table[{i,19+i},{i,2,10,2}],Table[{i,10+i},{i,12,20,2}]]],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",59},"Circulant"]

GraphData[{"CubicTransitive",59},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",59},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",59}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",59}&]

RootGraph[GraphData[{"CubicTransitive",59}]]

Halin

GraphData[{"CubicTransitive",59},"Halin"]

GraphData[{"CubicTransitive",59},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",59},"Rigid"]

GraphData[{"CubicTransitive",59},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",59},"Flexible"]

GraphData[{"CubicTransitive",59},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",59},"LCF"]

GraphData[{"CubicTransitive",59},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",59},"LCFSignature"]

GraphData[{"CubicTransitive",59},"LCFNotations"]

GraphData[{"CubicTransitive",59},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",59}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",59},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",59}],Debug->True]//Timing

GraphData[{"CubicTransitive",59},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",59},"VertexList"],GraphData[{"CubicTransitive",59},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",59},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",59}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",59},"Matchstick"]

GraphData[{"CubicTransitive",59},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",59},"Edges"]]

3D All

GraphData[{"CubicTransitive",59},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",59},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",59},"Polyhedral"]

{"CubicTransitive", 60}

Names

GraphData[{"CubicTransitive",60},"StandardName"]

GraphData[{"CubicTransitive",60},"StandardNames"]

Primary

GraphData[{"CubicTransitive",60}]//StyleGraphs[#,ImageSize->Small]&

Read and Wilson

All

GraphData[{"CubicTransitive",60},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",60},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",60},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",60},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",60},"Graph","Degenerate"]

GeneralizedHoneycombGraph construction

With[{n=30},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",60}}]]//Timing

g=GeneralizedHoneycombGraph[30,13]

RecognizeGraph@g

Bilateral

GraphData[{"CubicTransitive",60},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",60},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",60},"Planar"]

GraphData[{"CubicTransitive",60},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",60},{"RCN","CN"}]

GraphData[{"CubicTransitive",60},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",60}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@RotateGraph[,Pi/8]

v={#/9,#2/7}&@@@{{0,0},{9,0},{1,1},{4,1},{6,1},{8,1},{0,2},{2,2},{7,2},{9,2},{2,3},{3,3},{4,3},{7,3},{1,4},{3,4},{4,4},{5,4},{6,4},{7,4},{2,5},{4,5},{7,5},{9,5},{1,6},{5,6},{8,6},{0,7},{2,7},{9,7}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,10,24,30,29,28,7,1,3,4,5,6,2],e[28,25,26,27,30],e[7,8,9,10],e[3,15,25],e[8,11,21,29],e[11,12,13,14],e[9,14,20,23],{6,27},e[15,16,17,18,19,20],e[21,22,23,24],{17,22},{12,16},{4,13},{5,19},{18,26}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",60}],"CrossingNumber"->9]

v={{0,0},{9,0},{2,1},{6,1},{2,2},{6,2},{2,3},{3,3},{5,3},{6,3},{2,4},{4,4},{5,4},{6,4},{7,4},{8,4},{1,5},{3,5},{4,5},{4,6},{0,7},{1,7},{4,7},{5,7},{8,6},{9,6},{11,6},{2,8},{5,8},{6,8}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[21,22,23,24,25,26,27,30,29,28,21,1,2,26],e[2,3,4,9],e[27,6,5,1],{4,16},e[3,17,22],e[5,7,11,28],e[7,8,9,10],{8,18},e[11,12,13,14,15,16,25],e[17,18,19],{24,29},e[19,20,23],{13,30},{20,15},e[6,10,14],{12,19}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",60},"Circulant"]

GraphData[{"CubicTransitive",60},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",60},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",60}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",60}&]

RootGraph[GraphData[{"CubicTransitive",60}]]

Halin

GraphData[{"CubicTransitive",60},"Halin"]

GraphData[{"CubicTransitive",60},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",60},"Rigid"]

GraphData[{"CubicTransitive",60},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",60},"Flexible"]

GraphData[{"CubicTransitive",60},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",60},"LCF"]

GraphData[{"CubicTransitive",60},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",60},"LCFSignature"]

GraphData[{"CubicTransitive",60},"LCFNotations"]

GraphData[{"CubicTransitive",60},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",60}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",60},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",60}],Debug->True]//Timing

GraphData[{"CubicTransitive",60},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",60},"VertexList"],GraphData[{"CubicTransitive",60},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",60},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",60}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",60},"Matchstick"]

GraphData[{"CubicTransitive",60},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",60},"Edges"]]

3D All

GraphData[{"CubicTransitive",60},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",60},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",60},"Polyhedral"]

{"CubicTransitive", 61} == {"GeneralizedPetersen", {15, 4}}

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

{"CubicTransitive", 62}

Names

GraphData[{"CubicTransitive",62},"StandardName"]

GraphData[{"CubicTransitive",62},"StandardNames"]

Primary

GraphData[{"CubicTransitive",62}]//StyleGraphs[#,ImageSize->Small]&

Construct from Read and Wilson

g=Graph[Range[29],UndirectedEdge@@@{{1,4},{1,5},{1,10},{2,3},{2,7},{2,15},{3,6},{3,10},{4,11},{4,12},{5,7},{5,14},{6,8},{6,12},{7,9},{8,9},{8,23},{9,11},{10,13},{11,20},{12,16},{13,18},{13,19},{14,17},{14,19},{15,17},{15,18},{16,25},{16,27},{17,22},{18,26},{19,29},{20,21},{20,27},{21,23},{21,24},{22,28},{22,30},{23,25},{24,26},{24,29},{25,28},{26,30},{27,30},{28,29}},VertexCoordinates->(10^(-4)){{8823,-8498},{9557,-6238},{10650,-9092},{10953,-15057},{11384,-6832},{12082,-13502},{12478,-9686},{12874,-16454},{13212,-11946},{13212,-7426},{14004,-14899},{15133,-13343},{15133,-6029},{15133,-4106},{15133,-2184},{17508,-13343},{17508,-6029},{17508,-4106},{17508,-2184},{18637,-14899},{19429,-11946},{19429,-7426},{19767,-16454},{20163,-9686},{20559,-13502},{21257,-6832},{21688,-15057},{21991,-9092},{23084,-6238},{23818,-8498}}]

RecognizeGraph@g

All

GraphData[{"CubicTransitive",62},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",62},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",62},"Edges"]

v=Flatten[Table[RotationMatrix[2Pi i/5].#&/@Flatten[Table[{i,j},{i,{-1/2,1/2}},{j,2,4}],1],{i,0,4}],1]/5;
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[8,17,13,22,20,29,27],e[2,4,3,12,8,10,9,11,7,16,14,18,9],e[12,7],e[17,15,24,20],e[18,13],{15,16},e[10,1,5,3],e[6,2],e[1,6,27,28,26,30,21,22],e[11,2],e[5,26],e[29,25,30],{4,25},e[28,19,23,21],{24,19},{14,23}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",62},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",62},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicTransitive",62},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",62},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",62},"Planar"]

GraphData[{"CubicTransitive",62},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",62},{"RCN","CN"}]

GraphData[{"CubicTransitive",62},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",62}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot[,VertexSize->1]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",62},"Circulant"]

GraphData[{"CubicTransitive",62},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",62},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",62}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",62}&]

RootGraph[GraphData[{"CubicTransitive",62}]]

Halin

GraphData[{"CubicTransitive",62},"Halin"]

GraphData[{"CubicTransitive",62},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",62},"Rigid"]

GraphData[{"CubicTransitive",62},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",62},"Flexible"]

GraphData[{"CubicTransitive",62},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",62},"LCF"]

GraphData[{"CubicTransitive",62},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",62},"LCFSignature"]

GraphData[{"CubicTransitive",62},"LCFNotations"]

GraphData[{"CubicTransitive",62},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",62}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",62},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",62}],Debug->True]//Timing

GraphData[{"CubicTransitive",62},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",62},"VertexList"],GraphData[{"CubicTransitive",62},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",62},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",62}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",62},"Matchstick"]

GraphData[{"CubicTransitive",62},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",62},"Edges"]]

3D All

GraphData[{"CubicTransitive",62},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",62},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",62},"Polyhedral"]

{"CubicTransitive", 63} == "Tutte8Cage"

GraphData[{"CubicTransitive",63},"StandardName"]

{"CubicTransitive", 64} == {"MoebiusLadder", 15}

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

{"CubicTransitive", 65} == {"Prism", 15}

GraphData[{"CubicTransitive",65},"StandardName"]

{"CubicTransitive", 66} == "TriangleReplacedPetersenGraph"

GraphData[{"CubicTransitive",66},"StandardName"]

{"CubicTransitive", 67}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",67},"EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",67},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",67},"Graph","Degenerate"]

GeneralizedHoneycombGraph construction

With[{n=32},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",67}}]]//Timing

gs=GeneralizedHoneycombGraph[32,#]&/@{7,9}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",67},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",67},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",67},"Planar"]

GraphData[{"CubicTransitive",67},"Graph","Planar"]//StyleGraphs

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",67}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@

GraphData[{"CubicTransitive",67},"V"]

GraphPlot@

v={#/9,#2/7}&@@@{{0,0},{5,0},{9,0},{1,1},{2,1},{8,1},{2,2},{4,2},{7,2},{8,2},{0,3},{3,3},{4,3},{5,3},{6,3},{7,3},{2,4},{3,4},{4,4},{5,4},{6,4},{9,4},{1,5},{2,5},{5,5},{7,5},{1,6},{7,6},{8,6},{0,7},{4,7},{9,7}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,22,32,31,30,11,1,4,5,6,3],e[30,27,28,29,32],e[4,23,27],e[6,10,29],e[9,16,26,28],e[23,24,25,26],e[17,18,19,20,21,22],e[5,7,17,24],e[11,12,13,14,15,16],e[7,8,9,10],e[2,14],{20,25},{12,18},{15,21},{19,31},{8,13}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",67}],"CrossingNumber"->8]

v=Join[CirclePoints[{1,0},8],CirclePoints[{3/4,Pi/8},8],CirclePoints[{1/2,Pi/8},8],CirclePoints[{1/4,0},8]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,6,7,8,1],e[9,10,11,12,13,14,15,16,9],e[17,18,19,20,21,22,23,24,17],e[25,26,27,28,29,30,31,32,25],{1,25},{3,27},{5,29},{7,31},{8,15},{2,9},{4,11},{6,13},Sequence@@Table[{i,i+7},{i,10,16,2}],Sequence@@Table[{i,i+8},{i,18,24,2}]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",67},"Circulant"]

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

Line graph

GraphData[{"CubicTransitive",67},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",67}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",67}&]

RootGraph[GraphData[{"CubicTransitive",67}]]

Halin

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

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

Rigid

GraphData[{"CubicTransitive",67},"Rigid"]

GraphData[{"CubicTransitive",67},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",67},"Flexible"]

GraphData[{"CubicTransitive",67},"Graph","Flexible"]//StyleGraphs

LCF

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

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

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

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

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

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

LCF compute all

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

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",67},"UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",67},"VertexList"],GraphData[{"CubicTransitive",67},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",67},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",67}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

{"CubicTransitive", 68}

Names

GraphData[{"CubicTransitive",68},"StandardName"]

GraphData[{"CubicTransitive",68},"StandardNames"]

Primary

GraphData[{"CubicTransitive",68}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CubicTransitive",68},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",68},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",68},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",68},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",68},"Graph","Degenerate"]

CubicVertexTransitiveGraph construction

g=CubicVertexTransitiveGraph[32]

RecognizeGraph@g

GeneralizedHoneycombGraph construction

With[{n=32},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",68}}]]//Timing

gs=GeneralizedHoneycombGraph[32,#]&/@{3,13}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",68},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",68},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",68},"Planar"]

GraphData[{"CubicTransitive",68},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",68},{"RCN","CN"}]

GraphData[{"CubicTransitive",68},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",68}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@RotateGraph[,9Pi/11]

v={#/5,#2/9}&@@@{{0,0},{5,0},{1,1},{2,1},{3,1},{4,1},{2,2},{3,2},{0,3},{2,3},{3,3},{5,3},{1,4},{2,4},{3,4},{4,4},{0,5},{1,5},{2,5},{3,5},{4,5},{5,5},{2,6},{3,6},{2,7},{3,7},{2,8},{3,8},{0,9},{2,9},{3,9},{5,9}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,5,6,2,4,3,1,9,17,29,30,31,32,22,12,2],e[3,13,18,25],e[26,21,16,6],{9,10},{11,12},{17,18},{21,22},e[4,7,10,14,19,23,25,27,30],e[5,8,11,15,20,24,26,28,31],{13,14},{15,16},{29,19},{20,32},{24,27},{23,28},{7,8}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

RectilinearCrossingCount@g

v=Delete[Join[CirclePoints[10],CirclePoints[3/4,17],CirclePoints[1/2,11]],List/@{19,33,22,25,13,16}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[{1,10},11],e[{11,16}],e[{17,22},1],e[{23,27}],e[{28,32},23,11],{22,32},e[27,17,6],e[28,16,5],{7,29},{18,28},{27,15},{26,4},{8,19},{20,30},{14,3},{25,13},{9,31},{2,24},{10,21},{1,12}},VertexCoordinates->v,VertexLabels->Automatic]

RectilinearCrossingCount[g]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",68}],"CrossingNumber"->6]

GraphPlot@HighlightGraph[RotateGraph[GraphicsToGraph@,{5,14}],Range[33,38]]

v={{2,0},{8,0},{2,1},{3,1},{6,1},{8,1},{0,2},{1,2},{3,2},{6,2},{7,2},{9,2},{1,3},{2,3},{7,3},{8,3},{0,4},{2,4},{3,4},{4,4},{6,4},{7,4},{1,5},{3,5},{5,5},{6,5},{8,5},{9,5},{1,6},{4,6},{5,6},{7,6}};
g0=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,5,6,2,12,28,32,31,30,29,17,7,1,3,4,2],e[6,16,27],e[3,14,18],e[7,8,9,10,11,12],{13,14},{15,16},{5,10},{4,9},e[11,15,22,32],{25,31},e[23,24,25,26,27,28],e[8,13,23,29],e[17,18,19,20,21,22],{19,24},{20,30},{21,26}},VertexCoordinates->v,VertexLabels->Automatic]

GraphPlot@UnlabelGraph[g0]

GraphicsToGraph@

v=Round[GraphEmbedding@%]

v={#/9,#2/6}&@@@{{0,0},{9,0},{2,1},{3,1},{6,1},{8,1},{0,2},{1,2},{3,2},{6,2},{7,2},{9,2},{1,3},{2,3},{7,3},{8,3},{0,4},{2,4},{3,4},{4,4},{6,4},{7,4},{1,5},{3,5},{5,5},{6,5},{8,5},{9,6},{0,6},{4,6},{5,6},{7,6}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,5,6,2,12,28,32,31,30,29,17,7,1,3,4,2],e[6,16,27],e[3,14,18],e[7,8,9,10,11,12],{13,14},{15,16},{5,10},{4,9},e[11,15,22,32],{25,31},e[23,24,25,26,27,28],e[8,13,23,29],e[17,18,19,20,21,22],{19,24},{20,30},{21,26}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",68},"Circulant"]

GraphData[{"CubicTransitive",68},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",68},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",68}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",68}&]

RootGraph[GraphData[{"CubicTransitive",68}]]

Halin

GraphData[{"CubicTransitive",68},"Halin"]

GraphData[{"CubicTransitive",68},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",68},"Rigid"]

GraphData[{"CubicTransitive",68},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",68},"Flexible"]

GraphData[{"CubicTransitive",68},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",68},"LCF"]

GraphData[{"CubicTransitive",68},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",68},"LCFSignature"]

GraphData[{"CubicTransitive",68},"LCFNotations"]

GraphData[{"CubicTransitive",68},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",68}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",68},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",68}],Debug->True]//Timing

GraphData[{"CubicTransitive",68},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",68},"VertexList"],GraphData[{"CubicTransitive",68},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",68},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",68}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",68},"Matchstick"]

GraphData[{"CubicTransitive",68},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",68},"Edges"]]

3D All

GraphData[{"CubicTransitive",68},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",68},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",68},"Polyhedral"]

{"CubicTransitive", 69}

Names

GraphData[{"CubicTransitive",69},"StandardName"]

GraphData[{"CubicTransitive",69},"StandardNames"]

Primary

GraphData[{"CubicTransitive",69}]//StyleGraphs[#,ImageSize->Small]&

Construct from Read and Wilson

g=Graph[Range[32],UndirectedEdge@@@{{1,2},{1,3},{1,7},{2,4},{2,8},{3,6},{3,13},{4,5},{4,14},{5,9},{5,11},{6,10},{6,12},{7,9},{7,25},{8,10},{8,26},{9,19},{10,20},{11,12},{11,15},{12,16},{13,15},{13,23},{14,16},{14,24},{15,17},{16,18},{17,19},{17,21},{18,20},{18,22},{19,29},{20,30},{21,22},{21,27},{22,28},{23,25},{23,27},{24,26},{24,28},{25,31},{26,32},{27,30},{28,29},{29,31},{30,32},{31,32}},VertexCoordinates->(10^(-4)){{6528,-14068},{6528,-6509},{8668,-13181},{8668,-7396},{10712,-12334},{10712,-8243},{11870,-19414},{11870,-1164},{12756,-17273},{12756,-3305},{12851,-11447},{12851,-9130},{13603,-15227},{13603,-5350},{14489,-13086},{14489,-7491},{16805,-13086},{16805,-7491},{17691,-15227},{17691,-5350},{18442,-11447},{18442,-9130},{18538,-17273},{18538,-3305},{19424,-19414},{19424,-1164},{20582,-12334},{20582,-8243},{22626,-13181},{22626,-7396},{24766,-14068},{24766,-6509}}]

RecognizeGraph@g

All

GraphData[{"CubicTransitive",69},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",69},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",69},"Edges"]

v={#/7,#2/9}&@@@{{3,0},{4,0},{1,1},{2,1},{5,1},{6,1},{3,2},{4,2},{0,3},{1,3},{3,3},{4,3},{6,3},{7,3},{2,4},{5,4},{2,5},{5,5},{0,6},{1,6},{3,6},{4,6},{6,6},{7,6},{3,7},{4,7},{1,8},{2,8},{5,8},{6,8},{3,9},{4,9}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[27,19,9,3,1,5,6,14,24,30,32,28,27,31,29,30],e[3,4,2,6],e[9,20,25,31],e[14,23,26,32],e[19,10,11,8,2],e[24,13,12,7,1],e[4,15,17,28],e[5,16,18,29],{7,10},{8,13},e[20,21,26],e[23,22,25],{17,11},{15,21},{22,16},{18,12}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",69},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",69},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicTransitive",69},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",69},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",69},"Planar"]

GraphData[{"CubicTransitive",69},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",69},{"RCN","CN"}]

GraphData[{"CubicTransitive",69},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

GraphData[{"CubicTransitive",69},"V"]

GraphPlot@

v={#,-(#2+1)}&@@@{{0,-1},{-1,1},{0,1},{1,1},{-3,2},{-2,2},{0,2},{2,2},{3,2},{-1,3},{0,3},{1,3},{-2,4},{-1,4},{1,4},{2,4},{-3,3},{-6,3},{-1,5},{0,5},{1,5},{3,3},{6,3},{-2,6},{0,6},{2,6},{-3,7},{0,7},{3,7},{-3,10},{0,10},{3,10}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,9,8,7,6,5,1,3],e[18,2,3,4,23,32,31,30,18],e[5,17,27,28,29,22,9],{28,31},e[6,13,24,25,26,16,8],e[2,10,14,19,30],e[4,12,15,21,32],{7,11},e[10,11,12],{17,18},{22,23},{13,14},{15,16},e[19,20,21],{20,25},{24,27},{26,29}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

v=Join[CirclePoints[1,8],CirclePoints[(3/4),8],CirclePoints[x,8],CirclePoints[(1/4),8]];

FullSimplify[RegionDistance[Line@v[[{14,12}]],v[[21]]]==0,x>0]

Solve[%,x]

N[%]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",69},"Circulant"]

GraphData[{"CubicTransitive",69},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",69},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",69}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",69}&]

RootGraph[GraphData[{"CubicTransitive",69}]]

Halin

GraphData[{"CubicTransitive",69},"Halin"]

GraphData[{"CubicTransitive",69},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",69},"Rigid"]

GraphData[{"CubicTransitive",69},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",69},"Flexible"]

GraphData[{"CubicTransitive",69},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",69},"LCF"]

GraphData[{"CubicTransitive",69},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",69},"LCFSignature"]

GraphData[{"CubicTransitive",69},"LCFNotations"]

GraphData[{"CubicTransitive",69},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",69}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",69},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",69}],Debug->True]//Timing

GraphData[{"CubicTransitive",69},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",69},"VertexList"],GraphData[{"CubicTransitive",69},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

ContractCoincidentVertices[,Tolerance->.1]

RecognizeGraph@%125

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",69},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",69}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",69},"Matchstick"]

GraphData[{"CubicTransitive",69},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",69},"Edges"]]

3D All

GraphData[{"CubicTransitive",69},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",69},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",69},"Polyhedral"]

{"CubicTransitive", 70} == {"GeneralizedPetersen", {16, 7}}

GraphData[{"CubicTransitive",70},"StandardName"]

{"CubicTransitive", 71} == "DyckGraph"

GraphData[{"CubicTransitive",71},"StandardName"]

{"CubicTransitive", 72}

Names

GraphData[{"CubicTransitive",72},"StandardName"]

GraphData[{"CubicTransitive",72},"StandardNames"]

Primary

GraphData[{"CubicTransitive",72}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CubicTransitive",72},"Graph","All"]//StyleGraphs

Construction of Read and Wilson

g=Graph[Range[32],UndirectedEdge@@@{{1,2},{1,3},{1,5},{2,4},{2,6},{3,7},{3,9},{4,8},{4,10},{5,6},{5,21},{6,22},{7,11},{7,16},{8,12},{8,15},{9,11},{9,13},{10,12},{10,14},{11,27},{12,28},{13,15},{13,19},{14,16},{14,20},{15,17},{16,18},{17,19},{17,26},{18,20},{18,25},{19,23},{20,24},{21,23},{21,25},{22,24},{22,26},{23,29},{24,30},{25,29},{26,30},{27,28},{27,31},{28,32},{29,31},{30,32},{31,32}},VertexCoordinates->(10^(-4)){{8096,-12019},{8096,-8666},{9168,-14607},{9168,-6078},{9871,-11630},{9871,-9054},{10697,-13626},{10697,-7059},{11537,-16978},{11537,-3707},{12517,-15447},{12517,-5237},{14123,-18050},{14123,-2635},{14512,-16274},{14512,-4411},{17086,-16274},{17086,-4411},{17474,-18050},{17474,-2635},{19080,-15447},{19080,-5237},{20060,-16978},{20060,-3707},{20901,-13626},{20901,-7059},{21727,-11630},{21727,-9054},{22430,-14607},{22430,-6078},{23501,-12019},{23501,-8666}}]

RecognizeGraph@g

v=Join[CirclePoints[16],CirclePoints[3/4,16]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[{1,16},1],e[17,22,23,28,29,18,19,24,25,30,31,20,21,26,27,32,17],Sequence@@Table[{i,i+16},{i,16}]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",72},"EdgeList"]]

Default embedding

GraphPlot[GraphData[{"CubicTransitive",72},"Edges"],GraphLayout->"HighDimensionalEmbedding",VertexLabels->Automatic]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",72},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",72},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicTransitive",72},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",72},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",72},"Planar"]

GraphData[{"CubicTransitive",72},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",72},{"RCN","CN"}]

GraphData[{"CubicTransitive",72},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

GraphData[{"CubicTransitive",72},"V"]

GraphPlot@RotateGraph[,-2Pi/6]

v={#/9,#2/8}&@@@{{0,0},{9,0},{1,1},{8,1},{1,2},{8,2},{1,3},{2,3},{3,3},{4,3},{5,3},{6,3},{7,3},{8,3},{1,5},{2,5},{4,5},{5,5},{7,5},{8,5},{1,6},{2,6},{4,6},{5,6},{7,6},{8,6},{1,7},{8,7},{0,8},{9,8},{4,4},{5,4}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,3,5,7,29,27,21,15,1,2,20,26,28,30,14,6,4,2],{29,30},{27,28},{3,4},e[8,17,18,13],e[{7,14}],e[{21,26}],e[15,16,31,32,19,20],{5,9},{12,6},{10,31},{11,32},{16,22},{17,23},{18,24},{19,25}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@RotateGraph[,2Pi/5]

v={#/9,#2/7}&@@@{{0,0},{9,0},{1,1},{2,1},{3,1},{6,1},{7,1},{8,1},{2,2},{3,2},{6,2},{7,2},{1,3},{3,3},{4,3},{5,3},{6,3},{8,3},{3,4},{4,4},{5,4},{6,4},{2,5},{3,5},{6,5},{7,5},{2,6},{3,6},{6,6},{7,6},{0,7},{9,7}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,32,27,28,29,30,31,1,3,4,5,6,7,8,2],e[3,13,14,15],e[16,17,18,8],e[4,9,23,27],e[7,12,26,30],{23,24},{25,26},e[9,10,16,21],e[12,11,15,20],e[19,20,21,22],e[14,19,24,28],e[17,22,25,29],{5,10},{6,11},{13,31},{18,32}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@

v={#/15,#2/7}&@@@{{0,0},{15,0},{3,1},{12,1},{5,2},{6,2},{7,2},{8,2},{9,2},{10,2},{5,3},{6,3},{7,3},{8,3},{9,3},{10,3},{3,4},{4,4},{7,4},{8,4},{11,4},{12,4},{5,5},{10,5},{3,6},{4,6},{5,6},{10,6},{11,6},{12,6},{0,7},{15,7}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,32,31,1,5,6,7,8,9,10,2],e[3,4,22,30,29,28,27,26,25,17,3],e[5,11,23,27],e[10,16,24,28],e[{17,22}],{23,24},e[{11,16}],{3,7},{8,4},{31,25},{30,32},{18,26},{21,29},{19,13},{20,14},{12,6},{15,9}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

gs=UnlabelGraph/@{,,}

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

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

GraphPlot@HighlightGraph[RotateGraph[GraphicsToGraph@,{17,15}],Range[33,36]]

v=Join[CirclePoints[1,8],CirclePoints[(2/3),8],CirclePoints[(1/6),8]//FullSimplify];
v=Join[v,top={v[[#,1]],v[[14,2]]}&/@{20,21},{#,-#2}&@@@top,right={v[[9,1]],v[[#,2]]}&/@{18,19},{-#,#2}&@@@right];
g=Graph[Range[Length[v]],UndirectedEdge@@@Sort[Sort/@{Sequence@@Partition[Range[8],2,1,1],Sequence@@Partition[Range[17,24],2,1,1],e[9,29,30,12,13,32,31,16,9,1],e[6,14,15,28,27,10,11,25,26,14],{7,15},{8,16},{2,10},{3,11},{4,12},{5,13},{20,25},{21,26},{19,30},{18,29},{24,28},{17,27},{22,32},{23,31}}],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

CirclePoints[(2/3),8]

v[[5]]

UnitCirclePoints[8]

v[[9]]

v=Join[CirclePoints[1,8],CirclePoints[(2/3),8],CirclePoints[(1/6),8]//FullSimplify];
v=Join[v,top={v[[#,1]],v[[14,2]]}&/@{20,21},{#,-#2}&@@@top,right={v[[9,1]],v[[#,2]]}&/@{18,19},{-#,#2}&@@@right];
g=Graph[Range[Length[v]],UndirectedEdge@@@Sort[Sort/@{Sequence@@Partition[Range[8],2,1,1],Sequence@@Partition[Range[17,24],2,1,1],e[9,29,30,12,13,32,31,16,9,1],e[6,14,15,28,27,10,11,25,26,14],{7,15},{8,16},{2,10},{3,11},{4,12},{5,13},{20,25},{21,26},{19,30},{18,29},{24,28},{17,27},{22,32},{23,31}}],VertexCoordinates->v,VertexLabels->Automatic]

Circulant

GraphData[{"CubicTransitive",72},"Circulant"]

GraphData[{"CubicTransitive",72},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",72},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",72}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",72}&]

RootGraph[GraphData[{"CubicTransitive",72}]]

Halin

GraphData[{"CubicTransitive",72},"Halin"]

GraphData[{"CubicTransitive",72},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",72},"Rigid"]

GraphData[{"CubicTransitive",72},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",72},"Flexible"]

GraphData[{"CubicTransitive",72},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",72},"LCF"]

GraphData[{"CubicTransitive",72},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",72},"LCFSignature"]

GraphData[{"CubicTransitive",72},"LCFNotations"]

GraphData[{"CubicTransitive",72},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",72}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",72},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",72}],Debug->True]//Timing

GraphData[{"CubicTransitive",72},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",72},"VertexList"],GraphData[{"CubicTransitive",72},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",72},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",72}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",72},"Matchstick"]

GraphData[{"CubicTransitive",72},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",72},"Edges"]]

v=Flatten[Table[Append[#,i]&/@UnitCirclePoints[8],{i,-3/2,3/2}],1];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[{1,8},1],e[{25,32},25],e[1,9,18,26],e[25,17,10,2],e[3,11,20,28],e[27,19,12,4],e[5,13,22,30],e[29,21,14,6],e[31,23,16,8],e[32,24,15,7],Sequence@@Partition[Range[9,16],2,1,1][[2;;All;;2]],Sequence@@Partition[Range[17,24],2,1,1][[2;;All;;2]]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

3D All

GraphData[{"CubicTransitive",72},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",72},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",72},"Polyhedral"]

{"CubicTransitive", 73}

Names

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

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

Primary

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

Construct from Read and Wilson

g=Graph[Range[32],UndirectedEdge@@@{{1,2},{1,3},{1,6},{2,4},{2,5},{3,9},{3,11},{4,10},{4,12},{5,6},{5,21},{6,22},{7,9},{7,11},{7,16},{8,10},{8,12},{8,15},{9,13},{10,14},{11,27},{12,28},{13,17},{13,19},{14,18},{14,20},{15,17},{15,19},{16,18},{16,20},{17,26},{18,25},{19,23},{20,24},{21,25},{21,29},{22,26},{22,30},{23,25},{23,29},{24,26},{24,30},{27,28},{27,32},{28,31},{29,31},{30,32},{31,32}},VertexCoordinates->(10^(-4)){{8096,-12019},{8096,-8666},{9168,-14607},{9168,-6078},{9871,-11630},{9871,-9054},{10697,-13626},{10697,-7059},{11537,-16978},{11537,-3707},{12517,-15447},{12517,-5237},{14123,-18050},{14123,-2635},{14512,-16274},{14512,-4411},{17086,-16274},{17086,-4411},{17474,-18050},{17474,-2635},{19080,-15447},{19080,-5237},{20060,-16978},{20060,-3707},{20901,-13626},{20901,-7059},{21727,-11630},{21727,-9054},{22430,-14607},{22430,-6078},{23501,-12019},{23501,-8666}}]

RecognizeGraph@g

v=Join[CirclePoints[16],CirclePoints[3/4,16]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[{1,16},1],e[32,17,22,23,28,29,18,19,24,25,30,31,20,21,26,27,32],{16,17},Sequence@@Table[{i,i+17},{i,2,14,2}],Sequence@@Table[{i,i+15},{i,3,15,2}],{1,32}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",73},"EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",73},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",73},"Graph","Degenerate"]

Bilateral

GraphData[{"CubicTransitive",73},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",73},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",73},"Planar"]

GraphData[{"CubicTransitive",73},"Graph","Planar"]//StyleGraphs

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

GraphPlot@RotateGraph[,-Pi/8]

v={#/8,#2/10}&@@@{{0,0},{8,0},{2,1},{4,1},{0,2},{1,2},{5,2},{6,2},{7,2},{8,2},{2,3},{3,3},{5,3},{6,3},{2,4},{3,4},{4,4},{6,4},{4,5},{6,5},{3,6},{4,6},{3,7},{7,7},{8,7},{0,8},{1,8},{4,8},{4,9},{5,9},{0,10},{8,10}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,10,25,32,31,26,5,1,3,4,2],e[5,6,7,8,9,10],{29,30},e[26,27,28],e[23,24,25],{6,27},e[3,11,12,13,14],{9,24},e[8,14,18,20,29,31],e[32,30,15,12],e[11,16],{7,13},{19,20},{17,18},e[4,17,19,22,28,23,21,22],{16,21},{15,16}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphData[{"CubicTransitive",73},"V"]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",73}],"CrossingNumber"->8]

GraphPlot@HighlightGraph[RotateGraph[GraphicsToGraph@,{17,13}],Range[32+1,32+8]]

v={{2,0},{4,0},{2,1},{4,1},{0,2},{1,2},{5,2},{2,3},{3,3},{5,3},{6,3},{7,3},{8,3},{9,3},{4,4},{6,4},{2,5},{3,5},{4,5},{6,5},{3,6},{4,6},{3,7},{8,7},{9,7},{0,8},{1,8},{3,8},{1,11},{2,11},{1,12},{2,12}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,14,25,32,31,26,5,1],e[8,9,10,11,12,13,14],e[5,6,7],{3,4},e[1,3,8],e[2,4,15,19,22,28],{6,27},e[26,27,28],e[31,29,30,32],e[29,20,16,11],e[18,21,23,28],{17,30},e[9,17,18,8],e[23,24,25],{21,22},{19,20},e[10,7,12],{13,24},{15,16}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@UnlabelGraph@

g0=GraphicsToGraph@

v={#/9,#2/12}&@@@Round[GraphEmbedding[g0]]

g=Graph[Range[32],EdgeList[g0],VertexCoordinates->v]

RecognizeGraph@g

RectilinearCrossingCount@g

Circulant

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

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

Line graph

GraphData[{"CubicTransitive",73},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",73}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",73}&]

RootGraph[GraphData[{"CubicTransitive",73}]]

Halin

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

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

Rigid

GraphData[{"CubicTransitive",73},"Rigid"]

GraphData[{"CubicTransitive",73},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",73},"Flexible"]

GraphData[{"CubicTransitive",73},"Graph","Flexible"]//StyleGraphs

LCF

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

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

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

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

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

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

LCF compute all

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

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",73},"UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",73},"VertexList"],GraphData[{"CubicTransitive",73},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

g=IndexGraph@ContractCoincidentVertices[,Tolerance->.2]

RecognizeGraph@g

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",73},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",73}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

{"CubicTransitive", 74} == {"CrossedPrism", 16}

GraphData[{"CubicTransitive",74},"StandardName"]

{"CubicTransitive", 75} == {"Prism", 16}

GraphData[{"CubicTransitive",75},"StandardName"]

{"CubicTransitive", 76} == {"MoebiusLadder", 16}

GraphData[{"CubicTransitive",76},"StandardName"]

{"CubicTransitive", 77}

Names

GraphData[{"CubicTransitive",77},"StandardName"]

GraphData[{"CubicTransitive",77},"StandardNames"]

Primary

GraphData[{"CubicTransitive",77}]//StyleGraphs[#,ImageSize->Small]&

Construct from Read and Wilson

All

GraphData[{"CubicTransitive",77},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",77},"EdgeList"]]

Default embedding

g=Graph[GraphData[{"CubicTransitive",77},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",77},"Graph","Degenerate"]//StyleGraphs

GeneralizedHoneycombGraph construction

With[{n=34},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",77}}]]//Timing

gs=GeneralizedHoneycombGraph[34,#]&/@{5,13,15}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",77},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",77},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",77},"Planar"]

GraphData[{"CubicTransitive",77},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",77},{"RCN","CN"}]

GraphData[{"CubicTransitive",77},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",77}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",77}],"CrossingNumber"->cn,RandomSeed->i],{i,100}]//Union

GraphData[{"CubicTransitive",77},"V"]

GraphPlot@RotateGraph[,6Pi/8]

v={#/8,#2/11}&@@@{{0,0},{8,0},{2,1},{4,1},{7,1},{1,2},{3,2},{6,2},{7,2},{7,3},{2,4},{3,4},{5,4},{8,4},{1,5},{2,5},{2,6},{4,6},{0,7},{4,7},{5,7},{6,7},{4,8},{5,8},{2,9},{4,9},{6,9},{1,10},{2,10},{7,9},{7,10},{0,11},{5,11},{8,11}};
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,5,4,3,2,14,34,33,32,19,1,6,7,8,9,5],e[9,10,30,31,34],e[6,15,28,32],e[3,11,16,17,25,29],{15,16},e[11,12,13,14],e[13,21,24,33],e[8,22,27],e[28,29,31],e[25,26,27,30],{23,24},{21,22},e[4,18,20,23,26],{7,12},{19,20},{17,18},{2,10}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

GraphPlot@

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",77}],"CrossingNumber"->10]

v={{1,0},{6,0},{1,1},{3,1},{8,1},{10,1},{3,2},{5,2},{7,2},{8,2},{0,3},{4,3},{5,3},{6,3},{1,4},{2,4},{3,4},{4,4},{6,4},{0,5},{1,5},{0,6},{4,6},{6,6},{7-1/2,6},{2,7},{4-1/2,7},{1,8},{2,8},{6,8},{1,9},{6,9},{1,10},{8,10}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,6,30,32,34,33,22,20,11,1],e[5,10,34],e[3,4,5,6],e[1,3,15,21,28,31,33],e[7,8,9,10],e[15,16,17,18],{20,21},{22,23},{31,25},e[4,7,17],e[11,12,13,14],e[2,14,19,24,30],{8,13},e[12,18,23,27],e[16,26,29],{26,27},e[28,29],{27,32},{24,29},e[9,25,19]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",77},"Circulant"]

GraphData[{"CubicTransitive",77},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"CubicTransitive",77},"Halin"]

GraphData[{"CubicTransitive",77},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",77},"LCF"]

GraphData[{"CubicTransitive",77},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",77},"LCFSignature"]

GraphData[{"CubicTransitive",77},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",77}],All][[All,All,1]]]//Timing

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

LCFGraph@@@lcf//StyleGraphs

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

UnitDistance

GraphData[{"CubicTransitive",77},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",77}],Debug->True]//Timing

GraphData[{"CubicTransitive",77},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",77},"VertexList"],GraphData[{"CubicTransitive",77},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",77},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",77}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicTransitive",77},"Matchstick"]

GraphData[{"CubicTransitive",77},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",77},"Edges"]]

3D All

GraphData[{"CubicTransitive",77},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",77},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",77},"Polyhedral"]

GraphData[{"CubicTransitive",77},"Graph",{"3D","Polyhedron"}]

{"CubicTransitive", 78}

Names

GraphData[{"CubicTransitive",78},"StandardName"]

GraphData[{"CubicTransitive",78},"StandardNames"]

Primary

GraphData[{"CubicTransitive",78}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CubicTransitive",78},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicTransitive",78},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicTransitive",78},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicTransitive",78},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicTransitive",78},"Graph","Degenerate"]

CubicVertexTransitiveGraph

g=CubicVertexTransitiveGraph[34]

RecognizeGraph@g

GeneralizedHoneycombGraph construction

With[{n=34},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"CubicTransitive",78}}]]//Timing

gs=GeneralizedHoneycombGraph[34,#]&/@{3,7,9}

RecognizeGraph/@gs

Bilateral

GraphData[{"CubicTransitive",78},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicTransitive",78},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"CubicTransitive",78},"Planar"]

GraphData[{"CubicTransitive",78},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CubicTransitive",78},{"RCN","CN"}]

GraphData[{"CubicTransitive",78},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicTransitive",78}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@RotateGraph[,Pi/12]

GraphData[{"CubicTransitive",78},"V"]

Length[v]

{e[1,2,3,4,16,20,36,35,34,33,32,17,1,5,6,4],e[32,27,28,29,30,31,36],{17,18},{19,20},{15,16},{21,22},e[7,8,9,10],e[6,10,12,14,15,22,31],e[3,11,13,19,21,26,35],{2,9},e[5,7,27],e[8,18,23,28],e[23,25,26],{24,33},{25,30},{13,14}}/.i_Integer:>If[i>12,i-2,i]

v

v={#/8,#2/9}&@@@{{0,0},{5,0},{6,0},{8,0},{1,1},{7,1},{1,2},{2,2},{5,2},{7,2},{6,3},{7,3},{7,4},{8,4},{0,5},{2,5},{6,5},{8,5},{6,6},{7,6},{2,7},{3,7},{5,7},{6,7},{1,8},{2,8},{4,8},{5,8},{7,8},{0,9},{3,9},{4,9},{6,9},{8,9}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{{1,2},{2,3},{3,4},{4,14},{14,18},{18,34},{34,33},{33,32},{32,31},{31,30},{30,15},{15,1},{1,5},{5,6},{6,4},{30,25},{25,26},{26,27},{27,28},{28,29},{29,34},{15,16},{17,18},{13,14},{19,20},{7,8},{8,9},{9,10},{6,10},{10,12},{12,13},{13,20},{20,29},{3,11},{11,17},{17,19},{19,24},{24,33},{2,9},{5,7},{7,25},{8,16},{16,21},{21,26},{21,22},{22,23},{23,24},{22,31},{23,28},{11,12},{27,32}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphData[{"CubicTransitive",78},"V"]

GraphPlot@MinimalCrossingGraph[GraphData[{"CubicTransitive",78}],"CrossingNumber"->7]

GraphPlot@HighlightGraph[RotateGraph[GraphicsToGraph@,{3,33}],Range[34+1,34+7]]

v={{2,0},{4,0},{5,0},{8,0},{3,1},{4,1},{6,1},{8,1},{-1/2,2},{1/2,2},{2,2},{3,2},{5,2},{6,2},{7,2},{8,3},{1/2,3},{2,3},{7,3},{9,2},{1,4},{2,4},{6,4},{8,4},{9,4},{1,5},{2,5},{3,5},{4,5},{5,5},{6,5},{7,5},{1,6},{7,6}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[30,33,17,10,9,1,2,3,4,20,25,34,28],e[9,21,22,29],e[26,27,28,29,30,31,32],e[1,11,18,22],e[11,12,13,14,15,20],e[4,8,16,24],e[10,5,6,7,8],{2,6},{3,13},{7,14},{5,12},e[27,23,24,25],e[15,19,32,34],{23,31},{16,19},{17,18},{21,26},{26,33}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicTransitive",78},"Circulant"]

GraphData[{"CubicTransitive",78},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"CubicTransitive",78},"Line"]

LineGraphQ[GraphData[{"CubicTransitive",78}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicTransitive",78}&]

RootGraph[GraphData[{"CubicTransitive",78}]]

Halin

GraphData[{"CubicTransitive",78},"Halin"]

GraphData[{"CubicTransitive",78},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicTransitive",78},"Rigid"]

GraphData[{"CubicTransitive",78},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicTransitive",78},"Flexible"]

GraphData[{"CubicTransitive",78},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicTransitive",78},"LCF"]

GraphData[{"CubicTransitive",78},"HamiltonianCycleCount"]

GraphData[{"CubicTransitive",78},"LCFSignature"]

GraphData[{"CubicTransitive",78},"LCFNotations"]

GraphData[{"CubicTransitive",78},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"CubicTransitive",78}],All][[All,All,1]]]//Timing

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

lcf

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

GraphData[{"CubicTransitive",78},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicTransitive",78}],Debug->True]//Timing

GraphData[{"CubicTransitive",78},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicTransitive",78},"VertexList"],GraphData[{"CubicTransitive",78},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicTransitive",78},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicTransitive",78}],TimeConstraint->300,"Results"->All]//Timing}

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

gs={,,};

Matchstick

GraphData[{"CubicTransitive",78},"Matchstick"]

GraphData[{"CubicTransitive",78},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicTransitive",78},"Edges"]]

3D All

GraphData[{"CubicTransitive",78},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicTransitive",78},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicTransitive",78},"Polyhedral"]