Chiu Graph

Author

Eric W. Weisstein
July 26, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/ChiuGraph.nb.

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

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

Figure

GraphicsGrid[Partition[StyleGraphs@GraphData["ChiuGraph","Graph","All"],UpTo[4]],Dividers->All]

Embeddings

<<MathWorld`Graphs`

Names

GraphData["ChiuGraph","StandardName"]

GraphData["ChiuGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["ChiuGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

GraphData["ChiuGraph","Planar"]

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

Tutte embeddings

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

Tally[ReverseSort[Length/@faces]]

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

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

RecognizeGraph/@gs

Tutte embedding construction 6

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

RecognizeGraph[g]

Tutte embedding construction 3

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

RecognizeGraph[g]

MinimalCrossing

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

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

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData["ChiuGraph"]],Pi/2]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Halin

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

LCF

GraphData["ChiuGraph","LCF"]

GraphData["ChiuGraph","LCFSignature"]

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

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

LCF compute

Length[FindHamiltonianCycle[GraphData["ChiuGraph"],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData["ChiuGraph"],All])[[All,2]]]//Timing

gs=LCFGraph@@@lcf//StyleGraphs

gs=Join[With[{g=BilateralLCFEmbedding[#]},If[MissingQ[g],#,g]]&/@LCFGraph@@@DeleteCases[lcf,{_,1}],DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]]

UnitDistance

GraphData["ChiuGraph","UnitDistance"]

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

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

Matchstick

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

3D default

Graph3D[GraphData["ChiuGraph","Edges"]]

3D All

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

3D Polyhedron

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

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

3D Canonical

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

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

3D Polyhedron construction

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

Properties

ChromaticNumber

GraphData["ChiuGraph","ChromaticNumber"]

VertexChromaticNumber[GraphData["ChiuGraph"]]//Timing

<<IGraphM`

IGChromaticNumber[GraphData["ChiuGraph"]]//Timing

EdgeChromaticNumber

GraphData["ChiuGraph","EdgeChromaticNumber"]

EdgeChromaticNumber[GraphData["ChiuGraph"]]//Timing

<<IGraphM`

IGMinimumEdgeColoring[GraphData["ChiuGraph"]]//Max//Timing

FractionalChromaticNumber

GraphData["ChiuGraph","FractionalChromaticNumber"]

FractionalChromaticNumber[GraphData["ChiuGraph"],Method->"Static",Debug->True]//Timing

FractionalChromaticNumber[GraphData["ChiuGraph"],Method->"Dynamic",Debug->True]//Timing

UnitDistance

GraphData["ChiuGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["ChiuGraph"],Debug->True]

Construction

https://page.math.tu-berlin.de/~steiner/EuroCG_2021_paper_42.pdf

Coloring Circle Arrangements: New 4-Chromatic Planar Graphs
Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher, Felix Schröder, Raphael Steiner, and Birgit Vogtenhuber

This disproves the conjecture of Gimbel, Kündgen, Li and Thomassen (2019) that every 4-chromatic planar graph has fractional chromatic number strictly greater than 3.

e[l__]:=Sequence@@Partition[{l},2,1]

v={{259.5182291666667`,288.60644531250006`},{215.57969835069446`,271.6082899305556`},{173.56363932291669`,289.3898654513889`},{295.73079427083337`,352.07378472222223`},{216.83`,327.17`},{137.61393229166669`,352.33148871527777`},{58.52457682291667`,219.3768446180556`},{133.02164713541669`,218.40787760416669`},{167.83745659722223`,190.9108615451389`},{265.81136067708337`,190.42637803819446`},{297.6944986979167`,219.95925564236114`},{370.1608615451389`,216.4699435763889`},{308.90462239583337`,164.2951931423612`},{255.126953125`,146.3435329861112`},{173.22347005208337`,146.45176866319446`},{118.63145616319444`,162.50672743055566`},{293.3908420138889`,83.57199435763891`},{137.26860894097223`,86.17480468750011`}};

g=ScaleGraph[Graph[Range[Length[v]],Sort[Sort/@UndirectedEdge@@@{e[18,17,12,4,6,7,18,15,14,13,11,1,5,3,8,16,15,9,8,7,16,18],e[6,3,2,1,4,5,6],e[9,10,2,9],e[13,17,14,10,11,12,13]}],VertexCoordinates->v,VertexLabels->Automatic]]

RecognizeGraph[g]

VertexCount[g]

VertexDegree[g]//Union

PlanarGraphQ[g]

ChromaticNumber[g]

FractionalChromaticNumber[g]

Length[hc=FindHamiltonianCycle[g,All][[All,All,1]]]//Timing

Tally[(lcf=LCF[g,All])[[All,-1]]]

LCFGraph@@@Take[lcf,2]

GraphData

GraphDataClassString

GraphDataClassString["ChiuGraph"]

GraphDataString

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

WriteString[file,GraphDataString[
g,
"StandardName"->"ChiuGraph",
"Name"->"Chiu Graph"
]]