Empire Problem

Author

Eric W. Weisstein
August 2, 2018

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

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

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

m=2

By Scott Kim via Ed Pegg, Aug 2 2018

A triangulated planar graph on 24 points.

TwopireEdges={{1,3},{1,10},{1,11},{1,12},{1,17},{1,18},{1,20},{2,3},{2,5},{2,6},{2,10},{2,19},{2,23},{2,24},{3,5},{3,12},{3,19},{3,20},{3,22},{4,5},{4,7},{4,8},{4,12},{4,13},{4,14},{4,21},{5,7},{5,21},{5,22},{5,23},{6,7},{6,9},{6,10},{6,15},{6,16},{6,24},{7,9},{7,13},{7,23},{7,24},{8,9},{8,11},{8,12},{8,14},{8,17},{8,18},{9,11},{9,13},{9,14},{9,15},{10,11},{10,16},{10,19},{10,20},{11,15},{11,16},{11,18},{12,17},{12,21},{12,22},{13,14},{15,16},{17,18},{19,20},{21,22},{23,24}};

{
g=System`Graph[Range[Max[Flatten[TwopireEdges]]],UndirectedEdge@@@TwopireEdges],
g2=System`Graph[Range[Max[Flatten[TwopireEdges]]],UndirectedEdge@@@TwopireEdges,GraphLayout->"PlanarEmbedding"],
g3=System`Graph[Range[Max[Flatten[TwopireEdges]]],UndirectedEdge@@@TwopireEdges,GraphLayout->"TutteEmbedding"],
g4=PlanarGraph[g]
}

{TriangulatedGraphQ[g],PlanarGraphQ[g]}

When points 1-12 are paired with 13-24 a 12-color 2-pire results.

Complement[Subsets[Range[12],{2}],Sort[Sort/@Mod[TwopireEdges,12,1]]]

gg=System`Graph[Range[Max[Flatten[TwopireEdges]]],UndirectedEdge@@@TwopireEdges,GraphLayout->"PlanarEmbedding",VertexLabels->"Name"]

faces=FindFace[gg]

https://www.jstor.org/stable/24966248?seq=1#page_scan_tab_contents

GraphData

GraphDataString

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

WriteString[file,GraphDataString[