Hamilton-Laceable Graph

Author

Eric W. Weisstein
May 10, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Hamilton-LaceableGraph.nb.

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

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

Counts

Length/@Table[ConnectedGraphs[n],{n,9}]//AbsoluteTiming

Length/@Table[GraphData["HamiltonLaceable",n],{n,7}]

Table[Count[Graphs[n],_?HamiltonLaceableGraphQ],{n,8}]//Timing

8

Table[Count[ParallelMap[HamiltonLaceableGraphQ,Graphs[n]],True],{n,8}]//AbsoluteTiming

Table[Count[ParallelMap[HamiltonLaceableGraphQ[#,"Preprocess"->False]&,Graphs[n]],True],{n,8}]//AbsoluteTiming

9

Table[Count[ParallelMap[HamiltonLaceableGraphQ,Graphs[n]],True],{n,9}]//AbsoluteTiming

Table[Count[ParallelMap[HamiltonLaceableGraphQ[#,"Preprocess"->False]&,Graphs[n]],True],{n,9}]//AbsoluteTiming

10

Table[Count[ParallelMap[HamiltonLaceableGraphQ,Graphs[n]],True],{n,10}]//AbsoluteTiming

Table[Count[ParallelMap[HamiltonLaceableGraphQ[#,"Preprocess"->False]&,Graphs[n]],True],{n,10}]//AbsoluteTiming

"FindPath"

Table[Count[ConnectedGraphs[n],_?(HamiltonLaceableGraphQ[#,Method->"FindPath"]&)],{n,7}]//AbsoluteTiming

Table[Count[ConnectedGraphs[n],_?(HamiltonLaceableGraphQ[#,Method->"FindPath"]&)],{n,8}]//AbsoluteTiming

Table[Count[ConnectedGraphs[n],_?(HamiltonLaceableGraphQ[#,Method->"FindPath"]&)],{n,9}]//AbsoluteTiming

"FindHamiltonianPath"

Table[Count[ConnectedGraphs[n],_?(HamiltonLaceableGraphQ[#,Method->"FindHamiltonianPath"]&)],{n,7}]//AbsoluteTiming

Table[Count[ConnectedGraphs[n],_?(HamiltonLaceableGraphQ[#,Method->"FindHamiltonianPath"]&)],{n,8}]//AbsoluteTiming

Table[Count[ConnectedGraphs[n],_?(HamiltonLaceableGraphQ[#,Method->"FindHamiltonianPath"]&)],{n,9}]//AbsoluteTiming

"MyFindHamiltonianPath"

Table[Count[ConnectedGraphs[n],_?(HamiltonLaceableGraphQ[#,Method->"FindPath"]&)],{n,7}]//AbsoluteTiming

Table[Count[ConnectedGraphs[n],_?(HamiltonLaceableGraphQ[#,Method->"FindPath"]&)],{n,8}]//AbsoluteTiming

Table[Count[ConnectedGraphs[n],_?(HamiltonLaceableGraphQ[#,Method->"FindPath"]&)],{n,9}]//AbsoluteTiming

H and B but not HL

nonhl=Select[GraphData[{"Hamiltonian","Bipartite"}],Mod[GraphData[#,"V"],2]==0&&GraphData[#,"HamiltonLaceable"]===False&]

Column[Table[Select[GraphData[{"Hamiltonian","Bipartite"},n],GraphData[#,"HamiltonLaceable"]===False&],{n,2,10,2}],Dividers->All]

Table[Count[Map[BipartiteGraphQ[#]&&HamiltonianGraphQ[#]&&!HamiltonLaceableGraphQ[#,"Hamiltonian"->True]&,Graphs[n]],True],{n,2,10,2}]//AbsoluteTiming

Domino Graph

m=GraphData[{"Ladder",3},"MinimumVertexColoring"]

c1=Position[m,1]//Flatten

c2=Position[m,2]//Flatten

uvs=Union[Sort/@Flatten[Outer[List,c1,c2],1]]

hps=Union[GraphData[{"Ladder",3},"UndirectedHamiltonianPaths"][[All,{1,-1}]]]

Complement[uvs,hps]

Figure

hl=DeleteCases[Table[GraphData["HamiltonLaceable",n],{n,8}],{}]

GraphicsGrid[
Flatten[Partition[#,6,6,{1,1},{}]&/@Map[Show[GraphData[#,"Image"],PlotLabel->TextCell[Style[StringReplace[GraphData[#,"Name"],"\[Hyphen]"->"-"],Italic,FontFamily->"Times"],PageWidth->600/6,TextAlignment->Center]]&,hl,{2}],1],Dividers->All,Alignment->Top,ImageSize->600
]

Embeddings

<<MathWorld`Graphs`

GraphData["HamiltonLaceable*"]

TextGrid[Sort[DeleteCases[{FirstCase[GraphData[#,"StandardNames"],{"HamiltonLaceable",_}],#}&/@DeleteCases[GraphData["HamiltonLaceable"],{"HamiltonLaceable",_}],{_Missing,_}]],Dividers->All]

Select[GraphData["HamiltonLaceable",;;8],FreeQ[GraphData[#,"StandardNames"],"HamiltonLaceable"]&]

{"HamiltonLaceable", {1, 1}} == "SingletonGraph"

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

{"HamiltonLaceable", {2, 1}} == {"Path", 2}

GraphData[{"HamiltonLaceable",{2,1}},"StandardName"]

{"HamiltonLaceable", {4, 1}} == "SquareGraph"

GraphData[{"HamiltonLaceable",{4,1}},"StandardName"]

{"HamiltonLaceable", {6, 1}}

GraphData[{"HamiltonLaceable",{6,1}},"StandardName"]

Primary

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

All

GraphData[{"HamiltonLaceable",{6,1}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"HamiltonLaceable",{6,1}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"HamiltonLaceable",{6,1}},"Edges"]

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

RecognizeGraph[g]

GraphPlot@RotateGraph[Graph[GraphData[{"HamiltonLaceable",{6,1}},"Edges"],GraphLayout->"HighDimensionalEmbedding"],-Pi/2]

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

RecognizeGraph@g

GraphPlot@RotateGraph[Graph[GraphData[{"HamiltonLaceable",{6,1}},"Edges"],GraphLayout->"CircularEmbedding"],-Pi/2]

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

RecognizeGraph@g

gs={,};

Degenerate

GraphData[{"HamiltonLaceable",{6,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"HamiltonLaceable",{6,1}},"Graph","Degenerate"]

Bilateral

GraphData[{"HamiltonLaceable",{6,1}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"HamiltonLaceable",{6,1}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"HamiltonLaceable",{6,1}}],All][[All,All,1]]]

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

gs=bilat

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

quad

Planar

GraphData[{"HamiltonLaceable",{6,1}},"Planar"]

GraphData[{"HamiltonLaceable",{6,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"HamiltonLaceable",{6,1}},{"RCN","CN"}]

GraphData[{"HamiltonLaceable",{6,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

GraphPlot@MinimalCrossingGraph[GraphData[{"HamiltonLaceable",{6,1}}]]

GraphPlot@RotateGraph[GraphicsToGraph@,-Pi/2]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"HamiltonLaceable",{6,1}},"Circulant"]

GraphData[{"HamiltonLaceable",{6,1}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"HamiltonLaceable",{6,1}},"Halin"]

GraphData[{"HamiltonLaceable",{6,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"HamiltonLaceable",{6,1}},"Rigid"]

GraphData[{"HamiltonLaceable",{6,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"HamiltonLaceable",{6,1}},"Flexible"]

GraphData[{"HamiltonLaceable",{6,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"HamiltonLaceable",{6,1}},"LCF"]

GraphData[{"HamiltonLaceable",{6,1}},"HamiltonianCycleCount"]

GraphData[{"HamiltonLaceable",{6,1}},"LCFSignature"]

GraphData[{"HamiltonLaceable",{6,1}},"LCFNotations"]

GraphData[{"HamiltonLaceable",{6,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"HamiltonLaceable",{6,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"HamiltonLaceable",{6,1}}],Debug->True]//Timing

GraphData[{"HamiltonLaceable",{6,1}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"HamiltonLaceable",{6,1}},"Matchstick"]

GraphData[{"HamiltonLaceable",{6,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"HamiltonLaceable",{6,1}},"Edges"]]

3D All

GraphData[{"HamiltonLaceable",{6,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"HamiltonLaceable",{6,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"HamiltonLaceable",{6,1}},"Polyhedral"]

GraphData[{"HamiltonLaceable",{6,1}},"Graph",{"3D","Polyhedron"}]

{"HamiltonLaceable", {6, 2}} == "UtilityGraph"

GraphData[{"HamiltonLaceable",{6,2}},"StandardName"]

{"HamiltonLaceable", {8, 1}}

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

Primary

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

All

GraphData[{"HamiltonLaceable",{8,1}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"HamiltonLaceable",{8,1}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"HamiltonLaceable",{8,1}},"Edges"]

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

RecognizeGraph[g]

gs={,};

GraphData[gn={"HamiltonLaceable",{8,1}},"Graph","Labeled"]

GraphData[gn,"Edges"]

gnew=System`Graph[Range[8],UndirectedEdge@@@Join[Partition[{1,3,5,8,6,4,2,7},2,1,1],{{1,4},{4,5},{2,3},{3,6}}],VertexCoordinates->Join[Flatten[Table[{i,j},{i,-1,1},{j,-1/2,1/2}],1],Table[i{1+1/2,0},{i,-1,1,2}]],VertexLabels->"Name"]

RecognizeGraph[gnew]

gnew2=PlanarGraph[Range[8],GraphData[gn,"Edges"],VertexLabels->"Name"]

gnew3=System`Graph[Range[8],EdgeList[gnew2],VertexCoordinates->ReplacePart[e=GraphEmbedding[gnew2],{3->{0,.5},4->{0,-.5},7->{.5,0},6->{-.5,0}}],VertexLabels->"Name"]

RecognizeGraph[gnew3]

Degenerate

GraphData[{"HamiltonLaceable",{8,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"HamiltonLaceable",{8,1}},"Graph","Degenerate"]

Bilateral

GraphData[{"HamiltonLaceable",{8,1}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"HamiltonLaceable",{8,1}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"HamiltonLaceable",{8,1}}],All][[All,All,1]]]

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

gs=bilat

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

quad

Planar

GraphData[{"HamiltonLaceable",{8,1}},"Planar"]

GraphData[{"HamiltonLaceable",{8,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"HamiltonLaceable",{8,1}},{"RCN","CN"}]

GraphData[{"HamiltonLaceable",{8,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

GraphPlot@MinimalCrossingGraph[GraphData[{"HamiltonLaceable",{8,1}}]]

GraphPlot@RotateGraph[GraphicsToGraph@,-Pi/2]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"HamiltonLaceable",{8,1}},"Circulant"]

GraphData[{"HamiltonLaceable",{8,1}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"HamiltonLaceable",{8,1}},"Halin"]

GraphData[{"HamiltonLaceable",{8,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"HamiltonLaceable",{8,1}},"Rigid"]

GraphData[{"HamiltonLaceable",{8,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"HamiltonLaceable",{8,1}},"Flexible"]

GraphData[{"HamiltonLaceable",{8,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"HamiltonLaceable",{8,1}},"LCF"]

GraphData[{"HamiltonLaceable",{8,1}},"HamiltonianCycleCount"]

GraphData[{"HamiltonLaceable",{8,1}},"LCFSignature"]

GraphData[{"HamiltonLaceable",{8,1}},"LCFNotations"]

GraphData[{"HamiltonLaceable",{8,1}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"HamiltonLaceable",{8,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"HamiltonLaceable",{8,1}}],Debug->True]//Timing

GraphData[{"HamiltonLaceable",{8,1}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"HamiltonLaceable",{8,1}},"Matchstick"]

GraphData[{"HamiltonLaceable",{8,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"HamiltonLaceable",{8,1}},"Edges"]]

3D All

GraphData[{"HamiltonLaceable",{8,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"HamiltonLaceable",{8,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"HamiltonLaceable",{8,1}},"Polyhedral"]

GraphData[{"HamiltonLaceable",{8,1}},"Graph",{"3D","Polyhedron"}]

{"HamiltonLaceable", {8, 2}}

GraphData[{"HamiltonLaceable",{8,2}},"StandardName"]

Primary

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

All

GraphData[{"HamiltonLaceable",{8,2}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"HamiltonLaceable",{8,2}},"EdgeList"]]

Default embedding

GraphPlot[GraphData[{"HamiltonLaceable",{8,2}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

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

RecognizeGraph[g]

gs={,};

Degenerate

GraphData[{"HamiltonLaceable",{8,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"HamiltonLaceable",{8,2}},"Graph","Degenerate"]

Bilateral

GraphData[{"HamiltonLaceable",{8,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"HamiltonLaceable",{8,2}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"HamiltonLaceable",{8,2}}],All][[All,All,1]]]

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

gs=bilat

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

Planar

GraphData[{"HamiltonLaceable",{8,2}},"Planar"]

GraphData[{"HamiltonLaceable",{8,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"HamiltonLaceable",{8,2}},{"RCN","CN"}]

GraphData[{"HamiltonLaceable",{8,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"HamiltonLaceable",{8,2}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"HamiltonLaceable",{8,2}},"Circulant"]

GraphData[{"HamiltonLaceable",{8,2}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"HamiltonLaceable",{8,2}},"Halin"]

GraphData[{"HamiltonLaceable",{8,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"HamiltonLaceable",{8,2}},"Rigid"]

GraphData[{"HamiltonLaceable",{8,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"HamiltonLaceable",{8,2}},"Flexible"]

GraphData[{"HamiltonLaceable",{8,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"HamiltonLaceable",{8,2}},"LCF"]

GraphData[{"HamiltonLaceable",{8,2}},"HamiltonianCycleCount"]

GraphData[{"HamiltonLaceable",{8,2}},"LCFSignature"]

GraphData[{"HamiltonLaceable",{8,2}},"LCFNotations"]

GraphData[{"HamiltonLaceable",{8,2}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"HamiltonLaceable",{8,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"HamiltonLaceable",{8,2}}],Debug->True]//Timing

GraphData[{"HamiltonLaceable",{8,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"HamiltonLaceable",{8,2}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"HamiltonLaceable",{8,2}}],TimeConstraint->300,"Results"->All]//Timing}

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

gs={,,,};

Matchstick

GraphData[{"HamiltonLaceable",{8,2}},"Matchstick"]

GraphData[{"HamiltonLaceable",{8,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"HamiltonLaceable",{8,2}},"Edges"]]

3D All

GraphData[{"HamiltonLaceable",{8,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"HamiltonLaceable",{8,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"HamiltonLaceable",{8,2}},"Polyhedral"]

GraphData[{"HamiltonLaceable",{8,2}},"Graph",{"3D","Polyhedron"}]

{"HamiltonLaceable", {8, 3}}

GraphData[{"HamiltonLaceable",{8,3}},"StandardName"]

Primary

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

All

GraphData[{"HamiltonLaceable",{8,3}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"HamiltonLaceable",{8,3}},"EdgeList"]]

Default embedding

GraphPlot[GraphData[{"HamiltonLaceable",{8,3}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

RotateGraph[GraphicsToGraph@,Pi/2]

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

RecognizeGraph[g]

gs={,,};

Degenerate

GraphData[{"HamiltonLaceable",{8,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"HamiltonLaceable",{8,3}},"Graph","Degenerate"]

Bilateral

GraphData[{"HamiltonLaceable",{8,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"HamiltonLaceable",{8,3}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"HamiltonLaceable",{8,3}}],All][[All,All,1]]]

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

gs=bilat

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

Planar

GraphData[{"HamiltonLaceable",{8,3}},"Planar"]

GraphData[{"HamiltonLaceable",{8,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"HamiltonLaceable",{8,3}},{"RCN","CN"}]

GraphData[{"HamiltonLaceable",{8,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"HamiltonLaceable",{8,3}}],TimeConstraint->1])//AbsoluteTiming

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

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

Table[MinimalCrossingGraph[GraphData[{"HamiltonLaceable",{8,3}}],"CrossingNumber"->cn,RandomSeed->i],{i,200}]//Union

GraphPlot@RotateGraph[,-2Pi/6]

Mean[v[[{2,6}]]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"HamiltonLaceable",{8,3}},"Circulant"]

GraphData[{"HamiltonLaceable",{8,3}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"HamiltonLaceable",{8,3}},"Halin"]

GraphData[{"HamiltonLaceable",{8,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"HamiltonLaceable",{8,3}},"Rigid"]

GraphData[{"HamiltonLaceable",{8,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"HamiltonLaceable",{8,3}},"Flexible"]

GraphData[{"HamiltonLaceable",{8,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"HamiltonLaceable",{8,3}},"LCF"]

GraphData[{"HamiltonLaceable",{8,3}},"HamiltonianCycleCount"]

GraphData[{"HamiltonLaceable",{8,3}},"LCFSignature"]

GraphData[{"HamiltonLaceable",{8,3}},"LCFNotations"]

GraphData[{"HamiltonLaceable",{8,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"HamiltonLaceable",{8,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"HamiltonLaceable",{8,3}}],Debug->True]//Timing

GraphData[{"HamiltonLaceable",{8,3}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"HamiltonLaceable",{8,3}},"Matchstick"]

GraphData[{"HamiltonLaceable",{8,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"HamiltonLaceable",{8,3}},"Edges"]]

3D All

GraphData[{"HamiltonLaceable",{8,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"HamiltonLaceable",{8,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"HamiltonLaceable",{8,3}},"Polyhedral"]

GraphData[{"HamiltonLaceable",{8,3}},"Graph",{"3D","Polyhedron"}]

{"HamiltonLaceable", {8, 4}}

GraphData[{"HamiltonLaceable",{8,4}},"StandardName"]

Primary

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

All

GraphData[{"HamiltonLaceable",{8,4}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"HamiltonLaceable",{8,4}},"EdgeList"]]

Default embedding

GraphData[gn={"HamiltonLaceable",{8,4}},"Graph","Labeled"]

GraphPlot@Annotate[,VertexLabels->None]

GraphPlot@RotateGraph[GraphicsToGraph@,Pi]

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

RecognizeGraph[g]

GraphPlot[GraphData[{"HamiltonLaceable",{8,4}},"Edges"],GraphLayout->"SpringEmbedding"]

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

RecognizeGraph@g

gnew=PlanarGraph[Range[8],GraphData[gn,"Edges"],VertexLabels->"Name"]

Graph[Range[8],EdgeList[gnew],VertexCoordinates->6{{-1,1},{1,-1},{-(1/2),-(1/2)},{-(5/6),-(1/2)},{1,1},{-(2/3),0},{0,0},{-1,-1}},VertexLabels->"Name"]

gs={,,}

RotateGraph[Graph[GraphData[{"HamiltonLaceable",{8,4}},"Edges"],GraphLayout->"CircularEmbedding"],-3/2Pi/4]

Degenerate

GraphData[{"HamiltonLaceable",{8,4}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"HamiltonLaceable",{8,4}},"Graph","Degenerate"]

Bilateral

GraphData[{"HamiltonLaceable",{8,4}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"HamiltonLaceable",{8,4}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"HamiltonLaceable",{8,4}}],All][[All,All,1]]]

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

gs=bilat

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

Planar

GraphData[{"HamiltonLaceable",{8,4}},"Planar"]

GraphData[{"HamiltonLaceable",{8,4}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"HamiltonLaceable",{8,4}},{"RCN","CN"}]

GraphData[{"HamiltonLaceable",{8,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"HamiltonLaceable",{8,4}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"HamiltonLaceable",{8,4}},"Circulant"]

GraphData[{"HamiltonLaceable",{8,4}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"HamiltonLaceable",{8,4}},"Halin"]

GraphData[{"HamiltonLaceable",{8,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"HamiltonLaceable",{8,4}},"Rigid"]

GraphData[{"HamiltonLaceable",{8,4}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"HamiltonLaceable",{8,4}},"Flexible"]

GraphData[{"HamiltonLaceable",{8,4}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"HamiltonLaceable",{8,4}},"LCF"]

GraphData[{"HamiltonLaceable",{8,4}},"HamiltonianCycleCount"]

GraphData[{"HamiltonLaceable",{8,4}},"LCFSignature"]

GraphData[{"HamiltonLaceable",{8,4}},"LCFNotations"]

GraphData[{"HamiltonLaceable",{8,4}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"HamiltonLaceable",{8,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"HamiltonLaceable",{8,4}}],Debug->True]//Timing

GraphData[{"HamiltonLaceable",{8,4}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"HamiltonLaceable",{8,4}},"Matchstick"]

GraphData[{"HamiltonLaceable",{8,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"HamiltonLaceable",{8,4}},"Edges"]]

3D All

GraphData[{"HamiltonLaceable",{8,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"HamiltonLaceable",{8,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"HamiltonLaceable",{8,4}},"Polyhedral"]

GraphData[{"HamiltonLaceable",{8,4}},"Graph",{"3D","Polyhedron"}]

{"HamiltonLaceable", {8, 5}}

GraphData[{"HamiltonLaceable",{8,5}},"StandardName"]

Primary

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

All

GraphData[{"HamiltonLaceable",{8,5}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"HamiltonLaceable",{8,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"HamiltonLaceable",{8,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"HamiltonLaceable",{8,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"HamiltonLaceable",{8,5}},"Graph","Degenerate"]

Bilateral

GraphData[{"HamiltonLaceable",{8,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"HamiltonLaceable",{8,5}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"HamiltonLaceable",{8,5}}],All][[All,All,1]]]

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

gs=bilat

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

quad

Planar

GraphData[{"HamiltonLaceable",{8,5}},"Planar"]

GraphData[{"HamiltonLaceable",{8,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"HamiltonLaceable",{8,5}},{"RCN","CN"}]

GraphData[{"HamiltonLaceable",{8,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

Table[MinimalCrossingGraph[GraphData[{"HamiltonLaceable",{8,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@RotateGraph[,Pi/2]

v[[3,2]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"HamiltonLaceable",{8,5}},"Circulant"]

GraphData[{"HamiltonLaceable",{8,5}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"HamiltonLaceable",{8,5}},"Halin"]

GraphData[{"HamiltonLaceable",{8,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"HamiltonLaceable",{8,5}},"Rigid"]

GraphData[{"HamiltonLaceable",{8,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"HamiltonLaceable",{8,5}},"Flexible"]

GraphData[{"HamiltonLaceable",{8,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"HamiltonLaceable",{8,5}},"LCF"]

GraphData[{"HamiltonLaceable",{8,5}},"HamiltonianCycleCount"]

GraphData[{"HamiltonLaceable",{8,5}},"LCFSignature"]

GraphData[{"HamiltonLaceable",{8,5}},"LCFNotations"]

GraphData[{"HamiltonLaceable",{8,5}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"HamiltonLaceable",{8,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"HamiltonLaceable",{8,5}}],Debug->True]//Timing

GraphData[{"HamiltonLaceable",{8,5}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"HamiltonLaceable",{8,5}},"VertexList"],GraphData[{"HamiltonLaceable",{8,5}},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"HamiltonLaceable",{8,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"HamiltonLaceable",{8,5}},"Matchstick"]

GraphData[{"HamiltonLaceable",{8,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"HamiltonLaceable",{8,5}},"Edges"]]

3D All

GraphData[{"HamiltonLaceable",{8,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"HamiltonLaceable",{8,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"HamiltonLaceable",{8,5}},"Polyhedral"]

GraphData[{"HamiltonLaceable",{8,5}},"Graph",{"3D","Polyhedron"}]

{"HamiltonLaceable", {8, 6}} == "CubicalGraph"

GraphData[{"HamiltonLaceable",{8,6}},"StandardName"]

{"HamiltonLaceable", {8, 7}}

GraphData[{"HamiltonLaceable",{8,7}},"StandardName"]

Primary

GraphData[{"HamiltonLaceable",{8,7}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"HamiltonLaceable",{8,7}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"HamiltonLaceable",{8,7}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"HamiltonLaceable",{8,7}},"Edges"]

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

RecognizeGraph[g]

gs={,,};

GraphPlot[GraphData[{"HamiltonLaceable",{8,7}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

Degenerate

GraphData[{"HamiltonLaceable",{8,7}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"HamiltonLaceable",{8,7}},"Graph","Degenerate"]

Bilateral

GraphData[{"HamiltonLaceable",{8,7}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"HamiltonLaceable",{8,7}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"HamiltonLaceable",{8,7}}],All][[All,All,1]]]

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

gs=bilat

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

quad

Planar

GraphData[{"HamiltonLaceable",{8,7}},"Planar"]

GraphData[{"HamiltonLaceable",{8,7}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"HamiltonLaceable",{8,7}},{"RCN","CN"}]

GraphData[{"HamiltonLaceable",{8,7}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"HamiltonLaceable",{8,7}}],TimeConstraint->1])//AbsoluteTiming

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

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

Table[MinimalCrossingGraph[GraphData[{"HamiltonLaceable",{8,7}}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"HamiltonLaceable",{8,7}},"Circulant"]

GraphData[{"HamiltonLaceable",{8,7}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"HamiltonLaceable",{8,7}},"Halin"]

GraphData[{"HamiltonLaceable",{8,7}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"HamiltonLaceable",{8,7}},"Rigid"]

GraphData[{"HamiltonLaceable",{8,7}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"HamiltonLaceable",{8,7}},"Flexible"]

GraphData[{"HamiltonLaceable",{8,7}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"HamiltonLaceable",{8,7}},"LCF"]

GraphData[{"HamiltonLaceable",{8,7}},"HamiltonianCycleCount"]

GraphData[{"HamiltonLaceable",{8,7}},"LCFSignature"]

GraphData[{"HamiltonLaceable",{8,7}},"LCFNotations"]

GraphData[{"HamiltonLaceable",{8,7}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"HamiltonLaceable",{8,7}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"HamiltonLaceable",{8,7}}],Debug->True]//Timing

GraphData[{"HamiltonLaceable",{8,7}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"HamiltonLaceable",{8,7}},"VertexList"],GraphData[{"HamiltonLaceable",{8,7}},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"HamiltonLaceable",{8,7}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"HamiltonLaceable",{8,7}},"Matchstick"]

GraphData[{"HamiltonLaceable",{8,7}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"HamiltonLaceable",{8,7}},"Edges"]]

3D All

GraphData[{"HamiltonLaceable",{8,7}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"HamiltonLaceable",{8,7}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"HamiltonLaceable",{8,7}},"Polyhedral"]

GraphData[{"HamiltonLaceable",{8,7}},"Graph",{"3D","Polyhedron"}]

{"HamiltonLaceable", {8, 8}}

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

Primary

GraphData[{"HamiltonLaceable",{8,8}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"HamiltonLaceable",{8,8}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"HamiltonLaceable",{8,8}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"HamiltonLaceable",{8,8}},"Edges"]

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

RecognizeGraph[g]

gs={,,,};

Degenerate

GraphData[{"HamiltonLaceable",{8,8}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"HamiltonLaceable",{8,8}},"Graph","Degenerate"]

Bilateral

GraphData[{"HamiltonLaceable",{8,8}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"HamiltonLaceable",{8,8}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"HamiltonLaceable",{8,8}}],All][[All,All,1]]]

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

gs=bilat

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

quad

gs={,,};

Planar

GraphData[{"HamiltonLaceable",{8,8}},"Planar"]

GraphData[{"HamiltonLaceable",{8,8}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"HamiltonLaceable",{8,8}},{"RCN","CN"}]

GraphData[{"HamiltonLaceable",{8,8}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

Table[MinimalCrossingGraph[GraphData[{"HamiltonLaceable",{8,8}}],"CrossingNumber"->cn,RandomSeed->i],{i,100}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"HamiltonLaceable",{8,8}},"Circulant"]

GraphData[{"HamiltonLaceable",{8,8}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"HamiltonLaceable",{8,8}},"Halin"]

GraphData[{"HamiltonLaceable",{8,8}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"HamiltonLaceable",{8,8}},"Rigid"]

GraphData[{"HamiltonLaceable",{8,8}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"HamiltonLaceable",{8,8}},"Flexible"]

GraphData[{"HamiltonLaceable",{8,8}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"HamiltonLaceable",{8,8}},"LCF"]

GraphData[{"HamiltonLaceable",{8,8}},"HamiltonianCycleCount"]

GraphData[{"HamiltonLaceable",{8,8}},"LCFSignature"]

GraphData[{"HamiltonLaceable",{8,8}},"LCFNotations"]

GraphData[{"HamiltonLaceable",{8,8}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"HamiltonLaceable",{8,8}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"HamiltonLaceable",{8,8}}],Debug->True]//Timing

GraphData[{"HamiltonLaceable",{8,8}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"HamiltonLaceable",{8,8}},"VertexList"],GraphData[{"HamiltonLaceable",{8,8}},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"HamiltonLaceable",{8,8}},"Matchstick"]

GraphData[{"HamiltonLaceable",{8,8}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"HamiltonLaceable",{8,8}},"Edges"]]

3D All

GraphData[{"HamiltonLaceable",{8,8}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"HamiltonLaceable",{8,8}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"HamiltonLaceable",{8,8}},"Polyhedral"]

GraphData[{"HamiltonLaceable",{8,8}},"Graph",{"3D","Polyhedron"}]

{"HamiltonLaceable", {8, 9}}

GraphData[{"HamiltonLaceable",{8,9}},"StandardName"]

Primary

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

All

GraphData[{"HamiltonLaceable",{8,9}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"HamiltonLaceable",{8,9}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"HamiltonLaceable",{8,9}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"HamiltonLaceable",{8,9}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"HamiltonLaceable",{8,9}},"Graph","Degenerate"]

Bilateral

GraphData[{"HamiltonLaceable",{8,9}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"HamiltonLaceable",{8,9}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"HamiltonLaceable",{8,9}}],All][[All,All,1]]]

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

Planar

GraphData[{"HamiltonLaceable",{8,9}},"Planar"]

GraphData[{"HamiltonLaceable",{8,9}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"HamiltonLaceable",{8,9}},{"RCN","CN"}]

GraphData[{"HamiltonLaceable",{8,9}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

Table[MinimalCrossingGraph[GraphData[{"HamiltonLaceable",{8,9}}],"CrossingNumber"->cn,RandomSeed->i],{i,100}]//Union

GraphPlot@RotateGraph[,-Pi/2]

v[[4,2]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"HamiltonLaceable",{8,9}},"Circulant"]

GraphData[{"HamiltonLaceable",{8,9}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"HamiltonLaceable",{8,9}},"Halin"]

GraphData[{"HamiltonLaceable",{8,9}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"HamiltonLaceable",{8,9}},"Rigid"]

GraphData[{"HamiltonLaceable",{8,9}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"HamiltonLaceable",{8,9}},"Flexible"]

GraphData[{"HamiltonLaceable",{8,9}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"HamiltonLaceable",{8,9}},"LCF"]

GraphData[{"HamiltonLaceable",{8,9}},"HamiltonianCycleCount"]

GraphData[{"HamiltonLaceable",{8,9}},"LCFSignature"]

GraphData[{"HamiltonLaceable",{8,9}},"LCFNotations"]

GraphData[{"HamiltonLaceable",{8,9}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"HamiltonLaceable",{8,9}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"HamiltonLaceable",{8,9}}],Debug->True]//Timing

GraphData[{"HamiltonLaceable",{8,9}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"HamiltonLaceable",{8,9}},"Matchstick"]

GraphData[{"HamiltonLaceable",{8,9}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"HamiltonLaceable",{8,9}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"HamiltonLaceable",{8,9}},"Polyhedral"]

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

{"HamiltonLaceable", {8, 10}}

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"HamiltonLaceable",{8,10}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"HamiltonLaceable",{8,10}},"Edges"]

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

RecognizeGraph@g

GraphPlot@RotateGraph[GraphicsToGraph@,Pi/2]

RotateGraph[GraphicsToGraph@,Pi]

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

RecognizeGraph[g]

gs={,};

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData[{"HamiltonLaceable",{8,10}},"Graph","Degenerate"]

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"HamiltonLaceable",{8,10}}],All][[All,All,1]]]

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

gs=bilat

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

quad

Planar

GraphData[{"HamiltonLaceable",{8,10}},"Planar"]

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

MinimalCrossing

GraphData[{"HamiltonLaceable",{8,10}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

Table[MinimalCrossingGraph[GraphData[{"HamiltonLaceable",{8,10}}],"CrossingNumber"->cn,RandomSeed->i],{i,200}]//Union

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"HamiltonLaceable",{8,10}},"Circulant"]

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

Halin

GraphData[{"HamiltonLaceable",{8,10}},"Halin"]

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

Rigid

GraphData[{"HamiltonLaceable",{8,10}},"Rigid"]

GraphData[{"HamiltonLaceable",{8,10}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"HamiltonLaceable",{8,10}},"Flexible"]

GraphData[{"HamiltonLaceable",{8,10}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"HamiltonLaceable",{8,10}},"LCF"]

GraphData[{"HamiltonLaceable",{8,10}},"HamiltonianCycleCount"]

GraphData[{"HamiltonLaceable",{8,10}},"LCFSignature"]

GraphData[{"HamiltonLaceable",{8,10}},"LCFNotations"]

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

UnitDistance

GraphData[{"HamiltonLaceable",{8,10}},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"HamiltonLaceable",{8,10}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"HamiltonLaceable",{8,10}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"HamiltonLaceable",{8,10}},"Polyhedral"]

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

{"HamiltonLaceable", {8, 11}} == "K4,4-e"

GraphData[{"HamiltonLaceable",{8,11}},"StandardName"]

{"HamiltonLaceable", {8, 12}} == {"CompleteBipartite", {4, 4}}

GraphData[{"HamiltonLaceable",{8,12}},"StandardName"]

Parametrized families

Alkane

seq=Table[GraphData[{"Alkane",n},"HamiltonLaceable"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"HamiltonLaceable"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"HamiltonLaceable"],{n,10}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"HamiltonLaceable"],{n,15}]

Antiprism

Entity["Graph",{"Antiprism",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Antiprism",n},"HamiltonLaceable"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"HamiltonLaceable"],{n,5}]

Barbell

seq=Table[GraphData[{"Barbell",n},"HamiltonLaceable"],{n,3,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"HamiltonLaceable"],{n,10}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"HamiltonLaceable"],{n,10}]

Book

seq=Table[GraphData[{"Book",n},"HamiltonLaceable"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"HamiltonLaceable"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"HamiltonLaceable"],{n,10}]

Centipede

seq=Table[GraphData[{"Centipede",n},"HamiltonLaceable"],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"HamiltonLaceable"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Complete",n},"HamiltonLaceable"],{n,30}]

Table[Piecewise[{{True,n==1||n==2}},False],{n,30}]==seq

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["HamiltonLaceable"]

Piecewise autoevaluates away:

Piecewise[{{m==n,True}},False]//FullForm

DeleteCases[{#,GraphData[#,"HamiltonLaceable"]}&/@GraphData["CompleteBipartite"],{_,False}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["HamiltonLaceable"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"HamiltonLaceable"],{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["HamiltonLaceable"]

DeleteCases[{#,GraphData[#,"HamiltonLaceable"]}&/@GraphData["CompleteTripartite"],{_,False}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["HamiltonLaceable"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"HamiltonLaceable"],{n,10}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"HamiltonLaceable"],{n,2,10}]

Crown

seq=Table[GraphData[{"Crown",n},"HamiltonLaceable"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"HamiltonLaceable"],{n,3,8}]

Table[Piecewise[{{False,Mod[n,2]==1},{True,Mod[n,2]==0}}],{n,3,8}]==seq

Cycle

Entity["Graph",{"Cycle",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Cycle",n},"HamiltonLaceable"],{n,3,30}]

Table[Piecewise[{{True,n==4}},False],{n,3,30}]==seq

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"HamiltonLaceable"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"HamiltonLaceable"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"HamiltonLaceable"],{n,3,20}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"HamiltonLaceable"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Empty",n},"HamiltonLaceable"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"HamiltonLaceable"],{n,15}]

Flower

seq=Table[GraphData[{"Flower",n},"HamiltonLaceable"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"HamiltonLaceable"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"HamiltonLaceable"],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"HamiltonLaceable"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"HamiltonLaceable"],{n,3,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["HamiltonLaceable"]

Assuming $m\leq n$, the \eref{grid graph} $G_{m,n}$ is Hamilton-laceable \eref{iff} $(m,n)\in\{(1,1),(1,2),(2,2)\}$ or one of $m,n$ is even and $m\geq 4$.

data=DeleteCases[Select[Flatten[Table[{
GraphData[{"Grid",{m,n}},"#"],
GraphData[{"Grid",{m,n}},"HamiltonLaceable"],Piecewise[{{True,Mod[m n,2]==0&&Min[m,n]≥4},{True,m==n==1||m==n==2||m n==2}},False]
},{n,20},{m,20}]//Quiet,1],FreeQ[GraphData]],{_,x_,x_}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["HamiltonLaceable"]

seq=Table[GraphData[{"Grid",{n,n}},"HamiltonLaceable"],{n,20}]

Table[Piecewise[{{True,n==1||Mod[n,2]==0}},False],{n,20}]

Grid k×m×n

A \erfe{grid graph} in three or more dimensions is hamilton-laceable \eref{iff} it has at least one even index (Simmons 1978).

Entity["Graph",{"Grid",{k,m,n}}]["HamiltonLaceable"]

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"HamiltonLaceable"],
Piecewise[{{True,Min[k,m,n]>1&&Mod[k m n,2]==0},{True,k m n==1||k m n==2},{True,k m n==4&&Max[k,m,n]==2},{True,Min[k,m,n]==1&&Mod[k m n,2]==0&&k m n/Max[k,m,n]≥4}},False]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Tally[GraphData[{"Grid",{2,3,4}},"DistanceMatrix"]//Normal//Flatten]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["HamiltonLaceable"]

seq=Table[GraphData[{"Grid",{n,n,n}},"HamiltonLaceable"],{n,10}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"HamiltonLaceable"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"HamiltonLaceable"],{n,5}]

Helm

seq=Table[GraphData[{"Helm",n},"HamiltonLaceable"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Hypercube",n},"HamiltonLaceable"],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Keller",n},"HamiltonLaceable"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"HamiltonLaceable"],{n,20}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["HamiltonLaceable"]

Piecewise[{{True,m>=6&&n>=6&&Mod[m n,2]==0}},False]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["HamiltonLaceable"]

seq=Table[GraphData[{"Knight",{n,n}},"HamiltonLaceable"],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Ladder",n},"HamiltonLaceable"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"HamiltonLaceable"],{n,20}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"HamiltonLaceable"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"MoebiusLadder",n},"HamiltonLaceable"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Mycielski",n},"HamiltonLaceable"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Odd",n},"HamiltonLaceable"],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"HamiltonLaceable"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Path",n},"HamiltonLaceable"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"HamiltonLaceable"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Prism",n},"HamiltonLaceable"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"HamiltonLaceable"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"HamiltonLaceable"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"HamiltonLaceable"],{n,10}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"HamiltonLaceable"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"HamiltonLaceable"],{n,5}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"HamiltonLaceable"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"HamiltonLaceable"],{n,5}]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"HamiltonLaceable"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"HamiltonLaceable"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Star",n},"HamiltonLaceable"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"HamiltonLaceable"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"HamiltonLaceable"],{n,3,20}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"HamiltonLaceable"],{n,3,10}]

Transposition

Entity["Graph",{"Transposition",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Transposition",n},"HamiltonLaceable"],{n,6}]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Trapezohedron",n},"HamiltonLaceable"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"HamiltonLaceable"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"HamiltonLaceable"],{n,0,10}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"HamiltonLaceable"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"HamiltonLaceable"],{n,9}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"HamiltonLaceable"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"HamiltonLaceable"],{n,10}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"HamiltonLaceable"],{n,10}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"HamiltonLaceable"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"HamiltonLaceable"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["HamiltonLaceable"]

seq=Table[GraphData[{"Wheel",n},"HamiltonLaceable"],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"HamiltonLaceable"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"HamiltonLaceable"],{n,2,10}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"HamiltonLaceable"],{n,20}]

Theorems

Generalized Petersen

Pensaert (2002) conjectured that for n>3k with k>2, the generalized Petersen graph GP(n, k) is Hamilton-laceable if  is even and  is odd, and Hamilton-connected otherwise.

gps={"GeneralizedPetersen"/.GraphData[#,"NotationRules"],#}&/@GraphData["GeneralizedPetersen"];

Conjectured to be HL

hl=Select[gps,With[{n=#[[1,1]],k=#[[1,2]]},n>3k&&k>2&&Mod[n,2]==0&&Mod[k,2]==1]&]

GraphData[#,"HamiltonLaceable"]&/@hl[[All,2]]

Conjectured to be HC

hc=Select[gps,With[{n=#[[1,1]],k=#[[1,2]]},n>3k&&k>2&&!(Mod[n,2]==0&&Mod[k,2]==1)]&]

GraphData[#,"HamiltonLaceable"]&/@hc[[All,2]]

Grid

Assuming $m\leq n$, the \eref{grid graph} $G_{m,n}$ is Hamilton-laceable \eref{iff} $(m,n)\in\{(1,1),(1,2),(2,2)\}$ or one of $m,n$ is even and $m\geq 4$. A \erfe{grid graph} in three or more dimensions is hamilton-laceable \eref{iff} it has at least one even index (Simmons 1978).

grid1=Select[("Grid"/.GraphData[#,"NotationRules"])&/@GraphData["Grid"],Length[#]==1&]

(GraphData[{"Grid",#},"HamiltonLaceable"]===MatchQ[#,{1|2}])&/@grid1

grid2=Select[("Grid"/.GraphData[#,"NotationRules"])&/@GraphData["Grid"],Length[#]==2&]

(GraphData[{"Grid",#},"HamiltonLaceable"]===(#==={2,2}||(#[[1]]≥4&&Count[Mod[#,2],0]>0))&)/@grid2

grid3=Select[("Grid"/.GraphData[#,"NotationRules"])&/@GraphData["Grid"],Length[#]>2&]

(GraphData[{"Grid",#},"HamiltonLaceable"]===Count[Mod[#,2],0]>0&)/@grid3

Hypercube

Complement@@GraphData/@{"Hypercube","HamiltonLaceable"}

Compute

HP Missing

(l=Select[GraphData[{"Bipartite","Traceable"}],Head[GraphData[#,"|HP|"]]===Missing&])//Timing

New

(l=Monitor[Select[GraphData[{"Bipartite","Traceable"}],Head[GraphData[g=#,"HamiltonLaceable"]]===Missing&&Head[GraphData[g,"|HP|"]]=!=Missing&],g])//Timing

Timing[bad=Monitor[Select[l,!ListQ[GetGraphData[g=#,"HP"]]&],g]]

Print[{#,HamiltonLaceableGraphQ[#]//AbsoluteTiming}]&/@Complement[l,Append[bad,"SingletonGraph"]];

Print[{#,HamiltonLaceableGraphQ[#]//AbsoluteTiming}]&/@i;

DetourMatrix

Listed as HamiltonLaceable but isn't

Correct but slow:

Monitor[Select[GraphData["HamiltonLaceable",2;;100],With[{n=GraphData[g=#,"V"],c=FindIndependentVertexSet[GraphData[#]][[1]],d=GetGraphData[#,"DetourMatrix"]},
Head[d]=!=Missing&&Union[Extract[d,Flatten[Outer[List,c,Complement[Range[n],c]],1]]]=!={n-1}]&],g]

Correct and fast:

Monitor[Select[GraphData["HamiltonLaceable",2;;],With[{n=GraphData[g=#,"V"],c=Position[GraphData[#,"MinimumVertexColoring"],2]//Flatten,d=GetGraphData[#,"DetourMatrix"]},
Head[d]=!=Missing&&Union[Extract[d,Flatten[Outer[List,c,Complement[Range[n],c]],1]]]=!={n-1}]&],g]//Timing

Monitor[Select[GraphData["HamiltonLaceable",2;;],With[{n=GraphData[g=#,"V"],c=Position[GraphData[#,"MinimumVertexColoring"],1]//Flatten,d=GetGraphData[#,"DetourMatrix"]},
Head[d]=!=Missing&&Union[Extract[d,Flatten[Outer[List,c,Complement[Range[n],c]],1]]]=!={n-1}]&],g]//Timing

Not listed as HamiltonLaceable but is

Complement[GraphData[{"Hamiltonian","Bipartite"}],GraphData["HamiltonLaceable"]]

Monitor[Select[
Complement[GraphData[{"Hamiltonian","Bipartite"}],GraphData["HamiltonLaceable"]],
With[{n=GraphData[g=#,"V"],c=Position[GraphData[#,"MinimumVertexColoring"],1]//Flatten,d=GetGraphData[#,"DetourMatrix"]},
Head[d]=!=Missing&&Union[Extract[d,Flatten[Outer[List,c,Complement[Range[n],c]],1]]]==={n-1}]&],g]//Timing

Profiling

{"Cage",{5,6}}

GraphData[{"Cage",{5,6}},"V"]

GraphData[{"Cage",{5,6}},"HamiltonLaceable"]

GetGraphData[{"Cage",{5,6}},"DetourMatrix"]//MatrixForm

HamiltonLaceableGraphQ[GraphData[{"Cage",{5,6}}],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonLaceableGraphQ[GraphData[{"Cage",{5,6}}],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonLaceableGraphQ[GraphData[{"Cage",{5,6}}],Method->"FindPath"]//AbsoluteTiming

"Foster040A"

GraphData["Foster040A","V"]

GraphData["Foster040A","HamiltonLaceable"]

GetGraphData["Foster040A","DetourMatrix"]//MatrixForm

HamiltonLaceableGraphQ[GraphData["Foster040A"],Method->"FindHamiltonianPath"]//AbsoluteTiming

HamiltonLaceableGraphQ[GraphData["Foster040A"],Method->"MyFindHamiltonianPath"]//AbsoluteTiming

HamiltonLaceableGraphQ[GraphData["Foster040A"],Method->"FindPath"]//AbsoluteTiming

Check

?HamiltonLaceableGraphQ

FindHamiltonianPath

Select[GraphData["Connected",;;6],HamiltonLaceableGraphQ[GraphData[#],Method->"FindHamiltonianPath"]=!=GraphData[#,"HamiltonLaceable"]&]//Timing

Select[GraphData["Connected",;;7],HamiltonLaceableGraphQ[GraphData[#],Method->"FindHamiltonianPath"]=!=GraphData[#,"HamiltonLaceable"]&]//Timing

FindPath

Select[GraphData["Connected",;;6],HamiltonLaceableGraphQ[GraphData[#],Method->"FindPath"]=!=GraphData[#,"HamiltonLaceable"]&]//Timing

Select[GraphData["Connected",;;7],HamiltonLaceableGraphQ[GraphData[#],Method->"FindPath"]=!=GraphData[#,"HamiltonLaceable"]&]//Timing

MyFindHamiltonianPath

Select[GraphData["Connected",;;6],HamiltonLaceableGraphQ[GraphData[#],Method->"MyFindHamiltonianPath"]=!=GraphData[#,"HamiltonLaceable"]&]//Timing

Select[GraphData["Connected",;;7],HamiltonLaceableGraphQ[GraphData[#],Method->"MyFindHamiltonianPath"]=!=GraphData[#,"HamiltonLaceable"]&]//Timing

GraphData

8-node

file=OpenWrite["hl8.m"]

i=0;
WriteString[file,GraphDataString[Graphs[8][[#]],
"Name"->"8\[Hyphen]Hamilton\[Hyphen]laceable graph "<>ToString[++i],
"StandardName"->{"HamiltonLaceable",{8,i}},
"AlternateNames"->{"8\[Hyphen]graph "<>ToString[#]},
"AlternateStandardNames"->{{8,#}},
Debug->True,
TimeConstraint->60,
MemoryConstraint->1*^9
]]&/@{3631,4498,4504,4680,5215,5358,5369,5438,5503,5547,5593,5618}

Close[file]