Sextic Graph

Author

Eric W. Weisstein
October 19, 2023

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

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

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

Generate

Connected

A006822

Table[Total[Boole[SexticGraphQ/@ConnectedGraphs[n]]],{n,10}]//Timing

Table[Length@GraphData[{"Sextic","Connected"},n],{n,10}]

Length/@Table[RegularConnectedGraphs[6,n],{n,12}]//Timing

Hamiltonian

Table[Length@GraphData[{"Sextic","Hamiltonian"},n],{n,13}]

Length/@Table[Select[RegularConnectedGraphs[6,n],HamiltonianGraphQ],{n,12}]

Same as connected up to at least 12-nodes

Disconnected

A165656

A165656={0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,5,25,297,8199,377004,22014143,1493574756,114880777582,9919463450855};

Position[A165656,Except[0,_Integer]]//Flatten

Table[Length@GraphData[{"Sextic","Disconnected"},n],{n,10}]

All

A165627

Table[Total[Boole[SexticGraphQ/@Graphs[n]]],{n,10}]//Timing

Table[Length@GraphData["Sextic",n],{n,10}]

Select from GraphData

Sort[GraphData[#,{"V","#"}]&/@GraphData["Sextic"]]

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

Embeddings

<<MathWorld`Graphs`

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

7

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

{"Sextic", {7, 1}} == {"Complete", 7}

GraphData[{"Sextic",{7,1}},"StandardName"]

8

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

{"Sextic", {8, 1}} == "SixteenCellGraph"

GraphData[{"Sextic",{8,1}},"StandardName"]

9

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

{"Sextic", {9, 1}}

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{9,1}},"EdgeList"]]

Default embedding

GraphPlot[GraphData[{"Sextic",{9,1}},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Sextic",{9,1}}],"CrossingNumber"->cn]]

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Sextic",{9,1}}],"CrossingNumber"->cn,RandomSeed->n]],{n,200}],Max[OuterFace[#]]<=GraphData[{"Sextic",{9,1}},"V"]&]]//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

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

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

Halin

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

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

LCF

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

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

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

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

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Sextic",{9,1}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{9,1}}],All])[[All,2]]]//Timing

gs=LCFGraph@@@lcf//StyleGraphs

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

UnitDistance

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

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

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

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Sextic", {9, 2}} == {"KleinBottleTriangulation", {9, 1}}

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

{"Sextic", {9, 3}} == {"Circulant", {9, {1, 2, 3}}}

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

{"Sextic", {9, 4}} == {"CompleteTripartite", {3, 3, 3}}

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

10

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

{"Sextic", {10, 1}}

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,1}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,1}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Sextic",{10,1}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

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

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

Halin

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

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

LCF

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

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

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

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

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,1}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,1}}],All])[[All,2]]]//Timing

gs=LCFGraph@@@lcf//StyleGraphs

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

UnitDistance

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

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

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

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Sextic", {10, 2}}

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,2}},"EdgeList"]]

Default embedding

GraphPlot[GraphData[{"Sextic",{10,2}},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Sextic",{10,2}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

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

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

Halin

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

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

LCF

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

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

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

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

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,2}}],All][[All,All,1]]]//Timing

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

gs=LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

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

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

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

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Sextic", {10, 3}}

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,3}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Sextic",{10,3}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

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

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

Halin

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

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

LCF

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

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

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

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

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,3}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,3}}],All])[[All,2]]]//Timing

gs=LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

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

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

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

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Sextic", {10, 4}}

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,4}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Sextic",{10,4}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

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

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

Halin

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

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

LCF

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

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

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

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

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,4}}],All][[All,All,1]]]//Timing

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

LCFGraph@@@lcf//StyleGraphs

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

Length[gs]

UnitDistance

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

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

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

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

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Sextic", {10, 5}}

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Sextic",{10,5}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,5}},"Circulant"]

GraphData[{"Sextic",{10,5}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Sextic",{10,5}},"Halin"]

GraphData[{"Sextic",{10,5}},"Graph","Halin"]//StyleGraphs

LCF

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

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

GraphData[{"Sextic",{10,5}},"LCFSignature"]

GraphData[{"Sextic",{10,5}},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,5}}],All][[All,All,1]]]//Timing

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

gs=LCFGraph@@@lcf//StyleGraphs

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

UnitDistance

GraphData[{"Sextic",{10,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{10,5}}],Debug->True]//Timing

GraphData[{"Sextic",{10,5}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Sextic",{10,5}},"Matchstick"]

GraphData[{"Sextic",{10,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{10,5}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,5}},"Polyhedral"]

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

{"Sextic", {10, 6}}

GraphData[{"Sextic",{10,6}},"StandardName"]

Primary

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

All

GraphData[{"Sextic",{10,6}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,6}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,6}},"Edges"]

RegionIntersection[Line[v[[{3,7}]]],Line[v[[{4,1}]]]]//FullSimplify

RegionIntersection[Line[v[[{3,8}]]],Line[v[[{5,1}]]]]//FullSimplify

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{10,6}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{10,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{10,6}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{10,6}},"Planar"]

GraphData[{"Sextic",{10,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{10,6}},{"RCN","CN"}]

GraphData[{"Sextic",{10,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Sextic",{10,6}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,6}},"Circulant"]

GraphData[{"Sextic",{10,6}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Sextic",{10,6}},"Halin"]

GraphData[{"Sextic",{10,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Sextic",{10,6}},"LCF"]

GraphData[{"Sextic",{10,6}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,6}},"LCFSignature"]

GraphData[{"Sextic",{10,6}},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,6}}],All][[All,All,1]]]//Timing

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

LCFGraph@@@lcf//StyleGraphs

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

UnitDistance

GraphData[{"Sextic",{10,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{10,6}}],Debug->True]//Timing

GraphData[{"Sextic",{10,6}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Sextic",{10,6}},"Matchstick"]

GraphData[{"Sextic",{10,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{10,6}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,6}},"Polyhedral"]

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

{"Sextic", {10, 7}} =={"Circulant", {10, {1, 2, 4}}}

GraphData[{"Sextic",{10,7}},"StandardName"]

{"Sextic", {10, 8}} == {"Circulant", {10, {1, 2, 3}}}

GraphData[{"Sextic",{10,8}},"StandardName"]

{"Sextic", {10, 9}}

GraphData[{"Sextic",{10,9}},"StandardName"]

Primary

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

All

GraphData[{"Sextic",{10,9}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,9}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,9}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{10,9}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{10,9}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{10,9}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{10,9}},"Planar"]

GraphData[{"Sextic",{10,9}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{10,9}},{"RCN","CN"}]

GraphData[{"Sextic",{10,9}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Sextic",{10,9}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,9}},"Circulant"]

GraphData[{"Sextic",{10,9}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Sextic",{10,9}},"Halin"]

GraphData[{"Sextic",{10,9}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Sextic",{10,9}},"LCF"]

GraphData[{"Sextic",{10,9}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,9}},"LCFSignature"]

GraphData[{"Sextic",{10,9}},"LCFNotations"]

GraphData[{"Sextic",{10,9}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,9}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,9}}],All])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

(gs=DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,2}]])//Timing

Length[gs]

UnitDistance

GraphData[{"Sextic",{10,9}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{10,9}}],Debug->True]//Timing

GraphData[{"Sextic",{10,9}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Sextic",{10,9}},"Matchstick"]

GraphData[{"Sextic",{10,9}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{10,9}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,9}},"Polyhedral"]

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

{"Sextic", {10, 10}}

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,10}},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph@GraphData[{"Sextic",{10,10}},"Edges"],Pi/2]

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

GraphData[{"Sextic",{10,10}},"Planar"]

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

MinimalCrossing

GraphData[{"Sextic",{10,10}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,10}},"Circulant"]

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

Halin

GraphData[{"Sextic",{10,10}},"Halin"]

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

LCF

GraphData[{"Sextic",{10,10}},"LCF"]

GraphData[{"Sextic",{10,10}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,10}},"LCFSignature"]

GraphData[{"Sextic",{10,10}},"LCFNotations"]

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

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,10}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,10}}],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[{"Sextic",{10,10}},"UnitDistance"]

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Sextic",{10,10}},"VertexList"],GraphData[{"Sextic",{10,10}},"EdgeList"]]]

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

LabelGraph@RotateGraph[,{6,5}]

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

VertexDegree[g]

RecognizeGraph@g

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Sextic",{10,10}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Sextic",{10,10}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,10}},"Polyhedral"]

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

{"Sextic", {10, 11}}

Names

GraphData[{"Sextic",{10,11}},"StandardName"]

GraphData[{"Sextic",{10,11}},"StandardNames"]

Primary

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

All

GraphData[{"Sextic",{10,11}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,11}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,11}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{10,11}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Sextic",{10,11}},"Graph","Degenerate"]

Perspective

GraphData[{"Sextic",{10,11}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{10,11}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{10,11}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{10,11}},"Planar"]

GraphData[{"Sextic",{10,11}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{10,11}},{"RCN","CN"}]

GraphData[{"Sextic",{10,11}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Sextic",{10,11}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,11}},"Circulant"]

GraphData[{"Sextic",{10,11}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Sextic",{10,11}},"Line"]

LineGraphQ[GraphData[{"Sextic",{10,11}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Sextic",{10,11}}&]

RootGraph[GraphData[{"Sextic",{10,11}}]]

Halin

GraphData[{"Sextic",{10,11}},"Halin"]

GraphData[{"Sextic",{10,11}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Sextic",{10,11}},"Rigid"]

GraphData[{"Sextic",{10,11}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Sextic",{10,11}},"Flexible"]

GraphData[{"Sextic",{10,11}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Sextic",{10,11}},"LCF"]

GraphData[{"Sextic",{10,11}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,11}},"LCFSignature"]

GraphData[{"Sextic",{10,11}},"LCFNotations"]

GraphData[{"Sextic",{10,11}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,11}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,11}}],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[{"Sextic",{10,11}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{10,11}}],Debug->True]//Timing

GraphData[{"Sextic",{10,11}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Sextic",{10,11}},"Matchstick"]

GraphData[{"Sextic",{10,11}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{10,11}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,11}},"Polyhedral"]

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

{"Sextic", {10, 12}}

Names

GraphData[{"Sextic",{10,12}},"StandardName"]

GraphData[{"Sextic",{10,12}},"StandardNames"]

Primary

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

All

GraphData[{"Sextic",{10,12}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,12}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,12}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{10,12}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Sextic",{10,12}},"Graph","Degenerate"]

Perspective

GraphData[{"Sextic",{10,12}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{10,12}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{10,12}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{10,12}},"Planar"]

GraphData[{"Sextic",{10,12}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{10,12}},{"RCN","CN"}]

GraphData[{"Sextic",{10,12}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,12}},"Circulant"]

GraphData[{"Sextic",{10,12}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Sextic",{10,12}},"Line"]

LineGraphQ[GraphData[{"Sextic",{10,12}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Sextic",{10,12}}&]

RootGraph[GraphData[{"Sextic",{10,12}}]]

Halin

GraphData[{"Sextic",{10,12}},"Halin"]

GraphData[{"Sextic",{10,12}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Sextic",{10,12}},"Rigid"]

GraphData[{"Sextic",{10,12}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Sextic",{10,12}},"Flexible"]

GraphData[{"Sextic",{10,12}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Sextic",{10,12}},"LCF"]

GraphData[{"Sextic",{10,12}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,12}},"LCFSignature"]

GraphData[{"Sextic",{10,12}},"LCFNotations"]

GraphData[{"Sextic",{10,12}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,12}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,12}}],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[{"Sextic",{10,12}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{10,12}}],Debug->True]//Timing

GraphData[{"Sextic",{10,12}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Sextic",{10,12}},"Matchstick"]

GraphData[{"Sextic",{10,12}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{10,12}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,12}},"Polyhedral"]

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

{"Sextic", {10, 13}}

Names

GraphData[{"Sextic",{10,13}},"StandardName"]

GraphData[{"Sextic",{10,13}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,13}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,13}},"Edges"]

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

RecognizeGraph[g]

GraphPlot@Graph[GraphData[{"Sextic",{10,13}},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph[g]

gs=UnlabelGraph/@{,}

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData[{"Sextic",{10,13}},"Graph","Degenerate"]

Perspective

GraphData[{"Sextic",{10,13}},"Graph","Perspective"]//StyleGraphs

Bilateral

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

Circular

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

Planar

GraphData[{"Sextic",{10,13}},"Planar"]

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

MinimalCrossing

GraphData[{"Sextic",{10,13}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

{,,}

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,13}},"Circulant"]

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

Line graph

GraphData[{"Sextic",{10,13}},"Line"]

LineGraphQ[GraphData[{"Sextic",{10,13}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Sextic",{10,13}}&]

RootGraph[GraphData[{"Sextic",{10,13}}]]

Halin

GraphData[{"Sextic",{10,13}},"Halin"]

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

Rigid

GraphData[{"Sextic",{10,13}},"Rigid"]

GraphData[{"Sextic",{10,13}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Sextic",{10,13}},"Flexible"]

GraphData[{"Sextic",{10,13}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Sextic",{10,13}},"LCF"]

GraphData[{"Sextic",{10,13}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,13}},"LCFSignature"]

GraphData[{"Sextic",{10,13}},"LCFNotations"]

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

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

LCF compute all

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

Tally[(lcf=LCF[GraphData[{"Sextic",{10,13}}],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[{"Sextic",{10,13}},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

RotateGraph[,{7,2}]

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

RecognizeGraph@g

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Sextic",{10,13}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Sextic",{10,13}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,13}},"Polyhedral"]

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

{"Sextic", {10, 14}}

Names

GraphData[{"Sextic",{10,14}},"StandardName"]

GraphData[{"Sextic",{10,14}},"StandardNames"]

Primary

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

All

GraphData[{"Sextic",{10,14}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,14}},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph[GraphData[{"Sextic",{10,14}},"Edges"],GraphLayout->"HighDimensionalEmbedding"],Pi/2]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{10,14}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Sextic",{10,14}},"Graph","Degenerate"]

Perspective

GraphData[{"Sextic",{10,14}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{10,14}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{10,14}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{10,14}},"Planar"]

GraphData[{"Sextic",{10,14}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{10,14}},{"RCN","CN"}]

GraphData[{"Sextic",{10,14}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Sextic",{10,14}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@

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

VertexDegree[g]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,14}},"Circulant"]

GraphData[{"Sextic",{10,14}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Sextic",{10,14}},"Line"]

LineGraphQ[GraphData[{"Sextic",{10,14}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Sextic",{10,14}}&]

RootGraph[GraphData[{"Sextic",{10,14}}]]

Halin

GraphData[{"Sextic",{10,14}},"Halin"]

GraphData[{"Sextic",{10,14}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Sextic",{10,14}},"Rigid"]

GraphData[{"Sextic",{10,14}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Sextic",{10,14}},"Flexible"]

GraphData[{"Sextic",{10,14}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Sextic",{10,14}},"LCF"]

GraphData[{"Sextic",{10,14}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,14}},"LCFSignature"]

GraphData[{"Sextic",{10,14}},"LCFNotations"]

GraphData[{"Sextic",{10,14}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,14}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,14}}],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[{"Sextic",{10,14}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{10,14}}],Debug->True]//Timing

GraphData[{"Sextic",{10,14}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

g=RotateGraph[,{3,6}]

gs={,};

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Sextic",{10,14}},"Matchstick"]

GraphData[{"Sextic",{10,14}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{10,14}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,14}},"Polyhedral"]

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

{"Sextic", {10, 15}}

Names

GraphData[{"Sextic",{10,15}},"StandardName"]

GraphData[{"Sextic",{10,15}},"StandardNames"]

Primary

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

All

GraphData[{"Sextic",{10,15}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,15}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,15}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{10,15}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Sextic",{10,15}},"Graph","Degenerate"]

Perspective

GraphData[{"Sextic",{10,15}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{10,15}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{10,15}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{10,15}},"Planar"]

GraphData[{"Sextic",{10,15}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{10,15}},{"RCN","CN"}]

GraphData[{"Sextic",{10,15}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Sextic",{10,15}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot[]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,15}},"Circulant"]

GraphData[{"Sextic",{10,15}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Sextic",{10,15}},"Line"]

LineGraphQ[GraphData[{"Sextic",{10,15}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Sextic",{10,15}}&]

RootGraph[GraphData[{"Sextic",{10,15}}]]

Halin

GraphData[{"Sextic",{10,15}},"Halin"]

GraphData[{"Sextic",{10,15}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Sextic",{10,15}},"Rigid"]

GraphData[{"Sextic",{10,15}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Sextic",{10,15}},"Flexible"]

GraphData[{"Sextic",{10,15}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Sextic",{10,15}},"LCF"]

GraphData[{"Sextic",{10,15}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,15}},"LCFSignature"]

GraphData[{"Sextic",{10,15}},"LCFNotations"]

GraphData[{"Sextic",{10,15}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,15}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,15}}],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[{"Sextic",{10,15}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{10,15}}],Debug->True]//Timing

GraphData[{"Sextic",{10,15}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Sextic",{10,15}},"Matchstick"]

GraphData[{"Sextic",{10,15}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{10,15}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,15}},"Polyhedral"]

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

{"Sextic", {10, 16}}

Names

GraphData[{"Sextic",{10,16}},"StandardName"]

GraphData[{"Sextic",{10,16}},"StandardNames"]

Primary

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

All

GraphData[{"Sextic",{10,16}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,16}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,16}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{10,16}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Sextic",{10,16}},"Graph","Degenerate"]

Perspective

GraphData[{"Sextic",{10,16}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{10,16}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{10,16}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{10,16}},"Planar"]

GraphData[{"Sextic",{10,16}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{10,16}},{"RCN","CN"}]

GraphData[{"Sextic",{10,16}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Sextic",{10,16}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,16}},"Circulant"]

GraphData[{"Sextic",{10,16}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Sextic",{10,16}},"Line"]

LineGraphQ[GraphData[{"Sextic",{10,16}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Sextic",{10,16}}&]

RootGraph[GraphData[{"Sextic",{10,16}}]]

Halin

GraphData[{"Sextic",{10,16}},"Halin"]

GraphData[{"Sextic",{10,16}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Sextic",{10,16}},"Rigid"]

GraphData[{"Sextic",{10,16}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Sextic",{10,16}},"Flexible"]

GraphData[{"Sextic",{10,16}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Sextic",{10,16}},"LCF"]

GraphData[{"Sextic",{10,16}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,16}},"LCFSignature"]

GraphData[{"Sextic",{10,16}},"LCFNotations"]

GraphData[{"Sextic",{10,16}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,16}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,16}}],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[{"Sextic",{10,16}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{10,16}}],Debug->True]//Timing

GraphData[{"Sextic",{10,16}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

GraphPlot@RotateGraph[,{3,5}]

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

VertexDegree[g]

RecognizeGraph@g

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Sextic",{10,16}},"Matchstick"]

GraphData[{"Sextic",{10,16}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{10,16}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,16}},"Polyhedral"]

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

{"Sextic", {10, 17}}

Names

GraphData[{"Sextic",{10,17}},"StandardName"]

GraphData[{"Sextic",{10,17}},"StandardNames"]

Primary

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

All

GraphData[{"Sextic",{10,17}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,17}},"EdgeList"]]

Default embedding

GraphPlot@Graph[GraphData[{"Sextic",{10,17}},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{10,17}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Sextic",{10,17}},"Graph","Degenerate"]

Perspective

GraphData[{"Sextic",{10,17}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{10,17}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{10,17}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{10,17}},"Planar"]

GraphData[{"Sextic",{10,17}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{10,17}},{"RCN","CN"}]

GraphData[{"Sextic",{10,17}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Sextic",{10,17}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,17}},"Circulant"]

GraphData[{"Sextic",{10,17}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Sextic",{10,17}},"Line"]

LineGraphQ[GraphData[{"Sextic",{10,17}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Sextic",{10,17}}&]

RootGraph[GraphData[{"Sextic",{10,17}}]]

Halin

GraphData[{"Sextic",{10,17}},"Halin"]

GraphData[{"Sextic",{10,17}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Sextic",{10,17}},"Rigid"]

GraphData[{"Sextic",{10,17}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Sextic",{10,17}},"Flexible"]

GraphData[{"Sextic",{10,17}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Sextic",{10,17}},"LCF"]

GraphData[{"Sextic",{10,17}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,17}},"LCFSignature"]

GraphData[{"Sextic",{10,17}},"LCFNotations"]

GraphData[{"Sextic",{10,17}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,17}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,17}}],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[{"Sextic",{10,17}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{10,17}}],Debug->True]//Timing

GraphData[{"Sextic",{10,17}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

g=RotateGraph[,{9,6}]

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

VertexDegree[g]

RecognizeGraph@g

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Sextic",{10,17}},"Matchstick"]

GraphData[{"Sextic",{10,17}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{10,17}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,17}},"Polyhedral"]

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

{"Sextic", {10, 18}} == {"Cone", {6, 4}}

GraphData[{"Sextic",{10,18}},"StandardName"]

{"Sextic", {10, 19}} == {"Triangular", 5}

GraphData[{"Sextic",{10,19}},"StandardName"]

{"Sextic", {10, 20}} == {"TriangularHoneycombQueen", 4}

GraphData[{"Sextic",{10,20}},"StandardName"]

{"Sextic", {10, 21}}

Names

GraphData[{"Sextic",{10,21}},"StandardName"]

GraphData[{"Sextic",{10,21}},"StandardNames"]

Primary

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

All

GraphData[{"Sextic",{10,21}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{10,21}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{10,21}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{10,21}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Sextic",{10,21}},"Graph","Degenerate"]

Perspective

GraphData[{"Sextic",{10,21}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{10,21}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{10,21}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{10,21}},"Planar"]

GraphData[{"Sextic",{10,21}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{10,21}},{"RCN","CN"}]

GraphData[{"Sextic",{10,21}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Sextic",{10,21}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{10,21}},"Circulant"]

GraphData[{"Sextic",{10,21}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Sextic",{10,21}},"Line"]

LineGraphQ[GraphData[{"Sextic",{10,21}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Sextic",{10,21}}&]

RootGraph[GraphData[{"Sextic",{10,21}}]]

Halin

GraphData[{"Sextic",{10,21}},"Halin"]

GraphData[{"Sextic",{10,21}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Sextic",{10,21}},"Rigid"]

GraphData[{"Sextic",{10,21}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Sextic",{10,21}},"Flexible"]

GraphData[{"Sextic",{10,21}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Sextic",{10,21}},"LCF"]

GraphData[{"Sextic",{10,21}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{10,21}},"LCFSignature"]

GraphData[{"Sextic",{10,21}},"LCFNotations"]

GraphData[{"Sextic",{10,21}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{10,21}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{10,21}}],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[{"Sextic",{10,21}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{10,21}}],Debug->True]//Timing

GraphData[{"Sextic",{10,21}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

g=RotateGraph[,{9,8}]

Matchstick

GraphData[{"Sextic",{10,21}},"Matchstick"]

GraphData[{"Sextic",{10,21}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{10,21}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Sextic",{10,21}},"Polyhedral"]

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

11

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

12

TextGrid[Sort[{Cases[GraphData[#,"StandardNames"],{"Sextic",n_}:>n][[-1]],#}&/@GraphData["Sextic",12]],Dividers->All]

{"Sextic", {12, 776}} == {"Rook", {2, 6}}

GraphData[{"Sextic",{12,776}},"StandardName"]

{"Sextic", {12, 831}} == {"KleinBottleTriangulation", {12, 1}}

GraphData[{"Sextic",{12,831}},"StandardName"]

{"Sextic", {12, 1101}} == {"Circulant", {12, {1, 2,3 }}}

GraphData[{"Sextic",{12,1101}},"StandardName"]

{"Sextic", {12, 5939}} == {"VertexTransitive", {12, 48}}

GraphData[{"Sextic",{12,5939}},"StandardName"]

{"Sextic", {12, 5958}} == {"VertexTransitive", {12, 45}}

GraphData[{"Sextic",{12,5958}},"StandardName"]

{"Sextic", {12, 6001}} == {"VertexTransitive", {12, 47}}

GraphData[{"Sextic",{12,6001}},"StandardName"]

{"Sextic", {12, 6380}}

Names

GraphData[{"Sextic",{12,6380}},"StandardName"]

GraphData[{"Sextic",{12,6380}},"StandardNames"]

Primary

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

All

GraphData[{"Sextic",{12,6380}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{12,6380}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{12,6380}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{12,6380}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Sextic",{12,6380}},"Graph","Degenerate"]

Perspective

GraphData[{"Sextic",{12,6380}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{12,6380}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{12,6380}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{12,6380}},"Planar"]

GraphData[{"Sextic",{12,6380}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{12,6380}},{"RCN","CN"}]

GraphData[{"Sextic",{12,6380}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{12,6380}},"Circulant"]

GraphData[{"Sextic",{12,6380}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Sextic",{12,6380}},"Line"]

LineGraphQ[GraphData[{"Sextic",{12,6380}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Sextic",{12,6380}}&]

RootGraph[GraphData[{"Sextic",{12,6380}}]]

Halin

GraphData[{"Sextic",{12,6380}},"Halin"]

GraphData[{"Sextic",{12,6380}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Sextic",{12,6380}},"Rigid"]

GraphData[{"Sextic",{12,6380}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Sextic",{12,6380}},"Flexible"]

GraphData[{"Sextic",{12,6380}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Sextic",{12,6380}},"LCF"]

GraphData[{"Sextic",{12,6380}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{12,6380}},"LCFSignature"]

GraphData[{"Sextic",{12,6380}},"LCFNotations"]

GraphData[{"Sextic",{12,6380}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{12,6380}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{12,6380}}],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[{"Sextic",{12,6380}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{12,6380}}],Debug->True]//Timing

GraphData[{"Sextic",{12,6380}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

GraphPlot/@{RotateGraph[,{1,5}],RotateGraph[,{3,1}]}

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Sextic",{12,6380}},"Matchstick"]

GraphData[{"Sextic",{12,6380}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{12,6380}},"Edges"]]

3D All

GraphData[{"Sextic",{12,6380}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Sextic",{12,6380}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Sextic",{12,6380}},"Polyhedral"]

GraphData[{"Sextic",{12,6380}},"Graph",{"3D","Polyhedron"}]

{"Sextic", {12, 7220}} == "OctahedralLineGraph"

GraphData[{"Sextic",{12,7220}},"StandardName"]

{"Sextic", {12, 7460}} == {"Circulant", {12, {1, 4, 5}}}

GraphData[{"Sextic",{12,7460}},"StandardName"]

{"Sextic", {12, 7461}} == {"KleinBottleTriangulation", {12, 3}}

GraphData[{"Sextic",{12,7461}},"StandardName"]

{"Sextic", {12, 7463}} == {"KleinBottleTriangulation", {12, 2}}

GraphData[{"Sextic",{12,7463}},"StandardName"]

{"Sextic", {12, 7465}} == {"Circulant", {12, {1, 3, 4}}}

GraphData[{"Sextic",{12,7465}},"StandardName"]

{"Sextic", {12, 7589}} == {"Circulant", {12, {1, 2, 4}}}

GraphData[{"Sextic",{12,7589}},"StandardName"]

{"Sextic", {12, 7593}}

Names

GraphData[{"Sextic",{12,7593}},"StandardName"]

GraphData[{"Sextic",{12,7593}},"StandardNames"]

Primary

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

All

GraphData[{"Sextic",{12,7593}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Sextic",{12,7593}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Sextic",{12,7593}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Sextic",{12,7593}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Sextic",{12,7593}},"Graph","Degenerate"]

Perspective

GraphData[{"Sextic",{12,7593}},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{"Sextic",{12,7593}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Sextic",{12,7593}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Sextic",{12,7593}},"Planar"]

GraphData[{"Sextic",{12,7593}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Sextic",{12,7593}},{"RCN","CN"}]

GraphData[{"Sextic",{12,7593}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Sextic",{12,7593}},"Circulant"]

GraphData[{"Sextic",{12,7593}},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Sextic",{12,7593}},"Line"]

LineGraphQ[GraphData[{"Sextic",{12,7593}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Sextic",{12,7593}}&]

RootGraph[GraphData[{"Sextic",{12,7593}}]]

Halin

GraphData[{"Sextic",{12,7593}},"Halin"]

GraphData[{"Sextic",{12,7593}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Sextic",{12,7593}},"Rigid"]

GraphData[{"Sextic",{12,7593}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Sextic",{12,7593}},"Flexible"]

GraphData[{"Sextic",{12,7593}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Sextic",{12,7593}},"LCF"]

GraphData[{"Sextic",{12,7593}},"HamiltonianCycleCount"]

GraphData[{"Sextic",{12,7593}},"LCFSignature"]

GraphData[{"Sextic",{12,7593}},"LCFNotations"]

GraphData[{"Sextic",{12,7593}},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Sextic",{12,7593}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Sextic",{12,7593}}],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|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,2}]]}])//Timing

Length[gs]

UnitDistance

GraphData[{"Sextic",{12,7593}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Sextic",{12,7593}}],Debug->True]//Timing

GraphData[{"Sextic",{12,7593}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

g=RotateGraph[,{1,4}]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Sextic",{12,7593}},"Matchstick"]

GraphData[{"Sextic",{12,7593}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Sextic",{12,7593}},"Edges"]]

3D All

GraphData[{"Sextic",{12,7593}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Sextic",{12,7593}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Sextic",{12,7593}},"Polyhedral"]

GraphData[{"Sextic",{12,7593}},"Graph",{"3D","Polyhedron"}]

{"Sextic", {12, 7846}} == {"Circulant", {12, {2, 3, 4}}}

GraphData[{"Sextic",{12,7846}},"StandardName"]

{"Sextic", {12, 7847}} == {"VertexTransitive", {12, 40}}

GraphData[{"Sextic",{12,7847}},"StandardName"]

{"Sextic", {12, 7848}} == {"RookComplement", {3, 4}}

GraphData[{"Sextic",{12,7848}},"StandardName"]

{"Sextic", {12, 7849}} == {"CompleteBipartite", {6, 6}}

GraphData[{"Sextic",{12,7849}},"StandardName"]

13

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

14

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

Plots

nice=SortBy[DeleteCases[sextic,{"Sextic"|"Circulant",_}],GraphData[#,"V"]&]

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

nicer=Select[nice,GraphData[#,"Embeddings"]=!={}&]

GraphicsGrid[Partition[GraphPlot[Graph[#],Method->None,BaseStyle->{FontSlant->"Italic",FontSize->9},PlotLabel->GraphData[#,"Name"]]&/@nicer,4,4,{1,1},{}],ImageSize->600,Spacings->{-20,20}]

GraphData

GraphDataString

Do[MapIndexed[
Print[If[(r=RecognizeGraph[#])=!={}&&!MatchQ[r,{_Integer,_Integer}],{r,{"Sextic",{n,#2[[1]]}}},GraphDataString[#1,
"StandardName"->{"Sextic",{n,#2[[1]]}},
"Name"->ToString[n]<>"-sextic graph "<>ToString[#2[[1]]],
"Vertices"->None,
"Information"->"SexticGraph",
TimeConstraint->120
]]]&,RegularGraph[6,n]],{n,7,11}];