Poussin Graph

Author

Eric W. Weisstein
January 28, 2023

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

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

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

Embeddings

GraphData["PoussinGraph","StandardName"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["PoussinGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

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

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

bilat

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

quad

Planar

GraphData["PoussinGraph","Planar"]

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

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData["PoussinGraph"]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData["PoussinGraph"],"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["PoussinGraph",{"RCN","CN"}]

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

Circulant

GraphData["PoussinGraph","Circulant"]

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

Halin

GraphData["PoussinGraph","Halin"]

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

Rigid

GraphData["PoussinGraph","Rigid"]

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

Flexible

GraphData["PoussinGraph","Flexible"]

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

LCF

GraphData["PoussinGraph","LCF"]

GraphData["PoussinGraph","HamiltonianCycleCount"]

GraphData["PoussinGraph","LCFSignature"]

GraphData["PoussinGraph","LCFNotations"]

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

UnitDistance

GraphData["PoussinGraph","UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData["PoussinGraph","Matchstick"]

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

3D default

Graph3D[GraphData["PoussinGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

3D Canonical

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

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

3D Canonical construction

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

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

Construction

Wagon

l=;

ShowLabeledGraph[g=LinesToGraph[l]]

RecognizeGraph[g]

(g2=RenumberVertices[g,{8,13,4,10,6,2,14,7,15,1,3,9,5,12,11}])//ShowLabeledGraph

FastIsomorphicQ[g,g2]

Wikipedia

Import["http://upload.wikimedia.org/wikipedia/commons/d/d5/Poussin_graph.svg","String"]

GraphData["PoussinGraph",{"V","M"}]

ShowLabeledGraph[g=AddEdges[Cycle[15],{{3,15},{3,14},{3,10},{4,10},{7,11},{7,12},{4,2},{2,5},{5,12},{5,7},{6,8},{8,10},{4,6},{2,15},{13,15},{11,13},{1,12},{10,14},{8,4},{9,7},{9,11},{1,5},{1,13},{11,14}}]]

M[g]

RecognizeGraph[g]

GraphData["PoussinGraph","Hamiltonian"]

GraphData["PoussinGraph","Regular"]

GraphData["PoussinGraph","LCFNotations"]

GraphData

GraphClassString

GraphClassString["PoussinGraph"]

GraphDataString

WriteString[file,GraphDataString[g2,
"StandardName"->"PoussinGraph",
"Name"->"Poussin graph",
"Classes"->{"KempeCounterexample"},
"Information"->"PoussinGraph",
Debug->True,
TimeConstraint->120
]]