Kittell Graph

Author

Eric W. Weisstein
March 6, 2023

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

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

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

Embeddings

GraphData["KittellGraph","StandardName"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["KittellGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

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

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

gs=bilat

Planar

GraphData["KittellGraph","Planar"]

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

Tutte embeddings

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

Tally[ReverseSort[Length/@faces]]

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

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

Circulant

GraphData["KittellGraph","Circulant"]

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

Halin

GraphData["KittellGraph","Halin"]

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

Rigid

GraphData["KittellGraph","Rigid"]

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

Flexible

GraphData["KittellGraph","Flexible"]

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

LCF

GraphData["KittellGraph","LCF"]

GraphData["KittellGraph","HamiltonianCycleCount"]

GraphData["KittellGraph","LCFSignature"]

GraphData["KittellGraph","LCFNotations"]

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

UnitDistance

GraphData["KittellGraph","UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData["KittellGraph","Matchstick"]

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

3D default

Graph3D[GraphData["KittellGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

3D Canonical

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

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

3D Canonical construction

<<MathWorld`Graphs`

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

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

Four-Coloring

<<Wagon1998`GraphColoring`

Wagon's package must be run in v4.1 using the old Combinatorica package

?KittellGraph

FourColoring[KittellGraph]

GraphData

GraphClassString

GraphClassString["KittellGraph"]