Cubic Planar Hypohamiltonian Graph

Author

Eric W. Weisstein
April 22, 2024

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

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

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

Table

TextGrid[CubicPlanarHypohamiltonianGraphs=Sort[GraphData[#,{"V","Girth","#"}]&/@GraphData[{"Cubic","Planar","Hypohamiltonian"}]],Dividers->All]

GraphicsGrid[Partition[Show[StyleGraphs[GraphData[#],VertexSize->{"Scaled",.015}],PlotLabel->Style[TextCell[GraphData[#,"Name"],PageWidth->190,TextAlignment->Center],Directive[Black,FontFamily->"Times",Italic,16]]]&/@CubicPlanarHypohamiltonianGraphs[[All,-1]],UpTo[4]],ImageSize->800,Dividers->All]

Embeddings

<<MathWorld`Graphs`

70

{"CubicPlanarHypohamiltonian", {70, 1-6}}

Construction

http://users.cecs.anu.edu.au/~bdm/data/planegraphs.html

http://users.cecs.anu.edu.au/~bdm/data/planegraphs.html

http://users.cecs.anu.edu.au/~bdm/data/cubhypo70.pc is some kind of planar code format, but not the usual ImportPlanarCode one.  Seems to be some extra headers...

data=Import["http://users.cecs.anu.edu.au/~bdm/data/cubhypo70.pc","Byte"];

Length[data]

70 7 4

Take[data,30]

Length/@(split=SequenceSplit[data,{s:Except[0,_Integer]..,0}:>{s}])

adj=Partition[Take[#,-3]&/@split,70];

Length/@adj

CubicPlanarHypohamiltonianGraphs70=FromAdjacencyLists/@adj

CubicGraphQ/@CubicPlanarHypohamiltonianGraphs70

PlanarGraphQ/@CubicPlanarHypohamiltonianGraphs70

HypohamiltonianGraphQ/@CubicPlanarHypohamiltonianGraphs70

RecognizeGraph/@CubicPlanarHypohamiltonianGraphs70

{"CubicPlanarHypohamiltonian", {70, 1}}

Names

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"StandardName"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"StandardNames"]

Construction

img=Import["/Users/eww/Downloads/arXiv-2403.18384v1/img/fig_1cph70.pdf"][[1]]

g=ScaleGraph@ImageToGraph[img]

Through[{VertexCount,EdgeCount,PlanarGraphQ,CubicGraphQ,HypohamiltonianGraphQ}[g]]

v=With[{n=50},Round[n GraphEmbedding[g]]/n]

TsaiGraph70=IndexGraph@Annotate[g,VertexCoordinates->v]

TsaiGraph70=;

Construction attempt #2

img=;

img2=EdgeDetect@Blur[ColorNegate@img,5.5]

circ=FindImageShapes[img2,"Circle"]

img2=Binarize@EdgeDetect@ColorNegate@img

lines=FindImageShapes[img2,"LineSegment"]

Length[lines]

HighlightImage[img2,lines]

Symmetry

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"StandardNames"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"AutomorphismCount"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"AutomorphismGroup"]

FiniteGroupData[4]

FiniteGroupData[{"AbelianGroup",{2,2}},"AlternateStandardNames"]

Primary

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

All

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Degenerate"]

Configuration

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Configuration"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"]

PolyhedronGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"],{1,0,1,-Pi/2}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Hamiltonian"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"HamiltonianCycleCount"]

Planar

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Planar"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Planar"]//StyleGraphs

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"CubicPlanarHypohamiltonian",{70,1}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"CubicPlanarHypohamiltonian",{70,1}}],"OuterFace"->#]&/@faces

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

RecognizeGraph/@gs

Tutte embedding construction 11

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

Tutte embedding construction 8

GraphPlot[RotateGraph[,-2Pi/8],VertexSize->1]

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

RecognizeGraph[g]

Tutte embedding construction 7

GraphPlot[RotateGraph[],VertexSize->1]

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

RecognizeGraph[g]

Tutte embedding construction 4

GraphPlot[RotateGraph[,Pi/4],VertexSize->1]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},{"RCN","CN"}]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{70,1}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{70,1}}],TimeConstraint->5 3600])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Circulant"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"CubicPlanarHypohamiltonian",{70,1}}]])//Timing

Complement graph

compl=GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Line"]

LineGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,1}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,1}}]]

Halin

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Halin"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Rigid"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Flexible"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"LCF"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"HamiltonianCycleCount"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"LCFSignature"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"LCFNotations"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,1}}],Debug->True]//Timing

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

g=;

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

gs={,};

Matchstick

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Matchstick"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Edges"]]

3D All

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedral"]

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron"]}]

3D Canonical

GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"CubicPlanarHypohamiltonian",{70,1}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"CubicPlanarHypohamiltonian",{70,1}}],1]}]

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

can0=Polyhedron[];

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

SimplePolyhedronQ[can]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

{"CubicPlanarHypohamiltonian", {70, 2}} == "ArayaWienerGraph70"

Names

GraphData[{"CubicPlanarHypohamiltonian",{70,2}},"StandardName"]

GraphData[{"CubicPlanarHypohamiltonian",{70,2}},"StandardNames"]

{"CubicPlanarHypohamiltonian", {70, 3}}

Names

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"StandardName"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"StandardNames"]

Primary

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

All

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Degenerate"]

Configuration

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Configuration"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"]

PolyhedronGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"],{1,0,1,-Pi/2}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Hamiltonian"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"HamiltonianCycleCount"]

Planar

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Planar"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Planar"]//StyleGraphs

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}],"OuterFace"->#]&/@faces

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

RecognizeGraph/@gs

g=

Tutte embedding construction

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},{"RCN","CN"}]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Circulant"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}]])//Timing

Complement graph

compl=GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"ComplementGraph","Name"]

Line graph

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Line"]

LineGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}]]

Halin

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Halin"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Rigid"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Flexible"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"LCF"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"HamiltonianCycleCount"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"LCFSignature"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"LCFNotations"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}],Debug->True]//Timing

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicPlanarHypohamiltonian",{70,3}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicPlanarHypohamiltonian",{70,3}}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Matchstick"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Edges"]]

3D All

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedral"]

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Polyhedron"]}]

3D Canonical

GraphData[{"CubicPlanarHypohamiltonian",{70,3}},"Graph",{"3D","Canonical"}]

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

3D Canonical construction

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

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

{"CubicPlanarHypohamiltonian", {70, 4}}

Names

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"StandardName"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"StandardNames"]

Primary

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

All

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Degenerate"]

Configuration

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Configuration"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"]

PolyhedronGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"],{1,0,1,-Pi/2}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Hamiltonian"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"HamiltonianCycleCount"]

Planar

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Planar"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Planar"]//StyleGraphs

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"CubicPlanarHypohamiltonian",{70,4}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"CubicPlanarHypohamiltonian",{70,4}}],"OuterFace"->#]&/@faces

g=;

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

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},{"RCN","CN"}]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Circulant"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"CubicPlanarHypohamiltonian",{70,4}}]])//Timing

Complement graph

compl=GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"ComplementGraph","Name"]

Line graph

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Line"]

LineGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,4}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,4}}]]

Halin

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Halin"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Rigid"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Flexible"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"LCF"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"HamiltonianCycleCount"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"LCFSignature"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"LCFNotations"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,4}}],Debug->True]//Timing

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicPlanarHypohamiltonian",{70,4}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicPlanarHypohamiltonian",{70,4}}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Matchstick"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Edges"]]

3D All

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedral"]

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron"]}]

3D Canonical

GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"CubicPlanarHypohamiltonian",{70,4}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"CubicPlanarHypohamiltonian",{70,4}}],1]}]

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

{"CubicPlanarHypohamiltonian", {70, 5}}

Names

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"StandardName"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"StandardNames"]

Primary

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

All

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Degenerate"]

Configuration

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Configuration"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"]

PolyhedronGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"],{1,0,1,-Pi/2}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Hamiltonian"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"HamiltonianCycleCount"]

Planar

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Planar"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Planar"]//StyleGraphs

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"CubicPlanarHypohamiltonian",{70,5}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"CubicPlanarHypohamiltonian",{70,5}}],"OuterFace"->#]&/@faces

g=

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

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},{"RCN","CN"}]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Circulant"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"CubicPlanarHypohamiltonian",{70,5}}]])//Timing

Complement graph

compl=GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Line"]

LineGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicPlanarHypohamiltonian",{70,5}}&]

RootGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,5}}]]

Halin

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Halin"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Rigid"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Flexible"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"LCF"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"HamiltonianCycleCount"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"LCFSignature"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"LCFNotations"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,5}}],Debug->True]//Timing

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"CubicPlanarHypohamiltonian",{70,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicPlanarHypohamiltonian",{70,5}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicPlanarHypohamiltonian",{70,5}}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Matchstick"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Edges"]]

3D All

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedral"]

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron"]}]

3D Canonical

GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"CubicPlanarHypohamiltonian",{70,5}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"CubicPlanarHypohamiltonian",{70,5}}],-1]}]

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

{"CubicPlanarHypohamiltonian", {70, 6}}

Names

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"StandardName"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"StandardNames"]

Construction

http://users.cecs.anu.edu.au/~bdm/data/planegraphs.html

data=Import["http://users.cecs.anu.edu.au/~bdm/data/cubhypo70.pc","Byte"]

Position[data,0]//Length

Import["http://users.cecs.anu.edu.au/~bdm/data/hypo70-5s.png"]

v={{64,73},{79,70},{73,56},{57,56},{48,62},{51,70},{45,78},{57,89},{65,87},{73,90},{84,78},{81,62},{71,43},{60,43},{53,36},{42,40},{36,49},{36,60},{36,82},{41,95},{54,100},{76,100},{89,94},{93,81},{93,62},{93,49},{86,39},{76,36},{56,22},{36,30},{23,46},{22,65},{26,83},{33,102},{56,110},{74,109},{94,102},{104,82},{106,66},{104,47},{93,30},{73,23},{42,18},{24,32},{14,56},{17,75},{23,97},{42,113},{64,115},{87,113},{107,96},{112,75},{114,55},{105,33},{86,18},{65,16},{38,9},{16,26},{3,52},{3,80},{16,105},{37,122},{64,127},{92,122},{113,104},{126,79},{126,51},{113,27},{91,9},{64,3}};
g=Bilateralize@CenterGraph@ScaleGraph@Graph[Range@Length@v,Sort[Sort/@UndirectedEdge@@@{e[{57,70},57,43,30,44,31,45,32,46,33,47,34,48,35,49,36,50,37,51,38,52,39,53,40,54,41,55,42,56,29,43],{58,44},{55,69},{54,68},{53,67},{52,66},{59,45},{60,46},{61,47},{62,48},{49,63},{50,64},{51,65},e[30,16,17,31],e[32,18,5,6,7,19,33],e[39,25,12,2,11,24,38],e[35,21,8,9,10,22,36],e[29,15,14,13,28,42],e[5,4,3,12],{4,14},{13,3},e[19,20,21],{20,34},e[22,23,24],{23,37},{15,16},e[28,27,26,25],{27,41},{26,40},e[6,1,2],{1,9},{7,8},{10,11},{56,70},{17,18}}],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Through[{CubicGraphQ,PlanarGraphQ,HypohamiltonianGraphQ,BilateralGraphEmbeddingTypes}[g]]

Primary

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

All

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Degenerate"]

Configuration

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Configuration"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"]

PolyhedronGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"],{1,0,1,-Pi/2}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Hamiltonian"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"HamiltonianCycleCount"]

Planar

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Planar"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Planar"]//StyleGraphs

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"CubicPlanarHypohamiltonian",{70,6}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"CubicPlanarHypohamiltonian",{70,6}}],"OuterFace"->#]&/@faces

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

RecognizeGraph/@gs

Tutte embedding construction 14

GraphPlot[RotateGraph[,-3Pi/14]]

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

RecognizeGraph[g]

Tutte embedding construction 7

Bilateralize@RotateGraph[,6Pi/7]

GraphPlot[%]

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

RecognizeGraph[g]

Tutte embedding construction 4

Bilateralize@RotateGraph[,0]

GraphPlot[%]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},{"RCN","CN"}]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Circulant"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"CubicPlanarHypohamiltonian",{70,6}}]])//Timing

Complement graph

compl=GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"ComplementGraph","Name"]

Line graph

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Line"]

LineGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,6}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicPlanarHypohamiltonian",{70,6}}&]

RootGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}}]]

Halin

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Halin"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Rigid"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Flexible"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"LCF"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"HamiltonianCycleCount"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"LCFSignature"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"LCFNotations"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,6}}],Debug->True]//Timing

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"VertexList"],GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

gs={,};

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"CubicPlanarHypohamiltonian",{70,6}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicPlanarHypohamiltonian",{70,6}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicPlanarHypohamiltonian",{70,6}}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Matchstick"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Edges"]]

3D All

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedral"]

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron"]}]

3D Canonical

GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"CubicPlanarHypohamiltonian",{70,6}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"CubicPlanarHypohamiltonian",{70,6}}],-1]}]

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

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

{"CubicPlanarHypohamiltonian", {70, 7}}

Names

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"StandardName"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"StandardNames"]

Primary

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

All

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Degenerate"]

Configuration

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Configuration"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"]

PolyhedronGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"],{1,0,1,-Pi/2}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Hamiltonian"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"HamiltonianCycleCount"]

Planar

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Planar"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Planar"]//StyleGraphs

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}],"OuterFace"->#]&/@faces

g=;

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

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},{"RCN","CN"}]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Circulant"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}]])//Timing

Complement graph

compl=GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"ComplementGraph","Name"]

Line graph

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Line"]

LineGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"CubicPlanarHypohamiltonian",{70,7}}&]

RootGraph[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}]]

Halin

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Halin"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Rigid"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Flexible"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"LCF"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"HamiltonianCycleCount"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"LCFSignature"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"LCFNotations"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}],Debug->True]//Timing

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicPlanarHypohamiltonian",{70,7}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}],TimeConstraint->300,"Results"->All]//Timing}

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

Matchstick

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Matchstick"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Edges"]]

3D All

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedral"]

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron"]}]

3D Canonical

GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"CubicPlanarHypohamiltonian",{70,7}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"CubicPlanarHypohamiltonian",{70,7}}],1]}]

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

76

{"CubicPlanarHypohamiltonian", {76, 1-3}}

http://users.cecs.anu.edu.au/~bdm/data/planegraphs.html

http://users.cecs.anu.edu.au/~bdm/data/cubhypo76c5.pc may be some kind of planar code format, but not the usual ImportPlanarCode one.

data=Import["http://users.cecs.anu.edu.au/~bdm/data/cubhypo76c5.pc","Byte"];

Position[data,0]

The header of the page says, "plus a zero byte to end the list".  That's clearly incorrect here.

Length[data]

76 3 4

Take[data,100]

adj=Partition[Take[#,-3]&/@SequenceSplit[data,{s:Except[0,_Integer]..,0}:>{s}],76];

Length/@adj

CubicPlanarHypohamiltonianGraphs70=FromAdjacencyLists/@adj

{"CubicPlanarHypohamiltonian", {76, 1}}

Names

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"StandardName"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"StandardNames"]

Construction

ImageCrop@ImageRotate[ImageCrop[Import["http://users.cecs.anu.edu.au/~bdm/data/hypo76-5a-s.png"]],-13Degree]

v={{94,116},{87,128},{102,136},{81,148},{66,124},{59,134},{34,126},{32,103},{52,110},{65,107},{65,99},{47,88},{55,80},{69,85},{78,96},{93,100},{84,79},{92,92},{107,94},{103,85},{112,89},{113,81},{124,86},{130,78},{123,78},{116,69},{108,74},{104,66},{93,77},{90,68},{96,65},{93,53},{82,48},{80,56},{77,66},{70,60},{68,73},{56,62},{47,68},{21,77},{32,74},{36,59},{7,69},{22,134},{83,163},{143,133},{129,127},{121,116},{116,109},{121,104},{127,99},{134,96},{138,89},{142,80},{147,72},{157,67},{123,64},{115,61},{108,57},{102,49},{129,63},{129,48},{121,49},{107,39},{99,43},{84,39},{65,44},{53,49},{43,44},{111,25},{95,28},{79,31},{66,30},{50,27},{116,15},{49,16}};

Length[v]

McKay, B.D.  "Hypohamiltonian Planar Cubic Graphs with Girth 5."  J. Graph Th., 2016.  https://onlinelibrary.wiley.com/doi/10.1002/jgt.22043

Import["/Users/eww/Documents/Articles/McKay2016.pdf",{"PageGraphics",3}]

g76a=CenterGraph@ScaleGraph@RotateGraph[JournalOfGraphsGraphicToGraph[],{52,39}]

RecognizeGraph@g76a

Through[{CubicGraphQ,PlanarGraphQ,HypohamiltonianGraphQ}[g76a]]

Primary

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

All

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Degenerate"]

Configuration

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Configuration"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"]

PolyhedronGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"],{1,0,1,-Pi/2}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Hamiltonian"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"HamiltonianCycleCount"]

Planar

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Planar"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Planar"]//StyleGraphs

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"CubicPlanarHypohamiltonian",{76,1}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"CubicPlanarHypohamiltonian",{76,1}}],"OuterFace"->#]&/@faces

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

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},{"RCN","CN"}]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{76,1}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{76,1}}],TimeConstraint->5 3600])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Circulant"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"CubicPlanarHypohamiltonian",{76,1}}]])//Timing

Complement graph

compl=GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Line"]

LineGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{76,1}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,1}}]]

Halin

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Halin"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Rigid"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Flexible"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"LCF"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"HamiltonianCycleCount"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"LCFSignature"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"LCFNotations"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{76,1}}],Debug->True]//Timing

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Matchstick"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Edges"]]

3D All

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedral"]

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron"]}]

3D Canonical

GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"CubicPlanarHypohamiltonian",{76,1}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"CubicPlanarHypohamiltonian",{76,1}}],-1]}]

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

{"CubicPlanarHypohamiltonian", {76, 2}}

Names

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"StandardName"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"StandardNames"]

Construction

ImageCrop@ImageRotate[ImageCrop[Import["http://users.cecs.anu.edu.au/~bdm/data/hypo76-5b-s.png"]],-9Degree]

McKay, B.D.  "Hypohamiltonian Planar Cubic Graphs with Girth 5."  J. Graph Th., 2016.  https://onlinelibrary.wiley.com/doi/10.1002/jgt.22043

Import["/Users/eww/Documents/Articles/McKay2016.pdf",{"PageGraphics",3}]

g76b=CenterGraph@ScaleGraph@RotateGraph[JournalOfGraphsJournalOfGraphsGraphicToGraph[],{52,39}]

Through[{CubicGraphQ,PlanarGraphQ,HypohamiltonianGraphQ}[g76b]]

Primary

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

All

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Degenerate"]

Configuration

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Configuration"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"]

PolyhedronGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"],{1,0,1,-Pi/2}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Hamiltonian"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"HamiltonianCycleCount"]

Planar

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Planar"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Planar"]//StyleGraphs

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"CubicPlanarHypohamiltonian",{76,2}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"CubicPlanarHypohamiltonian",{76,2}}],"OuterFace"->#]&/@faces

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

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},{"RCN","CN"}]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Circulant"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"CubicPlanarHypohamiltonian",{76,2}}]])//Timing

Complement graph

compl=GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"ComplementGraph","Name"]

Line graph

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Line"]

LineGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{76,2}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,2}}]]

Halin

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Halin"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Rigid"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Flexible"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"LCF"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"HamiltonianCycleCount"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"LCFSignature"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"LCFNotations"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{76,2}}],Debug->True]//Timing

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Matchstick"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Edges"]]

3D All

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedral"]

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron"]}]

3D Canonical

GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"CubicPlanarHypohamiltonian",{76,2}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"CubicPlanarHypohamiltonian",{76,2}}],-1]}]

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

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

{"CubicPlanarHypohamiltonian", {76, 3}}

Names

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"StandardName"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"StandardNames"]

Construction

ImageCrop@ImageRotate[ImageCrop[Import["http://users.cecs.anu.edu.au/~bdm/data/hypo76-5c-s.png"]],-9Degree]

McKay, B.D.  "Hypohamiltonian Planar Cubic Graphs with Girth 5."  J. Graph Th., 2016.  https://onlinelibrary.wiley.com/doi/10.1002/jgt.22043

Import["/Users/eww/Documents/Articles/McKay2016.pdf",{"PageGraphics",4}]

g76c=CenterGraph@ScaleGraph@RotateGraph[JournalOfGraphsJournalOfGraphsGraphicToGraph[],{50,49}]

Through[{CubicGraphQ,PlanarGraphQ,HypohamiltonianGraphQ}[g76c]]

Primary

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

All

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Degenerate"]

Configuration

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Configuration"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"]

PolyhedronGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"],{1,0,1,-Pi/2}]

PolyhedronProjectionGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Hamiltonian"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"HamiltonianCycleCount"]

Planar

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Planar"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Planar"]//StyleGraphs

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}],"OuterFace"->#]&/@faces

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

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},{"RCN","CN"}]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Circulant"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}]])//Timing

Complement graph

compl=GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"ComplementGraph","Name"]

Line graph

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Line"]

LineGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}]]

Halin

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Halin"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Rigid"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Flexible"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"LCF"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"HamiltonianCycleCount"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"LCFSignature"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"LCFNotations"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}],Debug->True]//Timing

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"CubicPlanarHypohamiltonian",{76,3}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"CubicPlanarHypohamiltonian",{76,3}}],TimeConstraint->300,"Results"->All]//Timing}

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

gs={,,,};

Matchstick

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Matchstick"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Edges"]]

3D All

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedral"]

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Polyhedron"]}]

3D Canonical

GraphData[{"CubicPlanarHypohamiltonian",{76,3}},"Graph",{"3D","Canonical"}]

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

3D Canonical construction

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

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

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

SimplePolyhedronQ[can]

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

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

v=PolyhedronCoordinates[can];

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

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

g=PolyhedronGraph[can]

GraphData

GraphDataClassString

GraphDataClassString[{"Cubic","Planar","Hypohamiltonian"}]

GraphDataString

file=OpenWrite["~/chh70.m"]

Do[
WriteString[file,GraphDataString[CubicPlanarHypohamiltonianGraphs70[[i]],
"StandardName"->{"CubicPlanarHypohamiltonian",{70,i}},
"Name"->"70\[Hyphen]cubic planar hypohamiltonian graph "<>ToString[i],
"Information"->"CubicalPlanarHypohamiltonianGraph",
"Skip"->{"ABCEnergy","Arboricity","BurningNumber","ConnectedDominatingSet","ConnectedInducedSubgraphPolynomial","ConstructionNumber","CoolingNumber","IdiosyncraticPolynomial","IndependencePolynomial","IrredundancePolynomial","MatchingGeneratingPolynomial","MaximumIndependentVertexSets","MinimumConnectedDominatingSet","MinimumCyclicEdgeCuts","MinimumVertexColorings","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","Minors","QuadraticEmbeddingConstant","TotalDominationPolynomial","TuttePolynomial"}
]],
{i,{3,4,5,7}}]

Close[file]