Vertex-Transitive Graph

Author

Eric W. Weisstein
October 26, 2023

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

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

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

Classes

GraphClassesThatAreClass["VertexTransitive"]

Counts

SetDirectory["/Volumes/Users/eww/Mathematica/Paclets/GraphData/Collections/Royle/VertexTransitive/"];

NonCayley

Length/@(noncayleyvt=Table[Import["Noncayley/noncay"<>(d=If[n<10,"0",""]<>ToString[n])<>".g6.gz","AdjacencyMatrix"],{n,31}]/.$Failed:>{})//Timing

Last/@Partition[{0,0,0,0,0,0,0,0,0,2,0,0,0,0,4,8,0,4,0,82,0,0,0,112,0,132,0,66,0,1124,0},2]

Length[noncay=DeleteCases[Flatten[MapIndexed[RecognizeGraph[FromAdjacencyMatrix[#]]&,noncayleyvt,{2}],1],{}]]//Timing

GraphData[#,"V"]&/@{"GreatRhombicosidodecahedralGraph","IcosidodecahedralGraph"}

TableForm[Sort[GraphData[#,{"V","Name"}]&/@noncay],TableDepth->2]

GraphData["CayleyGraph"]

All

From McKay

Total[Boole[Get[#]]]&/@FileNames["*.m",FileNameJoin[{$GraphDataDirectory,"Nodes","VertexTransitive"}]]

From GraphData (complete only up to n=15)

A006799

Length[{1,2,2,4,3,8,4,14,9,22,8,74,14,56,48,286,36,380,60,1214,240,816,188,15506,464,4236,1434,25850,1182,46308,2192}]

Length/@Table[GraphData["VertexTransitive",n],{n,15}]

Length/@Table[GraphData["VertexTransitive",n],{n,16}]

GraphicsGrid[Flatten[Partition[#,5,5,{1,1},{}]&/@Map[GraphPlot[Graph[#],Method->None,PlotLabel->TextCell[GraphData[#,"Name"]PageWidth->65,TextAlignment->Center],BaseStyle->{FontSize->Scaled[.022]}]&,Take[l,7],{2}],1],ImageSize->400,BaseStyle->{FontSlant->Italic}]

From Royle's database

Monitor[Length/@Table[Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Collections/VertexTransitive/All/trans"<>(dig=If[i<10,"0",""]<>ToString[i])<>"/trans"<>dig<>".g6","AdjacencyMatrix"],{i,2,31}],i]//Timing

Length/@(vt=Table[Import["trans"<>(d=If[n<10,"0",""]<>ToString[n])<>".tar.gz",{"trans"<>d<>".g6","AdjacencyMatrix"}],{n,31}])//Timing

Map[RecognizeGraph[FromAdjacencyMatrix[#]]&,Take[vt,12],{2}]

Connected

From McKay

Table[Total[Boole[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","VertexTransitive","VertexTransitive_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[ConnectedGraphIndices[n]]]]],{n,10}]

From GraphData

Length/@(c=Select[#,ConnectedQ[GetGraph[#]]&]&/@l)

GraphicsGrid[Flatten[Partition[#,6,6,{1,1},{}]&/@Map[GraphPlot[Graph[#],Method->None,PlotLabel->TextCell[GraphData[#,"Name"],PageWidth->65,TextAlignment->Center],BaseStyle->{FontSize->Scaled[.022]}]&,Take[c,7],{2}],1],ImageSize->400,BaseStyle->{FontSlant->Italic}]

From Royle's database

Length/@(cvt=Table[Import["trans"<>(d=If[n<10,"0",""]<>ToString[n])<>".tar.gz",{"trans"<>d<>"c.g6","AdjacencyMatrix"}],{n,20}])//Timing

Royle's database of all (incl. disconnected) vertex-transitive graphs up to 31 nodes (complete up to 30)

SetDirectory["/Users/eww/Documents/Mathematica/Paclets/GraphData/Collections/Royle/VertexTransitive"]

Connected:

connectedvtfiles=FileNames["*c.g6"]

Not necessarily connected:

allvtfiles=Complement[FileNames["*.g6"],FileNames["*c.g6"]]

Connected:

Length/@(vtconnected=MapIndexed[{#,RecognizeGraph@#,{"VertexTransitive",#2}}&,Monitor[Import[file=#,{"Graph6","GraphList"}]&/@connectedvtfiles,file],{2}])//Timing//AbsoluteTiming

All:

Length/@(vt=MapIndexed[{#,RecognizeGraph@#,{"VertexTransitive",#2}}&,Monitor[Import[file=#,{"Graph6","GraphList"}]&/@allvtfiles,file],{2}])//Timing//AbsoluteTiming

new=Select[GraphData["VertexTransitive"],MissingQ[FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",_}]]&];

Union[GraphData[#,"V"]&/@new]

altstdnames=Select[DeleteCases[Flatten[Drop[vt,15],1],{_,{},_}],FreeQ[GraphData[#[[2]],"StandardNames"],#[[3]]]&]

l={#2,{0,SortBy[Union@Append[GraphData[#2,"AlternateStandardNames"],#3],First[Flatten[{#}]]&]}}&@@@altstdnames

PropertyReplace[l,"AlternateStandardNames","13.2"]

RenameGraphFiles[]

l2={#2,{0,Union[GraphData[#2,"AlternateNames"],{ToString[#3[[2,1]]]<>"\[Hyphen]vertex transitive graph "<>ToString[#3[[2,2]]]}]}}&@@@altstdnames

PropertyReplace[l2,"AlternateNames","13.2"]

RenameGraphFiles[]

l3={#2,{0,Union[Append[DeleteCases[GraphData[#2,"NotationRules"],HoldPattern[Rule["VertexTransitive",_Missing]]],Rule@@#3]]}}&@@@altstdnames

PropertyReplace[l3,"NotationRules","13.2"]

RenameGraphFiles[]

Enumeration

Off[General::"spell"];

Length/@(vt=Table[Select[Graphs[n],VertexTransitiveGraphQ],{n,7}])//Timing

Length/@(vt=Select[#,VertexTransitiveGraphQ]&/@Graphs/@Range[9])//Timing

Off[General::"stop"]

ShowGraphArray[
Flatten[
Partition[#,8,8,{1,1},{}]&/@Map[RecognizeGraph,vt,{2}],
1],
GraphicsSpacing->.3,
VertexStyle->Disk[.12],
VertexColor->Red
]

Connected Simple Graphs

Length/@(convt=Select[#,ConnectedQ]&/@vt)//Timing

ShowGraphArray[Map[RecognizeGraph,Flatten[Partition[#,8,8,{1,1},{}]&/@convt,1],{2}],
GraphicsSpacing->.3,VertexStyle->Disk[.1],VertexColor->Red]//Timing

Algorithms

GAP

DeleteCases[Monitor[{g=#, GraphData[#, "VertexTransitive"], FastVertexTransitiveGraphQ[Graph[#]]}& /@ GraphData[;; 4],g],{_,x_,x_}]//Timing//AbsoluteTiming

DeleteCases[Monitor[{g=#, GraphData[#, "VertexTransitive"], FastVertexTransitiveGraphQ[Graph[#]]}& /@ GraphData[;; 5],g],{_,x_,x_}]//Timing//AbsoluteTiming

Banner Graph

Show[GraphData["BannerGraph","LabeledImage"],ImageSize->Small]

AutomorphismGroup[GraphData["BannerGraph"]]

FastVertexTransitiveGraphQ[Graph["BannerGraph"],Debug->True]

GraphData["BannerGraph","VertexTransitive"]

{“Cycle”, 4}

Show[GraphData["C4","LabeledImage"],ImageSize->Small]

AutomorphismGroup[GraphData["C4"]]

FastVertexTransitiveGraphQ[Graph["C4"],Debug->True]

GraphData["C4","VertexTransitive"]

{“Cycle”, 3}

Show[GraphData["C3","LabeledImage"],ImageSize->Small]

AutomorphismGroup[GraphData["C3"]]

FastVertexTransitiveGraphQ[Graph["C3"],Debug->True]

GraphData["C4","VertexTransitive"]

“ButterflyGraph”

Show[GraphData["ButterflyGraph","LabeledImage"],ImageSize->Small]

AutomorphismGroup[GraphData["ButterflyGraph"]]

FastVertexTransitiveGraphQ[Graph["ButterflyGraph"],Debug->True]

GraphData["ClawGraph","VertexTransitive"]

“ClawGraph”

Show[GraphData["ClawGraph","LabeledImage"],ImageSize->Small]

AutomorphismGroup[GraphData["ClawGraph"]]

FastVertexTransitiveGraphQ[Graph["ClawGraph"],Debug->True]

GraphData["ClawGraph","VertexTransitive"]

IGraphM

$Version

<<IGraphM`

DeleteCases[igvertextransitiveq=Monitor[{g=#,GraphData[#,"VertexTransitive"],IGVertexTransitiveGraphQ[GraphData[#]]//Timing}&/@GraphData[All],g],{_,x_,{_,x_}}]//Timing//AbsoluteTiming

Nauty

Monitor[
Complements[{
Select[GraphData[All],VertexTransitiveGraphQ[Graph[g=#]]&],
GraphData["VertexTransitive"]
}],g]//Timing

MyVertexTransitiveGraphQ

$Version

DeleteCases[Monitor[{g=#,GraphData[#,"VertexTransitive"],MyVertexTransitiveGraphQ[GraphData[#]]}&/@GraphData[All],g],{_,x_,x_}]//Timing

VertexTransitiveGraphQ

$Version

DeleteCases[Monitor[vertextransitivegraphq={g=#,GraphData[#,"VertexTransitive"],VertexTransitiveGraphQ[GraphData[#]]//Timing}&/@GraphData[All],g],{_,x_,{_,x_}}]//Timing//AbsoluteTiming

data=Reverse[SortBy[{#,#2,#3,#3/#2}&@@@Transpose[{igvertextransitiveq[[All,1]],igvertextransitiveq[[All,3,1]],vertextransitivegraphq[[All,3,1]]}],Last]];

Take[data,20]

plotdata=Take[#4->#1&@@@data,200]

ListLogPlot[plotdata,ImageSize->Large]

g=GraphData[{"GoethalsSeidelBlockDesign",{5,11}}];

RepeatedTiming[IGVertexTransitiveGraphQ[g]]

RepeatedTiming[VertexTransitiveGraphQ[g]]

Embeddings

<<MathWorld`Graphs`

Counts[GraphData[#,"V"]&/@GraphData["VertexTransitive*"]]

Intersection[GraphData["VertexTransitive*"],GraphData["Disconnected"]]

1

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},1]],Dividers->All]

2

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},2]],Dividers->All]

3

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},3]],Dividers->All]

4

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},4]],Dividers->All]

5

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},5]],Dividers->All]

6

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},6]],Dividers->All]

7

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},7]],Dividers->All]

8

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},8]],Dividers->All]

9

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},9]],Dividers->All]

10

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},10]],Dividers->All]

11

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},11]],Dividers->All]

12

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},12]],Dividers->All]

{"VertexTransitive", {12, 27}}

Names

GraphData[{"VertexTransitive",{12,27}},"StandardName"]

GraphData[{"VertexTransitive",{12,27}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{12,27}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{12,27}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,27}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,27}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{12,27}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,27}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,27}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,27}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,27}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,27}},"Planar"]

GraphData[{"VertexTransitive",{12,27}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,27}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{12,27}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,27}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,27}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,27}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,27}}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,27}},"Circulant"]

GraphData[{"VertexTransitive",{12,27}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"VertexTransitive",{12,27}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,27}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,27}}&]

RootGraph[GraphData[{"VertexTransitive",{12,27}}]]

Halin

GraphData[{"VertexTransitive",{12,27}},"Halin"]

GraphData[{"VertexTransitive",{12,27}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{12,27}},"Rigid"]

GraphData[{"VertexTransitive",{12,27}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,27}},"Flexible"]

GraphData[{"VertexTransitive",{12,27}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,27}},"LCF"]

GraphData[{"VertexTransitive",{12,27}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,27}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,27}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,27}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,27}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,27}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//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[{"VertexTransitive",{12,27}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,27}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,27}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,27}},"VertexList"],GraphData[{"VertexTransitive",{12,27}},"EdgeList"]],MaxIterations->500]

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

GraphPlot@RotateGraph[,{9,10}]

GraphPlot@RotateGraph[,{5,3}]

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

RecognizeGraph@g

GraphPlot@RotateGraph[,{3,6}]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,27}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,27}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,27}},"Matchstick"]

GraphData[{"VertexTransitive",{12,27}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,27}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{12,27}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,27}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,27}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,27}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 28}}

Names

GraphData[{"VertexTransitive",{12,28}},"StandardName"]

GraphData[{"VertexTransitive",{12,28}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,28}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,28}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Perspective

GraphData[{"VertexTransitive",{12,28}},"Graph","Perspective"]//StyleGraphs

Bilateral

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

Circular

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

Planar

GraphData[{"VertexTransitive",{12,28}},"Planar"]

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

MinimalCrossing

GraphData[{"VertexTransitive",{12,28}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,28}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@RotateGraph[,-Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,28}},"Circulant"]

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

Line graph

GraphData[{"VertexTransitive",{12,28}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,28}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"VertexTransitive",{12,28}}]]

Halin

GraphData[{"VertexTransitive",{12,28}},"Halin"]

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

Rigid

GraphData[{"VertexTransitive",{12,28}},"Rigid"]

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

Flexible

GraphData[{"VertexTransitive",{12,28}},"Flexible"]

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

LCF

GraphData[{"VertexTransitive",{12,28}},"LCF"]

GraphData[{"VertexTransitive",{12,28}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,28}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,28}},"LCFNotations"]

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

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

LCF compute all

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

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//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]

(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,{_,XXX}]]}])//Timing

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,28}},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

GraphPlot@RotateGraph[,{9,5}]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"VertexTransitive",{12,28}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"VertexTransitive",{12,28}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"VertexTransitive",{12,28}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,28}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 30}}

Names

GraphData[{"VertexTransitive",{12,30}},"StandardName"]

GraphData[{"VertexTransitive",{12,30}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{12,30}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{12,30}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,30}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,30}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{12,30}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,30}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,30}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,30}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,30}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,30}},"Planar"]

GraphData[{"VertexTransitive",{12,30}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,30}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{12,30}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,30}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,30}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,30}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,30}}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,30}},"Circulant"]

GraphData[{"VertexTransitive",{12,30}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"VertexTransitive",{12,30}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,30}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,30}}&]

RootGraph[GraphData[{"VertexTransitive",{12,30}}]]

Halin

GraphData[{"VertexTransitive",{12,30}},"Halin"]

GraphData[{"VertexTransitive",{12,30}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{12,30}},"Rigid"]

GraphData[{"VertexTransitive",{12,30}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,30}},"Flexible"]

GraphData[{"VertexTransitive",{12,30}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,30}},"LCF"]

GraphData[{"VertexTransitive",{12,30}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,30}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,30}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,30}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,30}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,30}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//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]

(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|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,2}]]}])//Timing

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,30}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,30}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,30}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,30}},"VertexList"],GraphData[{"VertexTransitive",{12,30}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,30}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,30}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{ {"VertexTransitive",{12,30}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,30}}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"VertexTransitive",{12,30}},"Matchstick"]

GraphData[{"VertexTransitive",{12,30}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,30}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{12,30}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,30}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,30}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,30}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 32}}

GraphData[{"VertexTransitive",{12,32}},"StandardName"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,32}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,32}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Planar

GraphData[{"VertexTransitive",{12,32}},"Planar"]

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

MinimalCrossing

GraphData[{"VertexTransitive",{12,32}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,32}}],"CrossingNumber"->7,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,32}},"Circulant"]

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

Halin

GraphData[{"VertexTransitive",{12,32}},"Halin"]

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

Rigid

GraphData[{"VertexTransitive",{12,32}},"Rigid"]

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

Flexible

GraphData[{"VertexTransitive",{12,32}},"Flexible"]

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

LCF

GraphData[{"VertexTransitive",{12,32}},"LCF"]

GraphData[{"VertexTransitive",{12,32}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,32}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,32}},"LCFNotations"]

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

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

LCF compute all

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

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,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[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]}])//Timing

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,32}},"UnitDistance"]

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,32}},"VertexList"],GraphData[{"VertexTransitive",{12,32}},"EdgeList"]]]

GraphPlot@

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

RecognizeGraph@g

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

GraphPlot@RotateGraph[,{3,11}]

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

VertexDegree[g]

RecognizeGraph@g

RotateGraph[,{11,5}]

GraphicsToGraph@

RotateGraph[,Pi/2]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"VertexTransitive",{12,32}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"VertexTransitive",{12,32}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"VertexTransitive",{12,32}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,32}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 40}}

Names

GraphData[{"VertexTransitive",{12,40}},"StandardName"]

GraphData[{"VertexTransitive",{12,40}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{12,40}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{12,40}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,40}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,40}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{12,40}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,40}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,40}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,40}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,40}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,40}},"Planar"]

GraphData[{"VertexTransitive",{12,40}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,40}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{12,40}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,40}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,40}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,40}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,40}}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,40}},"Circulant"]

GraphData[{"VertexTransitive",{12,40}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"VertexTransitive",{12,40}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,40}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,40}}&]

RootGraph[GraphData[{"VertexTransitive",{12,40}}]]

Halin

GraphData[{"VertexTransitive",{12,40}},"Halin"]

GraphData[{"VertexTransitive",{12,40}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{12,40}},"Rigid"]

GraphData[{"VertexTransitive",{12,40}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,40}},"Flexible"]

GraphData[{"VertexTransitive",{12,40}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,40}},"LCF"]

GraphData[{"VertexTransitive",{12,40}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,40}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,40}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,40}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,40}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,40}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//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]

(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,{_,XXX}]]}])//Timing

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,40}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,40}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,40}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,40}},"VertexList"],GraphData[{"VertexTransitive",{12,40}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

gs={RotateGraph[,{5,7}],RotateGraph[,{6,3}]}

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,40}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,40}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,40}},"Matchstick"]

GraphData[{"VertexTransitive",{12,40}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,40}},"Edges"]]

v=GraphData["IcosahedralGraph","Embeddings","3D"];

ee=GraphData["IcosahedralGraph","Edges","List"]

eeall=Join[ee,Select[Subsets[Range[12],{2}],RegionDistance[N@Line[v[[#]]],{0,0,0}]<.01&]//Quiet]

g=Graph[Range@Length@v,UndirectedEdge@@@eeall,VertexCoordinates->v]

RecognizeGraph@g

3D All

GraphData[{"VertexTransitive",{12,40}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,40}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,40}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,40}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 45}}

Names

GraphData[{"VertexTransitive",{12,45}},"StandardName"]

GraphData[{"VertexTransitive",{12,45}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{12,45}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{12,45}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,45}},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph@GraphData[{"VertexTransitive",{12,45}},"Edges"],Pi/2]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{12,45}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,45}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,45}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,45}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,45}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,45}},"Planar"]

GraphData[{"VertexTransitive",{12,45}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,45}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{12,45}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,45}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,45}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,45}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,45}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,45}},"Circulant"]

GraphData[{"VertexTransitive",{12,45}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"VertexTransitive",{12,45}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,45}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,45}}&]

RootGraph[GraphData[{"VertexTransitive",{12,45}}]]

Halin

GraphData[{"VertexTransitive",{12,45}},"Halin"]

GraphData[{"VertexTransitive",{12,45}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{12,45}},"Rigid"]

GraphData[{"VertexTransitive",{12,45}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,45}},"Flexible"]

GraphData[{"VertexTransitive",{12,45}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,45}},"LCF"]

GraphData[{"VertexTransitive",{12,45}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,45}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,45}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,45}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,45}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,45}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//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]

(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|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,2}]]}])//Timing

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,45}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,45}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,45}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,45}},"VertexList"],GraphData[{"VertexTransitive",{12,45}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

RotateGraph[,{5,7}]

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

RecognizeGraph@g

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,45}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,45}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,45}},"Matchstick"]

GraphData[{"VertexTransitive",{12,45}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,45}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{12,45}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,45}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,45}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,45}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 47}}

Names

GraphData[{"VertexTransitive",{12,47}},"StandardName"]

GraphData[{"VertexTransitive",{12,47}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,47}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,47}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Perspective

GraphData[{"VertexTransitive",{12,47}},"Graph","Perspective"]//StyleGraphs

Bilateral

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

Circular

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

Planar

GraphData[{"VertexTransitive",{12,47}},"Planar"]

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

MinimalCrossing

GraphData[{"VertexTransitive",{12,47}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,47}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,47}},"Circulant"]

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

Line graph

GraphData[{"VertexTransitive",{12,47}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,47}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"VertexTransitive",{12,47}}]]

Halin

GraphData[{"VertexTransitive",{12,47}},"Halin"]

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

Rigid

GraphData[{"VertexTransitive",{12,47}},"Rigid"]

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

Flexible

GraphData[{"VertexTransitive",{12,47}},"Flexible"]

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

LCF

GraphData[{"VertexTransitive",{12,47}},"LCF"]

GraphData[{"VertexTransitive",{12,47}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,47}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,47}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,47}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,47}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,47}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//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]

(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|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,2}]]}])//Timing

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,47}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,47}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,47}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,47}},"VertexList"],GraphData[{"VertexTransitive",{12,47}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

g=RotateGraph[,{6,4}]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,47}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,47}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,47}},"Matchstick"]

GraphData[{"VertexTransitive",{12,47}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,47}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{12,47}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,47}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,47}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,47}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 48}}

Names

GraphData[{"VertexTransitive",{12,48}},"StandardName"]

GraphData[{"VertexTransitive",{12,48}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{12,48}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{12,48}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,48}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,48}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{12,48}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,48}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,48}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,48}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,48}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,48}},"Planar"]

GraphData[{"VertexTransitive",{12,48}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,48}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{12,48}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,48}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,48}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,48}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,48}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,48}},"Circulant"]

GraphData[{"VertexTransitive",{12,48}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"VertexTransitive",{12,48}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,48}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,48}}&]

RootGraph[GraphData[{"VertexTransitive",{12,48}}]]

Halin

GraphData[{"VertexTransitive",{12,48}},"Halin"]

GraphData[{"VertexTransitive",{12,48}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{12,48}},"Rigid"]

GraphData[{"VertexTransitive",{12,48}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,48}},"Flexible"]

GraphData[{"VertexTransitive",{12,48}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,48}},"LCF"]

GraphData[{"VertexTransitive",{12,48}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,48}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,48}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,48}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,48}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,48}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

(gs=NiceLCFGraphs[lcf,2,1])//Timing

Length[gs]

(gs=NiceLCFGraphs[lcf,3,2])//Timing

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,48}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,48}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,48}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,48}},"VertexList"],GraphData[{"VertexTransitive",{12,48}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

g=RotateGraph[,{5,4}]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,48}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,48}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,48}},"Matchstick"]

GraphData[{"VertexTransitive",{12,48}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,48}},"Edges"]]

g=EdgeAdd[GraphData[{"Prism",6},"Graph",{"3D","Labeled"}],UndirectedEdge@@@{{3,6},{1,4},{2,5},{7,10},{11,8},{12,9},{12,1},{1,8},{8,3},{3,10},{10,5},{5,12},{7,2},{2,9},{9,4},{4,11},{11,6},{6,7}}]

RecognizeGraph@g

3D All

GraphData[{"VertexTransitive",{12,48}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,48}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,48}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,48}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 51}}

Names

GraphData[{"VertexTransitive",{12,51}},"StandardName"]

GraphData[{"VertexTransitive",{12,51}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{12,51}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{12,51}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,51}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,51}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{12,51}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,51}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,51}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,51}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,51}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,51}},"Planar"]

GraphData[{"VertexTransitive",{12,51}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,51}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{12,51}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,51}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,51}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,51}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,51}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,51}},"Circulant"]

GraphData[{"VertexTransitive",{12,51}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"VertexTransitive",{12,51}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,51}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,51}}&]

RootGraph[GraphData[{"VertexTransitive",{12,51}}]]

Halin

GraphData[{"VertexTransitive",{12,51}},"Halin"]

GraphData[{"VertexTransitive",{12,51}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{12,51}},"Rigid"]

GraphData[{"VertexTransitive",{12,51}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,51}},"Flexible"]

GraphData[{"VertexTransitive",{12,51}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,51}},"LCF"]

GraphData[{"VertexTransitive",{12,51}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,51}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,51}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,51}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,51}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,51}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

(gs=NiceLCFGraphs[lcf,2,1])//Timing

Length[gs]

(gs=NiceLCFGraphs[lcf,3,2])//Timing

Tally[LCFNotation[#][[-1]]&/@gs]

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,51}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,51}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,51}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,51}},"VertexList"],GraphData[{"VertexTransitive",{12,51}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

g=RotateGraph[,{4,10}]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,51}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,51}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,51}},"Matchstick"]

GraphData[{"VertexTransitive",{12,51}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,51}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{12,51}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,51}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,51}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,51}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 54}}

Names

GraphData[{"VertexTransitive",{12,54}},"StandardName"]

GraphData[{"VertexTransitive",{12,54}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{12,54}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{12,54}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,54}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,54}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{12,54}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,54}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,54}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,54}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,54}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,54}},"Planar"]

GraphData[{"VertexTransitive",{12,54}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,54}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{12,54}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,54}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,54}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,54}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,54}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,54}},"Circulant"]

GraphData[{"VertexTransitive",{12,54}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"VertexTransitive",{12,54}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,54}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,54}}&]

RootGraph[GraphData[{"VertexTransitive",{12,54}}]]

Halin

GraphData[{"VertexTransitive",{12,54}},"Halin"]

GraphData[{"VertexTransitive",{12,54}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{12,54}},"Rigid"]

GraphData[{"VertexTransitive",{12,54}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,54}},"Flexible"]

GraphData[{"VertexTransitive",{12,54}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,54}},"LCF"]

GraphData[{"VertexTransitive",{12,54}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,54}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,54}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,54}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,54}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,54}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

(gs=NiceLCFGraphs[lcf,2,None])//Timing

Tally[LCFNotation[#][[-1]]&/@gs]

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,54}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,54}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,54}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,54}},"VertexList"],GraphData[{"VertexTransitive",{12,54}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

gs={RotateGraph[,{2,10}],RotateGraph[,{11,12}],RotateGraph[,{5,6}]}

g=RotateGraph[,{7,11}]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,54}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,54}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,54}},"Matchstick"]

GraphData[{"VertexTransitive",{12,54}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,54}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{12,54}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,54}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,54}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,54}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 55}}

Names

GraphData[{"VertexTransitive",{12,55}},"StandardName"]

GraphData[{"VertexTransitive",{12,55}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{12,55}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{12,55}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,55}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,55}},"Edges"]

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

RecognizeGraph[g]

GraphPlot@RotateGraph[Graph[GraphData[{"VertexTransitive",{12,55}},"Edges"],GraphLayout->"HighDimensionalEmbedding"],{10,5}]

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

RecognizeGraph@g

gs=UnlabelGraph/@{,}

Degenerate

GraphData[{"VertexTransitive",{12,55}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,55}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,55}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,55}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,55}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,55}},"Planar"]

GraphData[{"VertexTransitive",{12,55}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,55}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{12,55}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,55}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,55}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,55}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,55}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,55}},"Circulant"]

GraphData[{"VertexTransitive",{12,55}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"VertexTransitive",{12,55}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,55}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,55}}&]

RootGraph[GraphData[{"VertexTransitive",{12,55}}]]

Halin

GraphData[{"VertexTransitive",{12,55}},"Halin"]

GraphData[{"VertexTransitive",{12,55}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{12,55}},"Rigid"]

GraphData[{"VertexTransitive",{12,55}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,55}},"Flexible"]

GraphData[{"VertexTransitive",{12,55}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,55}},"LCF"]

GraphData[{"VertexTransitive",{12,55}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,55}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,55}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,55}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,55}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,55}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

(gs=NiceLCFGraphs[lcf,3,2])//Timing

Tally[LCFNotation[#][[-1]]&/@gs]

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,55}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,55}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,55}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,55}},"VertexList"],GraphData[{"VertexTransitive",{12,55}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

gs={RotateGraph[,{1,2}],RotateGraph[,{5,7}],RotateGraph[,{9,4}],RotateGraph[,{9,10}],RotateGraph[,{9,4}],RotateGraph[,{11,12}]}

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,55}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,55}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,55}},"Matchstick"]

GraphData[{"VertexTransitive",{12,55}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,55}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{12,55}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,55}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,55}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,55}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 60}}

Names

GraphData[{"VertexTransitive",{12,60}},"StandardName"]

GraphData[{"VertexTransitive",{12,60}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{12,60}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{12,60}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,60}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,60}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{12,60}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,60}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,60}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,60}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,60}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,60}},"Planar"]

GraphData[{"VertexTransitive",{12,60}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,60}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{12,60}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,60}}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,60}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,60}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,60}},"Circulant"]

GraphData[{"VertexTransitive",{12,60}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"VertexTransitive",{12,60}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,60}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,60}}&]

RootGraph[GraphData[{"VertexTransitive",{12,60}}]]

Halin

GraphData[{"VertexTransitive",{12,60}},"Halin"]

GraphData[{"VertexTransitive",{12,60}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{12,60}},"Rigid"]

GraphData[{"VertexTransitive",{12,60}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,60}},"Flexible"]

GraphData[{"VertexTransitive",{12,60}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,60}},"LCF"]

GraphData[{"VertexTransitive",{12,60}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,60}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,60}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,60}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,60}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,60}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

(gs=NiceLCFGraphs[lcf,3,2])//Timing

Tally[LCFNotation[#][[-1]]&/@gs]

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,60}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,60}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,60}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,60}},"VertexList"],GraphData[{"VertexTransitive",{12,60}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,60}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,60}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,60}},"Matchstick"]

GraphData[{"VertexTransitive",{12,60}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,60}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{12,60}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,60}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,60}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,60}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 64}}

Names

GraphData[{"VertexTransitive",{12,64}},"StandardName"]

GraphData[{"VertexTransitive",{12,64}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,64}},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph[GraphData[{"VertexTransitive",{12,64}},"Edges"],GraphLayout->"HighDimensionalEmbedding"],{3,12}]

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

VertexDegree[g]

RecognizeGraph[g]

Degenerate

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

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

Perspective

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

Bilateral

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

Circular

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

Planar

GraphData[{"VertexTransitive",{12,64}},"Planar"]

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

MinimalCrossing

GraphData[{"VertexTransitive",{12,64}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,64}},"Circulant"]

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

Line graph

GraphData[{"VertexTransitive",{12,64}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,64}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"VertexTransitive",{12,64}}]]

Halin

GraphData[{"VertexTransitive",{12,64}},"Halin"]

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

Rigid

GraphData[{"VertexTransitive",{12,64}},"Rigid"]

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

Flexible

GraphData[{"VertexTransitive",{12,64}},"Flexible"]

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

LCF

GraphData[{"VertexTransitive",{12,64}},"LCF"]

GraphData[{"VertexTransitive",{12,64}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,64}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,64}},"LCFNotations"]

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

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

LCF compute all

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

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

(gs=NiceLCFGraphs[lcf,3,None])//Timing

Tally[LCFNotation[#][[-1]]&/@gs]

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,64}},"UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,64}},"VertexList"],GraphData[{"VertexTransitive",{12,64}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

gs={RotateGraph[,{2,6}],RotateGraph[,{10,7}],RotateGraph[,{5,8}]}

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,64}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,64}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,64}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"VertexTransitive",{12,64}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"VertexTransitive",{12,64}},"Polyhedral"]

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

{"VertexTransitive", {12, 65}}

Names

GraphData[{"VertexTransitive",{12,65}},"StandardName"]

GraphData[{"VertexTransitive",{12,65}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{12,65}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{12,65}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,65}},"EdgeList"]]

Default embedding

GraphPlot[GraphData[{"VertexTransitive",{12,65}},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{12,65}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,65}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,65}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,65}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,65}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,65}},"Planar"]

GraphData[{"VertexTransitive",{12,65}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,65}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{12,65}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,65}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,65}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,65}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,65}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,65}},"Circulant"]

GraphData[{"VertexTransitive",{12,65}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"VertexTransitive",{12,65}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,65}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,65}}&]

RootGraph[GraphData[{"VertexTransitive",{12,65}}]]

Halin

GraphData[{"VertexTransitive",{12,65}},"Halin"]

GraphData[{"VertexTransitive",{12,65}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{12,65}},"Rigid"]

GraphData[{"VertexTransitive",{12,65}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,65}},"Flexible"]

GraphData[{"VertexTransitive",{12,65}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,65}},"LCF"]

GraphData[{"VertexTransitive",{12,65}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,65}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,65}},"LCFNotations"]

GraphData[{"VertexTransitive",{12,65}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{12,65}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{12,65}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

gs=NiceLCFGraphs[lcf,3,2];//Timing

Tally[LCFNotation[#][[-1]]&/@gs]

(gs=NiceLCFGraphs[lcf,3,None])//Timing

Tally[LCFNotation[#][[-1]]&/@gs]

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,65}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{12,65}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{12,65}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,65}},"VertexList"],GraphData[{"VertexTransitive",{12,65}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

gs={RotateGraph[,{12,11}],RotateGraph[,{8,1}]}

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,65}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,65}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,65}},"Matchstick"]

GraphData[{"VertexTransitive",{12,65}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{12,65}},"Edges"]]

Transpose[{Range[6],RotateLeft@Range[7,12]}]

g=SimpleGraph@EdgeAdd[GraphData[{"Prism",6},"Graph",{"3D","Labeled"}],UndirectedEdge@@@Join[Subsets[Range[6],{2}],Subsets[Range[7,12],{2}],Transpose[{Range[6],RotateLeft@Range[7,12]}],Transpose[{Range[6],RotateRight@Range[7,12]}]]]

RecognizeGraph@g

3D All

GraphData[{"VertexTransitive",{12,65}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{12,65}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{12,65}},"Polyhedral"]

GraphData[{"VertexTransitive",{12,65}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {12, 67}}

Names

GraphData[{"VertexTransitive",{12,67}},"StandardName"]

GraphData[{"VertexTransitive",{12,67}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{12,67}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{12,67}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{12,67}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{12,67}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{12,67}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"VertexTransitive",{12,67}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{12,67}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{12,67}},"Planar"]

GraphData[{"VertexTransitive",{12,67}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{12,67}},{"RCN","CN"}]

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

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,67}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{12,67}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,67}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{12,67}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{12,67}},"Circulant"]

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

Line graph

GraphData[{"VertexTransitive",{12,67}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{12,67}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{12,67}}&]

RootGraph[GraphData[{"VertexTransitive",{12,67}}]]

Halin

GraphData[{"VertexTransitive",{12,67}},"Halin"]

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

Rigid

GraphData[{"VertexTransitive",{12,67}},"Rigid"]

GraphData[{"VertexTransitive",{12,67}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{12,67}},"Flexible"]

GraphData[{"VertexTransitive",{12,67}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{12,67}},"LCF"]

GraphData[{"VertexTransitive",{12,67}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{12,67}},"LCFSignature"]

GraphData[{"VertexTransitive",{12,67}},"LCFNotations"]

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

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

LCF compute all

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

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

gs

Length[gs]

UnitDistance

GraphData[{"VertexTransitive",{12,67}},"UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{12,67}},"VertexList"],GraphData[{"VertexTransitive",{12,67}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

g=RotateGraph[,{7,1}]

LabelGraph@RotateGraph[,{12,2}]

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

RecognizeGraph@g

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,67}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{12,67}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{12,67}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"VertexTransitive",{12,67}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"VertexTransitive",{12,67}},"Polyhedral"]

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

14

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},14]],Dividers->All]

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@Cases[GraphData[{"VertexTransitive","Connected"},14],{"VertexTransitive",_}]],Dividers->All]

{"VertexTransitive", {14, 16}}

Names

GraphData[{"VertexTransitive",{14,16}},"StandardName"]

GraphData[{"VertexTransitive",{14,16}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{14,16}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{14,16}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{14,16}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{14,16}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{14,16}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{14,16}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{14,16}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"VertexTransitive",{14,16}},"Polyhedron"]

Bilateral

GraphData[{"VertexTransitive",{14,16}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{14,16}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{14,16}},"Planar"]

GraphData[{"VertexTransitive",{14,16}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{14,16}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{14,16}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{14,16}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{14,16}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,16}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,16}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{14,16}},"Circulant"]

GraphData[{"VertexTransitive",{14,16}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"VertexTransitive",{14,16}},"ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

Line graph

GraphData[{"VertexTransitive",{14,16}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{14,16}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{14,16}}&]

RootGraph[GraphData[{"VertexTransitive",{14,16}}]]

Halin

GraphData[{"VertexTransitive",{14,16}},"Halin"]

GraphData[{"VertexTransitive",{14,16}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{14,16}},"Rigid"]

GraphData[{"VertexTransitive",{14,16}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{14,16}},"Flexible"]

GraphData[{"VertexTransitive",{14,16}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{14,16}},"LCF"]

GraphData[{"VertexTransitive",{14,16}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{14,16}},"LCFSignature"]

GraphData[{"VertexTransitive",{14,16}},"LCFNotations"]

GraphData[{"VertexTransitive",{14,16}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{14,16}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{14,16}}],All])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"VertexTransitive",{14,16}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{14,16}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{14,16}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{14,16}},"VertexList"],GraphData[{"VertexTransitive",{14,16}},"EdgeList"]],MaxIterations->500]

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

g=LabelGraph@RotateGraph[,{5,2}]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{14,16}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{14,16}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{14,16}},"Matchstick"]

GraphData[{"VertexTransitive",{14,16}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{14,16}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{14,16}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{14,16}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{14,16}},"Polyhedral"]

GraphData[{"VertexTransitive",{14,16}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {14, 26}}

Names

GraphData[{"VertexTransitive",{14,26}},"StandardName"]

GraphData[{"VertexTransitive",{14,26}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{14,26}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{14,26}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{14,26}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{14,26}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{14,26}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{14,26}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{14,26}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"VertexTransitive",{14,26}},"Polyhedron"]

Bilateral

GraphData[{"VertexTransitive",{14,26}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{14,26}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{14,26}},"Planar"]

GraphData[{"VertexTransitive",{14,26}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{14,26}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{14,26}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{14,26}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{14,26}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,26}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,26}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{14,26}},"Circulant"]

GraphData[{"VertexTransitive",{14,26}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"VertexTransitive",{14,26}},"ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

Line graph

GraphData[{"VertexTransitive",{14,26}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{14,26}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{14,26}}&]

RootGraph[GraphData[{"VertexTransitive",{14,26}}]]

Halin

GraphData[{"VertexTransitive",{14,26}},"Halin"]

GraphData[{"VertexTransitive",{14,26}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{14,26}},"Rigid"]

GraphData[{"VertexTransitive",{14,26}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{14,26}},"Flexible"]

GraphData[{"VertexTransitive",{14,26}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{14,26}},"LCF"]

GraphData[{"VertexTransitive",{14,26}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{14,26}},"LCFSignature"]

GraphData[{"VertexTransitive",{14,26}},"LCFNotations"]

GraphData[{"VertexTransitive",{14,26}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{14,26}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{14,26}}],All])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"VertexTransitive",{14,26}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{14,26}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{14,26}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{14,26}},"VertexList"],GraphData[{"VertexTransitive",{14,26}},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{14,26}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{14,26}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{14,26}},"Matchstick"]

GraphData[{"VertexTransitive",{14,26}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{14,26}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{14,26}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{14,26}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{14,26}},"Polyhedral"]

GraphData[{"VertexTransitive",{14,26}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {14, 30}}

Names

GraphData[{"VertexTransitive",{14,30}},"StandardName"]

GraphData[{"VertexTransitive",{14,30}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{14,30}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{14,30}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{14,30}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{14,30}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{14,30}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{14,30}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{14,30}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"VertexTransitive",{14,30}},"Polyhedron"]

Bilateral

GraphData[{"VertexTransitive",{14,30}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{14,30}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{14,30}},"Planar"]

GraphData[{"VertexTransitive",{14,30}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{14,30}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{14,30}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{14,30}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{14,30}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,30}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,30}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{14,30}},"Circulant"]

GraphData[{"VertexTransitive",{14,30}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"VertexTransitive",{14,30}},"ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

Line graph

GraphData[{"VertexTransitive",{14,30}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{14,30}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{14,30}}&]

RootGraph[GraphData[{"VertexTransitive",{14,30}}]]

Halin

GraphData[{"VertexTransitive",{14,30}},"Halin"]

GraphData[{"VertexTransitive",{14,30}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{14,30}},"Rigid"]

GraphData[{"VertexTransitive",{14,30}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{14,30}},"Flexible"]

GraphData[{"VertexTransitive",{14,30}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{14,30}},"LCF"]

GraphData[{"VertexTransitive",{14,30}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{14,30}},"LCFSignature"]

GraphData[{"VertexTransitive",{14,30}},"LCFNotations"]

GraphData[{"VertexTransitive",{14,30}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{14,30}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{14,30}}],All])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"VertexTransitive",{14,30}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{14,30}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{14,30}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{14,30}},"VertexList"],GraphData[{"VertexTransitive",{14,30}},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{14,30}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{14,30}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{14,30}},"Matchstick"]

GraphData[{"VertexTransitive",{14,30}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{14,30}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{14,30}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{14,30}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{14,30}},"Polyhedral"]

GraphData[{"VertexTransitive",{14,30}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {14, 41}}

Names

GraphData[{"VertexTransitive",{14,41}},"StandardName"]

GraphData[{"VertexTransitive",{14,41}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{14,41}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{14,41}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Perspective

GraphData[{"VertexTransitive",{14,41}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"VertexTransitive",{14,41}},"Polyhedron"]

Bilateral

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

Circular

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

Planar

GraphData[{"VertexTransitive",{14,41}},"Planar"]

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

MinimalCrossing

GraphData[{"VertexTransitive",{14,41}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,41}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{14,41}},"Circulant"]

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

Complement graph

GraphData[{"VertexTransitive",{14,41}},"ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

g=;

Line graph

GraphData[{"VertexTransitive",{14,41}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{14,41}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"VertexTransitive",{14,41}}]]

Halin

GraphData[{"VertexTransitive",{14,41}},"Halin"]

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

Rigid

GraphData[{"VertexTransitive",{14,41}},"Rigid"]

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

Flexible

GraphData[{"VertexTransitive",{14,41}},"Flexible"]

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

LCF

GraphData[{"VertexTransitive",{14,41}},"LCF"]

GraphData[{"VertexTransitive",{14,41}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{14,41}},"LCFSignature"]

GraphData[{"VertexTransitive",{14,41}},"LCFNotations"]

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

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

LCF compute all

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

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"VertexTransitive",{14,41}},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"VertexTransitive",{14,41}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"VertexTransitive",{14,41}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"VertexTransitive",{14,41}},"Polyhedral"]

GraphData[{"VertexTransitive",{14,41}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {14, 48}}

Names

GraphData[{"VertexTransitive",{14,48}},"StandardName"]

GraphData[{"VertexTransitive",{14,48}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{14,48}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{14,48}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{14,48}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{14,48}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{14,48}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{14,48}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{14,48}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"VertexTransitive",{14,48}},"Polyhedron"]

Bilateral

GraphData[{"VertexTransitive",{14,48}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{14,48}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{14,48}},"Planar"]

GraphData[{"VertexTransitive",{14,48}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{14,48}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{14,48}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{14,48}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{14,48}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,48}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,48}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{14,48}},"Circulant"]

GraphData[{"VertexTransitive",{14,48}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"VertexTransitive",{14,48}},"ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

Line graph

GraphData[{"VertexTransitive",{14,48}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{14,48}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{14,48}}&]

RootGraph[GraphData[{"VertexTransitive",{14,48}}]]

Halin

GraphData[{"VertexTransitive",{14,48}},"Halin"]

GraphData[{"VertexTransitive",{14,48}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{14,48}},"Rigid"]

GraphData[{"VertexTransitive",{14,48}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{14,48}},"Flexible"]

GraphData[{"VertexTransitive",{14,48}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{14,48}},"LCF"]

GraphData[{"VertexTransitive",{14,48}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{14,48}},"LCFSignature"]

GraphData[{"VertexTransitive",{14,48}},"LCFNotations"]

GraphData[{"VertexTransitive",{14,48}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{14,48}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{14,48}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

gs=NiceLCFGraphs[{{{{-6,-5,-4,-2,2,4,6},{-6,-4,-2,2,4,5,6}},7}},2]

UnitDistance

GraphData[{"VertexTransitive",{14,48}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{14,48}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{14,48}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{14,48}},"VertexList"],GraphData[{"VertexTransitive",{14,48}},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{14,48}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{14,48}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{14,48}},"Matchstick"]

GraphData[{"VertexTransitive",{14,48}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{14,48}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{14,48}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{14,48}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{14,48}},"Polyhedral"]

GraphData[{"VertexTransitive",{14,48}},"Graph",{"3D","Polyhedron"}]

{"VertexTransitive", {14, 52}}

Names

GraphData[{"VertexTransitive",{14,52}},"StandardName"]

GraphData[{"VertexTransitive",{14,52}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{14,52}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{14,52}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{14,52}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{14,52}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{14,52}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{14,52}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{14,52}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"VertexTransitive",{14,52}},"Polyhedron"]

Bilateral

GraphData[{"VertexTransitive",{14,52}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{14,52}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{14,52}},"Planar"]

GraphData[{"VertexTransitive",{14,52}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{14,52}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{14,52}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{14,52}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{14,52}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,52}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{14,52}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{14,52}},"Circulant"]

GraphData[{"VertexTransitive",{14,52}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"VertexTransitive",{14,52}},"ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

Line graph

GraphData[{"VertexTransitive",{14,52}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{14,52}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{14,52}}&]

RootGraph[GraphData[{"VertexTransitive",{14,52}}]]

Halin

GraphData[{"VertexTransitive",{14,52}},"Halin"]

GraphData[{"VertexTransitive",{14,52}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{14,52}},"Rigid"]

GraphData[{"VertexTransitive",{14,52}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{14,52}},"Flexible"]

GraphData[{"VertexTransitive",{14,52}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{14,52}},"LCF"]

GraphData[{"VertexTransitive",{14,52}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{14,52}},"LCFSignature"]

GraphData[{"VertexTransitive",{14,52}},"LCFNotations"]

GraphData[{"VertexTransitive",{14,52}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{14,52}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{14,52}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"VertexTransitive",{14,52}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{14,52}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{14,52}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{14,52}},"VertexList"],GraphData[{"VertexTransitive",{14,52}},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{14,52}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{14,52}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{14,52}},"Matchstick"]

GraphData[{"VertexTransitive",{14,52}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{14,52}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{14,52}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{14,52}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{14,52}},"Polyhedral"]

GraphData[{"VertexTransitive",{14,52}},"Graph",{"3D","Polyhedron"}]

15

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@GraphData[{"VertexTransitive","Connected"},15]],Dividers->All]

TextGrid[Sort[{FirstCase[GraphData[#,"StandardNames"],{"VertexTransitive",n_}:>n],#}&/@Cases[GraphData[{"VertexTransitive","Connected"},15],{"VertexTransitive",_}]],Dividers->All]

{"VertexTransitive", {15, 42}}

Names

GraphData[{"VertexTransitive",{15,42}},"StandardName"]

GraphData[{"VertexTransitive",{15,42}},"StandardNames"]

Primary

GraphData[{"VertexTransitive",{15,42}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"VertexTransitive",{15,42}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"VertexTransitive",{15,42}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"VertexTransitive",{15,42}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"VertexTransitive",{15,42}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"VertexTransitive",{15,42}},"Graph","Degenerate"]

Perspective

GraphData[{"VertexTransitive",{15,42}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"VertexTransitive",{15,42}},"Polyhedron"]

Bilateral

GraphData[{"VertexTransitive",{15,42}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"VertexTransitive",{15,42}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"VertexTransitive",{15,42}},"Planar"]

GraphData[{"VertexTransitive",{15,42}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"VertexTransitive",{15,42}},{"RCN","CN"}]

GraphData[{"VertexTransitive",{15,42}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"VertexTransitive",{15,42}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"VertexTransitive",{15,42}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"VertexTransitive",{15,42}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"VertexTransitive",{15,42}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"VertexTransitive",{15,42}},"Circulant"]

GraphData[{"VertexTransitive",{15,42}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"VertexTransitive",{15,42}},"ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

gs={,,,};

Line graph

GraphData[{"VertexTransitive",{15,42}},"Line"]

LineGraphQ[GraphData[{"VertexTransitive",{15,42}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"VertexTransitive",{15,42}}&]

RootGraph[GraphData[{"VertexTransitive",{15,42}}]]

Halin

GraphData[{"VertexTransitive",{15,42}},"Halin"]

GraphData[{"VertexTransitive",{15,42}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"VertexTransitive",{15,42}},"Rigid"]

GraphData[{"VertexTransitive",{15,42}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"VertexTransitive",{15,42}},"Flexible"]

GraphData[{"VertexTransitive",{15,42}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"VertexTransitive",{15,42}},"LCF"]

GraphData[{"VertexTransitive",{15,42}},"HamiltonianCycleCount"]

GraphData[{"VertexTransitive",{15,42}},"LCFSignature"]

GraphData[{"VertexTransitive",{15,42}},"LCFNotations"]

GraphData[{"VertexTransitive",{15,42}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"VertexTransitive",{15,42}}],TimeConstraint->120]

LCF compute 10^5

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"VertexTransitive",{15,42}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"VertexTransitive",{15,42}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"VertexTransitive",{15,42}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"VertexTransitive",{15,42}}],Debug->True]//Timing

GraphData[{"VertexTransitive",{15,42}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"VertexTransitive",{15,42}},"VertexList"],GraphData[{"VertexTransitive",{15,42}},"EdgeList"]],MaxIterations->500]

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

LabelGraph@RotateGraph[,{10,13}]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{15,42}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"VertexTransitive",{15,42}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"VertexTransitive",{15,42}},"Matchstick"]

GraphData[{"VertexTransitive",{15,42}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"VertexTransitive",{15,42}},"Edges"]]

3D All

GraphData[{"VertexTransitive",{15,42}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"VertexTransitive",{15,42}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"VertexTransitive",{15,42}},"Polyhedral"]

GraphData[{"VertexTransitive",{15,42}},"Graph",{"3D","Polyhedron"}]

GraphData

GraphDataString

unknown=Position[Map[RecognizeGraph[FromAdjacencyMatrix[#]]&,Take[vt,15],{2}],{}]

Length[%]

file=OpenWrite["vt.m"]

Monitor[WriteString[file,GraphDataString[FromAdjacencyMatrix[vt[[Sequence@@(g=#)]]],
"Name"->ToString[#[[1]]]<>"-vertex transitive graph "<>ToString[#[[2]]],
"StandardName"->{"VertexTransitive",#},
"Classes"->{"VertexTranstive"},
"Information"->"Vertex-TransitiveGraph",
"Vertices"->None,
Debug->True,
TimeConstraint->60
]]&/@unknown,g];