van Cleemput-Zamfirescu Graphs

Author

Eric W. Weisstein
May 24, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/vanCleemput-ZamfirescuGraphs.nb.

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

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

Figure

VanCleemputZamfirescu=SortBy[GraphData["VanCleemput*"],(ToExpression[StringCases[#,DigitCharacter..][[1]]]&)]

GraphicsRow[Show[StyleGraphs[GraphData[#],VertexSize->{"Scaled",.02}],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[12,Black,Italic,FontFamily->"Times New Roman",Hyphenation->True]],PageWidth->150,TextAlignment->Center]]&/@VanCleemputZamfirescu,Dividers->All,ImageSize->800]

GraphicsRow[Show[StyleGraphs[GraphData[#],VertexSize->{"Scaled",.02}],PlotLabel->TextCell[Style[GraphData[#,"V"],Directive[14,Black,FontFamily->"Times New Roman"]],TextAlignment->Center]]&/@VanCleemputZamfirescu,Dividers->All,ImageSize->800]

"VanCleemputZamfirescuGraph13"

Embeddings

GraphData["VanCleemputZamfirescuGraph13","StandardName"]

Primary

GraphData["VanCleemputZamfirescuGraph13"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["VanCleemputZamfirescuGraph13","Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["VanCleemputZamfirescuGraph13","EdgeList"]]

Default embedding

GraphPlot@GraphData["VanCleemputZamfirescuGraph13","Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData["VanCleemputZamfirescuGraph13","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["VanCleemputZamfirescuGraph13","Graph","Degenerate"]

Bilateral

GraphData["VanCleemputZamfirescuGraph13","Graph","Bilateral"]//StyleGraphs

Circular

GraphData["VanCleemputZamfirescuGraph13","Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData["VanCleemputZamfirescuGraph13"],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["VanCleemputZamfirescuGraph13"],#]&/@hc],CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData["VanCleemputZamfirescuGraph13","Planar"]

GraphData["VanCleemputZamfirescuGraph13","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["VanCleemputZamfirescuGraph13",{"RCN","CN"}]

GraphData["VanCleemputZamfirescuGraph13","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

MinimalCrossingGraph[GraphData["VanCleemputZamfirescuGraph13"]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["VanCleemputZamfirescuGraph13","Circulant"]

GraphData["VanCleemputZamfirescuGraph13","Graph","Circulant"]//StyleGraphs

Halin

GraphData["VanCleemputZamfirescuGraph13","Halin"]

GraphData["VanCleemputZamfirescuGraph13","Graph","Halin"]//StyleGraphs

Rigid

GraphData["VanCleemputZamfirescuGraph13","Rigid"]

GraphData["VanCleemputZamfirescuGraph13","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["VanCleemputZamfirescuGraph13","Flexible"]

GraphData["VanCleemputZamfirescuGraph13","Graph","Flexible"]//StyleGraphs

LCF

GraphData["VanCleemputZamfirescuGraph13","LCF"]

GraphData["VanCleemputZamfirescuGraph13","HamiltonianCycleCount"]

GraphData["VanCleemputZamfirescuGraph13","LCFSignature"]

GraphData["VanCleemputZamfirescuGraph13","LCFNotations"]

GraphData["VanCleemputZamfirescuGraph13","Graph","LCF"]//StyleGraphs

UnitDistance

GraphData["VanCleemputZamfirescuGraph13","UnitDistance"]

UnitDistanceGraphQ[GraphData["VanCleemputZamfirescuGraph13"],Debug->True]//Timing

GraphData["VanCleemputZamfirescuGraph13","Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["VanCleemputZamfirescuGraph13","VertexList"],GraphData["VanCleemputZamfirescuGraph13","EdgeList"]],MaxIterations->500]

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

GraphPlot@

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

RecognizeGraph@g

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["VanCleemputZamfirescuGraph13"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData["VanCleemputZamfirescuGraph13","Matchstick"]

GraphData["VanCleemputZamfirescuGraph13","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["VanCleemputZamfirescuGraph13","Edges"]]

3D All

GraphData["VanCleemputZamfirescuGraph13","Graph",{"3D","All"}]

3D UnitDistance

GraphData["VanCleemputZamfirescuGraph13","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["VanCleemputZamfirescuGraph13","Polyhedral"]

GraphData["VanCleemputZamfirescuGraph13","Graph",{"3D","Polyhedron"}]

HamiltonianCycles

GraphData["VanCleemputZamfirescuGraph13","HamiltonianCycles"]

FindHamiltonianCycle[GraphData["VanCleemputZamfirescuGraph13"]]//Timing

HamiltonianCycleCount

GraphData["VanCleemputZamfirescuGraph13","HamiltonianCycleCount"]

FindHamiltonianCycle[GraphData["VanCleemputZamfirescuGraph13"],All]//Length//Timing

HamiltonianPaths

GraphData["VanCleemputZamfirescuGraph13","HamiltonianPaths"]

HamiltonianPathCount

GraphData["VanCleemputZamfirescuGraph13","HamiltonianPathCount"]

MyFindHamiltonianPath[GraphData["VanCleemputZamfirescuGraph13"],All]//Length//Timing

Hypohamiltonian

GraphData["VanCleemputZamfirescuGraph13","Hypohamiltonian"]

Planar

GraphData["VanCleemputZamfirescuGraph13","Planar"]

PlanarGraphQ[GraphData["VanCleemputZamfirescuGraph13"]]

Polyhedral

GraphData["VanCleemputZamfirescuGraph13","Polyhedral"]

PolyhedralGraphQ[GraphData["VanCleemputZamfirescuGraph39"]]

Regular

GraphData["VanCleemputZamfirescuGraph13","Regular"]

Traceable

GraphData["VanCleemputZamfirescuGraph13","Traceable"]

UnitDistance

GraphData["VanCleemputZamfirescuGraph13","UnitDistance"]

UnitDistanceGraphQ[GraphData["VanCleemputZamfirescuGraph13"],Debug->True]//Timing

"VanCleemputZamfirescuGraph15"

Embeddings

GraphData["VanCleemputZamfirescuGraph15","StandardName"]

Primary

GraphData["VanCleemputZamfirescuGraph15"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["VanCleemputZamfirescuGraph15","Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["VanCleemputZamfirescuGraph15","EdgeList"]]

Default embedding

GraphPlot@GraphData["VanCleemputZamfirescuGraph15","Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData["VanCleemputZamfirescuGraph15","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["VanCleemputZamfirescuGraph15","Graph","Degenerate"]

Bilateral

GraphData["VanCleemputZamfirescuGraph15","Graph","Bilateral"]//StyleGraphs

Circular

GraphData["VanCleemputZamfirescuGraph15","Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData["VanCleemputZamfirescuGraph15"],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["VanCleemputZamfirescuGraph15"],#]&/@hc],CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData["VanCleemputZamfirescuGraph15","Planar"]

GraphData["VanCleemputZamfirescuGraph15","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["VanCleemputZamfirescuGraph15",{"RCN","CN"}]

GraphData["VanCleemputZamfirescuGraph15","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData["VanCleemputZamfirescuGraph15"],TimeConstraint->1])//AbsoluteTiming

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

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

MinimalCrossingGraph[GraphData["VanCleemputZamfirescuGraph15"]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["VanCleemputZamfirescuGraph15","Circulant"]

GraphData["VanCleemputZamfirescuGraph15","Graph","Circulant"]//StyleGraphs

Halin

GraphData["VanCleemputZamfirescuGraph15","Halin"]

GraphData["VanCleemputZamfirescuGraph15","Graph","Halin"]//StyleGraphs

Rigid

GraphData["VanCleemputZamfirescuGraph15","Rigid"]

GraphData["VanCleemputZamfirescuGraph15","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["VanCleemputZamfirescuGraph15","Flexible"]

GraphData["VanCleemputZamfirescuGraph15","Graph","Flexible"]//StyleGraphs

LCF

GraphData["VanCleemputZamfirescuGraph15","LCF"]

GraphData["VanCleemputZamfirescuGraph15","HamiltonianCycleCount"]

GraphData["VanCleemputZamfirescuGraph15","LCFSignature"]

GraphData["VanCleemputZamfirescuGraph15","LCFNotations"]

GraphData["VanCleemputZamfirescuGraph15","Graph","LCF"]//StyleGraphs

UnitDistance

GraphData["VanCleemputZamfirescuGraph15","UnitDistance"]

UnitDistanceGraphQ[GraphData["VanCleemputZamfirescuGraph15"],Debug->True]//Timing

GraphData["VanCleemputZamfirescuGraph15","Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["VanCleemputZamfirescuGraph15","VertexList"],GraphData["VanCleemputZamfirescuGraph15","EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["VanCleemputZamfirescuGraph15"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData["VanCleemputZamfirescuGraph15","Matchstick"]

GraphData["VanCleemputZamfirescuGraph15","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["VanCleemputZamfirescuGraph15","Edges"]]

3D All

GraphData["VanCleemputZamfirescuGraph15","Graph",{"3D","All"}]

3D UnitDistance

GraphData["VanCleemputZamfirescuGraph15","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["VanCleemputZamfirescuGraph15","Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData["VanCleemputZamfirescuGraph15","Polyhedron"]}]

3D UnitDistance

GraphData["VanCleemputZamfirescuGraph15","Graph",{"3D","UnitDistance"}]

3D Canonical

GraphData["VanCleemputZamfirescuGraph15","Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData["VanCleemputZamfirescuGraph15","Polyhedron"],Yellow,Sphere[]}]

3D Polyhedron construction

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

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->1000,MaxIterations->10000,PrecisionGoal->20])//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]

HamiltonianCycleCount

GraphData["VanCleemputZamfirescuGraph15","HamiltonianCycleCount"]

HamiltonianCycles

GraphData["VanCleemputZamfirescuGraph15","HamiltonianCycles"]

FindHamiltonianCycle[GraphData["VanCleemputZamfirescuGraph15"]]//Timing

HamiltonianPaths

GraphData["VanCleemputZamfirescuGraph15","HamiltonianPaths"]

HamiltonianPathCount

GraphData["VanCleemputZamfirescuGraph15","HamiltonianPathCount"]

Hypohamiltonian

GraphData["VanCleemputZamfirescuGraph15","Hypohamiltonian"]

Planar

GraphData["VanCleemputZamfirescuGraph15","Planar"]

PlanarGraphQ[GraphData["VanCleemputZamfirescuGraph15"]]

Polyhedral

GraphData["VanCleemputZamfirescuGraph15","Polyhedral"]

PolyhedralGraphQ[GraphData["VanCleemputZamfirescuGraph39"]]

Regular

GraphData["VanCleemputZamfirescuGraph15","Regular"]

Traceable

GraphData["VanCleemputZamfirescuGraph15","Traceable"]

UnitDistance

GraphData["VanCleemputZamfirescuGraph15","UnitDistance"]

UnitDistanceGraphQ[GraphData["VanCleemputZamfirescuGraph15"],Debug->True]//Timing

"VanCleemputZamfirescuGraph39"

Embeddings

Default

GraphData["VanCleemputZamfirescuGraph39"]//StyleGraphs

All

GraphData["VanCleemputZamfirescuGraph39","Graph","All"]//StyleGraphs

Built-in (spring-embedding)

GraphPlot[GraphData["VanCleemputZamfirescuGraph39","Edges"]]

Construction from spring-embedding

e[l__]:=Sequence@@Partition[{l},2,1];
v=Union[Flatten[Table[{i,j}#&/@{{0,0},{2,0},{4,0},{1,1},{3,1},{5,1},{1,2},{3,2},{2,3},{0,4},{1,4},{3,4}},{i,{-1,1}},{j,{-1,1}}],2]];
v={#+Sign[#]3/2,#2}&@@@v;
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[4,13,19,22,31,38,39,36,27,21,18,9,2,1,4],e[27,26,35,36,30,26,20,14,10,4,5,14,13,10,5,1,3,7,6,15,16,7,11,15,19,24,33,34,25,24,29,34,37,38,32,28,22,23,32,31,28,23,20,17,12,9,8,12,18,17,8,2,3,6,11,16,21,25,29,33,37,39,35,30,27]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Built-in Planar (spring-embedding)

PlanarGraph[GraphData["VanCleemputZamfirescuGraph39","Edges"]]

3D default

Graph3D[GraphData["VanCleemputZamfirescuGraph39","Edges"]]

3D All

GraphData["VanCleemputZamfirescuGraph39","Graph",{"3D","All"}]

3D UnitDistance

GraphData["VanCleemputZamfirescuGraph39","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["VanCleemputZamfirescuGraph39","Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData["VanCleemputZamfirescuGraph39","Polyhedron"]}]

3D Canonical

GraphData["VanCleemputZamfirescuGraph39","Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData["VanCleemputZamfirescuGraph39","Polyhedron"],Yellow,Sphere[]}]

3D Polyhedron construction

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

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->100,MaxIterations->5000,PrecisionGoal->20,"ProgressInterval"->500,"TangentFactor"->1/5,"PlanarFactor"->1/5,Debug->True])//Timing

Graphics3D[can]

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

(can=FindCanonicalPolyhedron[can,WorkingPrecision->50,MaxIterations->100000,PrecisionGoal->20,"ProgressInterval"->1000,"TangentFactor"->1/5,"PlanarFactor"->1/5,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]

Hamiltonian

GraphData["VanCleemputZamfirescuGraph39","Hamiltonian"]

HamiltonianGraphQ[GraphData["VanCleemputZamfirescuGraph39"]]//Timing

HamiltonianCycle

GraphData["VanCleemputZamfirescuGraph39","HamiltonianCycles"]

FindHamiltonianCycle[GraphData["VanCleemputZamfirescuGraph39"]]//Timing

HamiltonianCycleCount

GraphData["VanCleemputZamfirescuGraph39","HamiltonianCycleCount"]

HamiltonianPathCount

GraphData["VanCleemputZamfirescuGraph39","HamiltonianPathCount"]

HamiltonianPaths

GraphData["VanCleemputZamfirescuGraph39","HamiltonianPaths"]

FindHamiltonianPath[g39]//Timing

Hypohamiltonian

GraphData["VanCleemputZamfirescuGraph39","Hypohamiltonian"]

HypohamiltonianGraphQ[g39]//Timing

Planar

GraphData["VanCleemputZamfirescuGraph39","Planar"]

PlanarGraphQ[GraphData["VanCleemputZamfirescuGraph39"]]

Polyhedral

GraphData["VanCleemputZamfirescuGraph39","Polyhedral"]

PolyhedralGraphQ[GraphData["VanCleemputZamfirescuGraph39"]]

Quartic

GraphData["VanCleemputZamfirescuGraph39","Quartic"]

QuarticGraphQ[GraphData["VanCleemputZamfirescuGraph39"]]

Traceable

GraphData["VanCleemputZamfirescuGraph39","Traceable"]

UnitDistance

GraphData["VanCleemputZamfirescuGraph39","UnitDistance"]

UnitDistanceGraphQ[GraphData["VanCleemputZamfirescuGraph39"],Debug->True]//Timing

"VanCleemputZamfirescuGraph78"

Embeddings

Default

GraphData["VanCleemputZamfirescuGraph78"]//StyleGraphs

All

GraphData["VanCleemputZamfirescuGraph78","Graph","All"]//StyleGraphs

Built-in (spring-embedding)

Graph[GraphData["VanCleemputZamfirescuGraph78","Edges"]]

Built-in Planar (spring-embedding)

PlanarGraph[GraphData["VanCleemputZamfirescuGraph78","Edges"]]

3D default

Graph3D[GraphData["VanCleemputZamfirescuGraph78","Edges"]]

3D All

GraphData["VanCleemputZamfirescuGraph78","Graph",{"3D","All"}]

3D UnitDistance construction

g=UnitDistanceEmbeddingRefine@GraphData["VanCleemputZamfirescuGraph78","Graph","3D"]

3D UnitDistance

GraphData["VanCleemputZamfirescuGraph78","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["VanCleemputZamfirescuGraph78","Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData["VanCleemputZamfirescuGraph78","Polyhedron"]}]

3D Canonical

GraphData["VanCleemputZamfirescuGraph78","Graph",{"3D","Canonical"}]

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

3D Polyhedron construction

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

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->100,MaxIterations->5000,PrecisionGoal->20,"ProgressInterval"->500,"TangentFactor"->1/5,"PlanarFactor"->1/5,Debug->True])//Timing

Graphics3D[can]

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

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

(can=FindCanonicalPolyhedron[can,WorkingPrecision->50,MaxIterations->100000,PrecisionGoal->20,"ProgressInterval"->1000,"TangentFactor"->1/5,"PlanarFactor"->1/5,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]

Properties

Hamiltonian

GraphData["VanCleemputZamfirescuGraph78","Hamiltonian"]

HamiltonianCycleCount

GraphData["VanCleemputZamfirescuGraph78","HamiltonianCycleCount"]

HamiltonianCycles

GraphData["VanCleemputZamfirescuGraph78","HamiltonianCycles"]

FindHamiltonianCycle[GraphData["VanCleemputZamfirescuGraph78"]]//Timing

HamiltonianPathCount

GraphData["VanCleemputZamfirescuGraph78","HamiltonianPathCount"]

HamiltonianPaths

GraphData["VanCleemputZamfirescuGraph78","HamiltonianPaths"]

FindHamiltonianPath[GraphData["VanCleemputZamfirescuGraph78"]]//Timing

...ran for several days...

Hypohamiltonian

GraphData["VanCleemputZamfirescuGraph78","Hypohamiltonian"]

HypohamiltonianGraphQ[GraphData["VanCleemputZamfirescuGraph78"]]//Timing

Hypotraceable

GraphData["VanCleemputZamfirescuGraph78","Hypotraceable"]

HypotraceableGraphQ[GraphData["VanCleemputZamfirescuGraph78"],"Traceable"->False]//Timing

Planar

GraphData["VanCleemputZamfirescuGraph78","Planar"]

PlanarGraphQ[GraphData["VanCleemputZamfirescuGraph78"]]

Polyhedral

GraphData["VanCleemputZamfirescuGraph78","Polyhedral"]

PolyhedralGraphQ[GraphData["VanCleemputZamfirescuGraph78"]]

Quartic

GraphData["VanCleemputZamfirescuGraph78","Quartic"]

QuarticGraphQ[GraphData["VanCleemputZamfirescuGraph78"]]

Traceable

GraphData["VanCleemputZamfirescuGraph78","Traceable"]

UnitDistance

GraphData["VanCleemputZamfirescuGraph78","UnitDistance"]

UnitDistanceGraphQ[GraphData["VanCleemputZamfirescuGraph78"],Debug->True]//Timing

VertexConnectivity

GraphData["VanCleemputZamfirescuGraph78","VertexConnectivity"]

VertexConnectivity[GraphData["VanCleemputZamfirescuGraph78"]]

"VanCleemputZamfirescuGraph108"

Embeddings

Default

GraphData["VanCleemputZamfirescuGraph108"]//StyleGraphs[#,VertexSize->{"Scaled",.015}]&

All

GraphData["VanCleemputZamfirescuGraph108","Graph","All"]//StyleGraphs

Built-in (spring-embedding)

Graph[GraphData["VanCleemputZamfirescuGraph108","Edges"]]

Built-in Planar (spring-embedding)

PlanarGraph[GraphData["VanCleemputZamfirescuGraph108","Edges"]]

<<IGraphM`

IGLayoutTutte[Graph[GraphData["VanCleemputZamfirescuGraph108","EdgeList"]]]

3D default

Graph3D[GraphData["VanCleemputZamfirescuGraph108","Edges"]]

3D All

GraphData["VanCleemputZamfirescuGraph108","Graph",{"3D","All"}]

3D UnitDistance

GraphData["VanCleemputZamfirescuGraph108","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["VanCleemputZamfirescuGraph108","Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData["VanCleemputZamfirescuGraph108","Polyhedron"]}]

3D Canonical

GraphData["VanCleemputZamfirescuGraph108","Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData["VanCleemputZamfirescuGraph108","Polyhedron"],Yellow,Sphere[]}]

3D Polyhedron construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData["VanCleemputZamfirescuGraph108"],-1,"Normalize"->True]}]

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

Graphics3D[can]

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]

3D Canonical construction from PolyhedralEmbedding

g=GraphData["VanCleemputZamfirescuGraph108","Graph","Planar"][[1]]

Show[g2=PolyhedralEmbedding[g,"Circular"->True,"Scale"->3],Boxed->True]//Quiet

With[
{faces=PlanarFaceList[Graph[EdgeList[g2]]],v=GraphEmbedding@g2},
Graphics3D[{Point[{0,0,0}],Opacity[.5],Sphere[],FaceForm[Green,Red],
poly=Polyhedron[1.2v,faces]}]]

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

Graphics3D[can]

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]

Properties

ChromaticNumber

GraphData["VanCleemputZamfirescuGraph108","ChromaticNumber"]

VertexChromaticNumber[GraphData["VanCleemputZamfirescuGraph108"]]//Timing

IGChromaticNumber[GraphData["VanCleemputZamfirescuGraph108"]]//Timing

EdgeChromaticNumber

GraphData["VanCleemputZamfirescuGraph108","EdgeChromaticNumber"]

EdgeChromaticNumber[GraphData["VanCleemputZamfirescuGraph108"]]//Timing

IGChromaticIndex[GraphData["VanCleemputZamfirescuGraph108"]]//Timing

IGChromaticNumber[LineGraph[GraphData["VanCleemputZamfirescuGraph108"]]]//Timing

MyFindEdgeColoring[GraphData["VanCleemputZamfirescuGraph108"],Method->"Blossom",Debug->True]//Timing

MyFindEdgeColoring[GraphData["VanCleemputZamfirescuGraph108"],Method->"VizingClass1",Debug->True]//Timing

MyFindEdgeColoring[GraphData["VanCleemputZamfirescuGraph108"],Method->"VizingClass2",Debug->True]//Timing

Hamiltonian

GraphData["VanCleemputZamfirescuGraph108","Hamiltonian"]

HamiltonianGraphQ[GraphData["VanCleemputZamfirescuGraph108"]]//Timing

HamiltonianCycleCount

GraphData["VanCleemputZamfirescuGraph108","HamiltonianCycleCount"]

HamiltonianPathCount

GraphData["VanCleemputZamfirescuGraph108","HamiltonianPathCount"]

LCF

GraphData["VanCleemputZamfirescuGraph108","LCF"]

LCFNotations

GraphData["VanCleemputZamfirescuGraph108","LCFNotations"]

LCFSignature

GraphData["VanCleemputZamfirescuGraph108","LCFSignature"]

Traceable

GraphData["VanCleemputZamfirescuGraph108","Traceable"]

TraceableGraphQ[GraphData["VanCleemputZamfirescuGraph108"]]//Timing

UnitDistance

GraphData["VanCleemputZamfirescuGraph108","UnitDistance"]

UnitDistanceGraphQ[GraphData["VanCleemputZamfirescuGraph108"],Debug->True]//Timing

Construction

"VanCleemputZamfirescuGraph13"

Van Cleemput and Zamfirescu 2018, Fig. ...

http://czamfirescu.tricube.de/CTZamfirescu-28.pdf

e[x__]:=Sequence@@Partition[{x},2,1]

valpha={{518.6569406275923`,270.0713804851207`},{490.56179281553403`,281.574090149061`},{511.5516489795598`,289.47716892950416`},{510.5889346995835`,309.52924166144146`},{479.0993560597202`,299.5338894159501`},{461.09161285458526`,283.25021023013534`},{485.3013839112012`,265.27123338794786`},{530.4051232553513`,248.30291476398259`},{542.1513881255804`,286.4336877296587`},{535.2397899880611`,323.4157239349646`},{446.7889771970883`,311.6157618539001`},{442.98031074283927`,263.58360676169457`},{580,286.4336877296587`}};

alpha=CenterGraph@ScaleGraph@Graph[Range[Length[valpha]],UndirectedEdge@@@{e[12,8,13,10,11,12,6,11,4,9,1,7,12],e[10,9,8,7,2,5,11],e[7,6,2,3,9],e[8,1,3,4,10],e[6,5,4],{3,5},{2,1}},VertexCoordinates->valpha,VertexLabels->Automatic]

VertexCount[alpha]

RecognizeGraph[alpha]

PlanarGraph[EdgeList[alpha]]

GraphPlot@RotateGraph[alpha,Pi/2,VertexLabels->None]

Solve[CirclePoints[{a,-Pi/2},5][[3,2]]==v[[4,2]],a]//FullSimplify

v=Join[CirclePoints[Csc[Pi/5]/2,5],CirclePoints[{(Sqrt[1-(2/(Sqrt[5]))]),-Pi/2},5],{{0,0}}];
v=Join[v,{Mean[v[[{4,9}]]],Mean[{v[[3]],{0,v[[4,2]]}}]}];
alpha2=Graph[Range[Length[v]],Sort[Sort/@UndirectedEdge@@@{e[1,2,3,4,5,1,7,6,10,12,13,8,7,11,10,9,13,2,7],e[10,5,6,1],e[13,4,12,9,8,2],e[9,11,8],{6,11},{12,5}}],VertexCoordinates->FullSimplify[v],VertexLabels->Automatic,Axes->True]

IsomorphicGraphQ[alpha,alpha2]

"VanCleemputZamfirescuGraph15"

Van Cleemput and Zamfirescu 2018, Fig. ...

http://czamfirescu.tricube.de/CTZamfirescu-28.pdf

vbeta={{523.7262819080112`,124.76807279591571`},{528.6509714107422`,135.89263116970739`},{516.3474350013839`,136.31632640123905`},{505.7038832914085`,135.13120785507067`},{510.5999170779972`,124.53473339304315`},{517.5264130369504`,115.56344740365421`},{537.0511899141536`,118.02169848128511`},{537.1535317575187`,140.4714052418641`},{516.773177069783`,151.52227748843285`},{496.52996045215656`,139.76729335951188`},{498.3721136327292`,117.04740413244889`},{517.583724469235`,106.06817117623575`},{566.6607320365583`,100.22240508321846`},{516.3699502069243`,187.30098592888882`},{466.7546245435002`,99.61244769676216`}};

beta=CenterGraph@ScaleGraph@Graph[Range[Length[vbeta]],Sort[Sort/@UndirectedEdge@@@{e[15,13,14,15,12,13,8,14,10,15],e[10,11,12,7,8,9,10,4,3,2,8],e[11,6,7,1,5,11],e[12,6,5,4,9,2,7],{11,4},e[5,3,1,2],{1,6},{3,9}}],VertexCoordinates->vbeta,VertexLabels->Automatic,Axes->True]

VertexCount[beta]

RecognizeGraph@beta

"VanCleemputZamfirescuGraph39"

39-node quartic nonhamiltonian planar (polyhedral)

Van Cleemput and Zamfirescu 2018, Fig. 2

http://czamfirescu.tricube.de/CTZamfirescu-28.pdf

Import["http://czamfirescu.tricube.de/CTZamfirescu-28.pdf","EmbeddedImages"]

pic=;

g=IndexGraph[MorphologicalGraph[Thinning[ColorNegate[Binarize[pic]],Method->"MedialAxis"]]]

pts=GraphEmbedding[g];

Median[EuclideanDistance[pts[[#[[1]]]],pts[[#[[2]]]]]&/@EdgeList[g]]

f=Nearest[Thread[pts->Range[Length[pts]]]]

merge=Select[f[#,{All,15}]&/@pts,Length[#]>1&];

HighlightGraph[g,merge,VertexSize->1]

final=Fold[VertexContract,g,merge]

g0=IndexGraph@Annotate[final,{VertexSize->{"Scaled",.01},VertexLabels->Automatic}]

VertexList[g0]

d=VertexDegree[g0]

g1=VertexDelete[g0,Flatten[Position[d,1]]]

VertexDegree[g1]

g0=IndexGraph@;

v0=GraphEmbedding[g0];

{{xmin,xmax},{ymin,ymax}}=MinMax/@Transpose[v0]

v={((#-xmin)/(xmax-xmin)),((#2-ymin)/(xmax-ymin))}&@@@v0;

g39=Graph[VertexList[g0],Sort[Sort/@EdgeList[g0]],VertexCoordinates->v]

g39=;

VertexList[g39]

VertexCount[g39]

GraphAutomorphismGroup[g]

VertexDegree[g39]//Tally

"VanCleemputZamfirescuGraph78"

78-node untraceable quartic planar (polyhedral)

Van Cleemput and Zamfirescu 2018, Fig. 11

http://czamfirescu.tricube.de/CTZamfirescu-28.pdf

Import["http://czamfirescu.tricube.de/CTZamfirescu-28.pdf","EmbeddedImages"]

v0=;

Length[v0]

{{xmin,xmax},{ymin,ymax}}=MinMax/@Transpose[v0]

v={((#-xmin)/(xmax-xmin)),((#2-ymin)/(xmax-ymin))}&@@@v0;

e[x__]:=Sequence@@Partition[{x},2,1]

g78=Graph[Range[Length[v]],UndirectedEdge@@@Sort[Sort/@{e[78,77,61,30,5,2,14,41,68,78,75,73,77,76,75,74,73,76,78],e[68,57,52,38,51,57,53,52,51,29,10,4,2,3,7,17,16,32,42,54,61,62,69,70,71,72,67,68],e[71,74,70,64,63,62,58,64,69,63,58,59,60,67,66,65,71],e[72,66,60,65,72],e[38,53,39,23,12,4,11,22,12,11,10,22,23,24,39,38],e[41,40,25,14,13,25,41],e[24,40,13,24],e[59,56,50,29,21,19,27,28,21,20,27,1,28,20,19,26,45,55,59],e[56,49,37,50,49,48,56],e[37,48,36,37],e[36,1,35,36],e[35,47,34,35],e[47,55,46,34,45,46,47],e[3,9,26,44,43,42,33,44,54,43,33,32,17,18,9,8,7,18,8,3],e[5,6,15,30,31,15,5],e[6,31,16,6]}],VertexCoordinates->v,VertexLabels->Automatic]

g78=;

VertexDegree[g78]//Union

"VanCleemputZamfirescuGraph108"

http://czamfirescu.tricube.de/CTZamfirescu-28.pdf

DisplaceGraph[g_Graph,xy_]:=Graph[VertexList[g],EdgeList[g],VertexCoordinates->(#+xy&/@GraphEmbedding[g])]

SpliceGraph[g1_,g02_,Rule[del_Integer,{add__Integer}],sc_,rot_,opts___?OptionQ]:=Module[
{
vl=VertexList[g1],
v1=GraphEmbedding[g1],vnew,
g2,pos
},
pos=FirstPosition[vl,del][[1]];
g2=DisplaceGraph[RotateGraph[ScaleGraph[CenterGraph@g02,sc],rot],v1[[pos]]];
vnew=Join[
Delete[GraphEmbedding[g1],pos],
GraphEmbedding[g2]
];
Graph[
DeleteCases[Join[vl,Max[vl]+VertexList[g2]],del],
Join[
EdgeList[VertexDelete[g1,del]],
EdgeList[g2]/.i_Integer:>i+Max[vl],
UndirectedEdge@@@Transpose[{Max[vl]+add,AdjacencyList[g1,del]}]
],
VertexCoordinates->vnew,
opts
]
]

g0=GraphData["RhombicDodecahedralGraph","Graph",{"Labeled","Planar"}][[2]]

alpha=GraphData["VanCleemputZamfirescuGraph13","Graph","Labeled"]

beta=GraphData["VanCleemputZamfirescuGraph15","Graph","Labeled"]

h1=SpliceGraph[g0,beta,3->{15,13,14},1,1.2,VertexLabels->Automatic]

h2=SpliceGraph[h1,beta,2->{13,15,14},.5,-.8,VertexLabels->Automatic,VertexSize->1]

SpliceGraph[g1_,g02_,del_->{a1_->del2_,l_List},sc_,rot_,opts___?OptionQ]:=Module[
{
vl=VertexList[g1],
v1=GraphEmbedding[g1],
g2,
pos1,pos2,
vs,vnew
},
pos1=FirstPosition[vl,del][[1]];
pos2=FirstPosition[vl,del2][[1]];
g2=DisplaceGraph[RotateGraph[ScaleGraph[CenterGraph@g02,sc],rot],v1[[pos1]]];
vnew=Join[
Delete[GraphEmbedding[g1],List/@{pos1,pos2}],
GraphEmbedding[g2]
];
vs=DeleteCases[Join[vl,Max[vl]+VertexList[g2]],del|del2];
Graph[
vs,
Join[
EdgeList[VertexDelete[g1,{del,del2}]],
EdgeList[g2]/.i_Integer:>i+Max[vl],
UndirectedEdge[a1+Max[vl],#]&/@DeleteCases[AdjacencyList[g1,del2],del],
UndirectedEdge@@@Transpose[{l+Max[vl],DeleteCases[AdjacencyList[g1,del],del2]}]
],
VertexCoordinates->vnew,
opts
]
]

i1=SpliceGraph[h2,alpha,6->{3->1,{1,4}},.5,Pi/2,VertexSize->1,VertexLabels->Automatic]

i2=SpliceGraph[i1,alpha,13->{3->8,{1,4}},.5,Pi/2,VertexSize->1,VertexLabels->Automatic]

i3=SpliceGraph[i2,alpha,10->{3->4,{1,4}},.5,Pi/2,VertexSize->1,VertexLabels->Automatic]

i4=SpliceGraph[i3,alpha,12->{3->14,{1,4}},.5,Pi/2,VertexSize->1,VertexLabels->Automatic]

i5=SpliceGraph[i4,alpha,9->{3->7,{1,4}},.5,Pi/2,VertexSize->1,VertexLabels->Automatic]

i6=SpliceGraph[i5,alpha,5->{3->11,{1,4}},.5,Pi/2,VertexSize->1,VertexLabels->Automatic]

g108=IndexGraph[i6,VertexLabels->None]

g108new=Graph[VertexList[g108],Sort[Sort/@EdgeList[g108]]]

g108new=;

VertexDegree[g]//Union

VertexCount[g]

PolyhedralGraphQ[g]

FindHamiltonianPath[g]//Timing

GraphPlot@RotateGraph[PlanarGraph[EdgeList[g]],.45,VertexSize->20]

g=RotateGraph[GraphicsToGraph@,Pi/2,VertexSize->1]

RectilinearCrossingCount[g]//Timing

RecognizeGraph[g]

GraphData

GraphData

GraphDataString

file=OpenWrite["~/vcz.m"]

"VanCleemputZamfirescuGraph13

WriteString[file,GraphDataString[alpha2,
"StandardName"->"VanCleemputZamfirescuGraph13",
"Name"->"van Cleemput\[Hyphen]Zamfirescu graph 13",
"Information"->"VanCleemput-ZamfirescuGraphs"]]//Timing//AbsoluteTiming

"VanCleemputZamfirescuGraph15"

file=OpenWrite["~/vcz.m"]

WriteString[file,GraphDataString[beta,
"StandardName"->"VanCleemputZamfirescuGraph15",
"Name"->"van Cleemput\[Hyphen]Zamfirescu graph 15",
"Information"->"VanCleemput-ZamfirescuGraphs"]]//Timing//AbsoluteTiming

"VanCleemputZamfirescuGraph39"

<<MathWorld`Graphs`

file=OpenWrite["~/vcz.m"]

WriteString[file,GraphDataString[g39,
"StandardName"->"VanCleemputZamfirescuGraph39",
"Name"->"van Cleemput\[Hyphen]Zamfirescu graph 39",
"Information"->"VanCleemput-ZamfirescuGraphs"]]

"VanCleemputZamfirescuGraph78"

WriteString[file,GraphDataString[g78,
"StandardName"->"VanCleemputZamfirescuGraph78",
"Name"->"van Cleemput\[Hyphen]Zamfirescu graph 78",
"Information"->"VanCleemput-ZamfirescuGraphs"]]

"VanCleemputZamfirescuGraph108"

WriteString[file,GraphDataString[g108new,
"StandardName"->"VanCleemputZamfirescuGraph108",
"Name"->"van Cleemput\[Hyphen]Zamfirescu graph 108",
"Embeddings"->{},
"Information"->"VanCleemput-ZamfirescuGraphs",
"Classes"->{"Untraceable"},
"Skip"->{"EdgeChromaticNumber"}
]]