Tilley Graph

Author

Eric W. Weisstein
September 9, 2022

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

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

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

Definition

Noted Sep 9, 2022 by Eric Weisstein

RecognizeGraph/@(EdgeDelete[GraphData["IcosahedralGraph"],#]&/@GraphData["IcosahedralGraph","Edges"])//Union

Tilley 2018

Tilley, James A.
Using Kempe exchanges to disentangle Kempe chains.
Math. Intelligencer 40 (2018), no. 1, 50–54.

Wagon

From Stan Wagon, May 14, 2015

The following planar graph has some interesting properties. Can you add it to GraphData. It is quite small so all your other properties will be easy to get.

Name should be TilleyGraph

Either it, or ideas underlying it, will appear in a paper by Jim Tilley, someone I know. I don’t think you need more details of why it is interesting as regards 4-color theorem issues. It is just a nice small planar graph with some nice properties.

Figure

GraphicsRow[Show[#//StyleGraphs,ImageSize->200]&/@{,}]

Properties

GraphData["TilleyGraph",{"V","E","F"}]

Faces

Tally[Length/@GraphData["TilleyGraph","Faces"]]

Embeddings

GraphData["TilleyGraph","StandardName"]

Primary

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

All

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

Planar

GraphData["TilleyGraph","Planar"]

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

Tutte embeddings

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

Tally[ReverseSort[Length/@faces]]

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

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

Tutte embedding construction 4

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

Tutte embedding construction 3 #1

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

Tutte embedding construction 3 #2

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

Tutte embedding construction 3 #3

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

Tutte embedding construction 3 #4

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

Tutte embedding construction 3 #5

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

Tutte embedding construction 3 #6

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

Manual construction

g=Graph[{1,2,3,4,5,6,7,8,9,10,11,12},UndirectedEdge@@@{{1,9},{1,10},{4,9},{4,10},{9,10},{2,11},{2,12},{11,12},{3,12},{3,11},{3,4},{3,7},{4,7},{3,8},{4,8},{5,7},{6,8},{1,5},{5,2},{2,6},{1,6},{5,9},{5,11},{7,9},{7,11},{8,10},{8,12},{6,12},{6,10}},VertexCoordinates->{{0,1},{0,-1},{0,-0.2},{0,0.2},{1,0},{-1,0},{0.6,0},{-0.6,0},{0.3,0.5},{-0.3,0.5},{0.3,-0.5},{-0.3,-0.5}}]

RecognizeGraph[g,Debug->True]

Halin

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

LCF

GraphData["TilleyGraph","LCFSignature"]

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

UnitDistance

GraphData["TilleyGraph","UnitDistance"]

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

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

Matchstick

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

Default embedding

g=Graph@GraphData["TilleyGraph","Edges"]

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

RecognizeGraph[g]

3D default

Graph3D[GraphData["TilleyGraph","Edges"]]

3D All

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

3D Polyhedron

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

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

3D Canonical

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

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

3D Polyhedron construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData["TilleyGraph"],-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]

GraphData

GraphClassString

GraphDataClassString["TilleyGraph"]