Moore Graph

Author

Eric W. Weisstein
June 9, 2022

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

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

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

Enumeration

(v,3) Cages

Excess/@(CompleteGraph[#+1]&/@Range[3,10])

(v,4) Cages

Excess/@(CompleteGraph[#,#]&/@Range[3,10])

Cages

(p=Position[Excess/@CageGraphs,0,{1}]//Flatten)//Timing

MooreGraphs=Sort[CageGraphs[[p]],V[#1]≤V[#2]&];

Length/@Split[V/@MooreGraphs]

DownValues[CageGraph][[p]]//ColumnForm

labels={{"(Subscript[K, 4])"},{"(Subscript[K, 5])"},{"(Subscript[K, 3, 3])","(Subscript[K, 6])"},{"(Subscript[K, 7])"},{"(Subscript[K, 4, 4])","(Subscript[K, 8])"},{"(Subscript[K, 9])"},{P,"(Subscript[K, 5, 5])","(Subscript[K, 10])"},{(Subscript[K, 11])}}

Show[GraphicsArray[
MapIndexed[ShowGraph[#1,AspectRatio->Automatic,DisplayFunction->Identity,
PlotLabel->TraditionalForm[labels[[Sequence@@#2]]],
VertexStyle->Disk[.07]]&,
Take[Split[MooreGraphs,V[#1]==V[#2]&],8],
{2}
]]]

l=Sort[V/@CageGraphs[[p]]]

Length/@Split[l]

ShowGraphArray[Partition[Sort[CageGraphs,V[#1]≤V[#2]&],5,5,{1,1},{}]]

Checks

ExcessGD[graph_]:=Module[{g=GraphData[graph,"Girth"],deg=GraphData[graph,"Degrees"],nu},
If[!Equal@@deg,Return[$Failed]];
nu=deg[[1]];
Switch[Mod[g,2],
0,1+(((nu-1))^(g/2-1))+nu Sum[(((nu-1))^r),{r,0,(g-4)/2}],
1,1+nu Sum[(((nu-1))^r),{r,0,(g-3)/2}]
]
]

l={#,ExcessGD[#],GraphData[#,"V"]}&/@GraphData["Cage"]

l2={#[[1]],{0,Equal@@Rest[#]}}&/@l

moore=Select[l,Equal@@Rest[#]&][[All,1]];

Complements[x_]:=Complement@@@{#,Reverse[#]}&[x]

Complements[{moore,GraphData["Moore"]}]

moore=Cases[l,{_,x_,x_}][[All,1]]

Select[moore,GraphData[#,"Moore"]=!=True&]

GraphData["Moore"]

nonmoore=DeleteCases[l,{_,x_,x_}][[All,1]]

Select[nonmoore,GraphData[#,"Moore"]=!=False&]

GraphData["WongGraph","Moore"]

Coloring-related) Moore graph from Wagon's Mathematica in Action

GraphData["*Moore*"]

ColorGraph[g_Graph,opts___?OptionQ]:=Module[{col=FindVertexColoring[g],cols={Red,Green,Yellow,Green,Blue}},
Annotate[g,{EdgeStyle->Directive[Gray],VertexStyle->MapIndexed[#2[[1]]->cols[[#]]&,col],opts}]
]

"MoorePartialGraph"

From Stan Wagon's
Mathematica in Action, 2nd ed.

MooreGraphPartial is a partial version of the Moore graph. Some edges are missing, but it still serves as an excellent test for 4-coloring, and is easier to draw

GraphData

GraphData["MoorePartialGraph","V"]

GraphData["MoorePartialGraph"]//StyleGraphs[#,VertexSize->{"Scaled",.012},EdgeStyle->Directive[Gray]]&

GraphData["MoorePartialGraph","ChromaticNumber"]

(col=FindVertexColoring[GraphData["MoorePartialGraph"]])//Timing

Max[col]

ColorGraph[GraphData["MoorePartialGraph"],VertexSize->{"Scaled",.01}]

Construction

MooreGraphPartial=PlanarGraph[First[FromAdjacencyLists[{{2,3,6,340},{1,4,6,55,56,57,340},{1,5,6},{2,11,12,56,57,58,64},{3,6,7,8},{1,2,3,5,8,9,55},{5,8,13,31},{5,6,7,9,13,14,25},{6,8,10,14,15,32,55},{9,11,15,16,26,55,56},{4,10,12,16,17,33,56},{4,11,17,18,27,58,68},{7,8,19,25,31},{8,9,20,25,32},{9,10,21,26,32},{10,11,22,26,33},{11,12,23,27,33},{12,24,27,68,92},{13,25,31,34,37},{14,25,32,35,40},{15,26,32,35,38},{16,26,33,36,41},{17,27,33,36,39},{18,27,42,92,95},{8,13,14,19,20,37,40},{10,15,16,21,22,38,41},{12,17,18,23,24,39,42},{37,40,46,49,211},{38,41,47,50,212},{39,42,48,51,213},{7,13,19,34},{9,14,15,20,21,35},{11,16,17,22,23,36},{19,31,37,43},{20,21,32,38,40,44,59},{22,23,33,39,41,45,60},{19,25,28,34,40,43,46},{21,26,29,35,41,44,47},{23,27,30,36,42,45,48},{20,25,28,35,37,49,59},{22,26,29,36,38,50,60},{24,27,30,39,51,61,95},{34,37,46,52},{35,38,47,53,59},{36,39,48,54,60},{28,37,43,52,211,220,226},{29,38,44,53,212,221,227},{30,39,45,54,213,222,228},{28,40,53,59,211,223,233},{29,41,54,60,212,224,234},{30,42,61,113,213,225,235},{43,46,226},{44,47,49,59,227,233},{45,48,50,60,228,234},{2,6,9,10,56},{2,4,10,11,55},{2,4,62,64,340},{4,12,64,66,68},{35,40,44,49,53},{36,41,45,50,54},{42,51,95,104,113},{57,63,64,67,340},{62,65,67,116,117,118,340},{4,57,58,62,66,67},{63,72,73,117,118,119,125},{58,64,67,68,69},{62,63,64,66,69,70,116},{12,18,58,66,69,74,92},{66,67,68,70,74,75,86},{67,69,71,75,76,93,116},{70,72,76,77,87,116,117},{65,71,73,77,78,94,117},{65,72,78,79,88,119,129},{68,69,80,86,92},{69,70,81,86,93},{70,71,82,87,93},{71,72,83,87,94},{72,73,84,88,94},{73,85,88,129,153},{74,86,92,95,98},{75,86,93,96,101},{76,87,93,96,99},{77,87,94,97,102},{78,88,94,97,100},{79,88,103,153,156},{69,74,75,80,81,98,101},{71,76,77,82,83,99,102},{73,78,79,84,85,100,103},{98,101,107,110,263},{99,102,108,111,264},{100,103,109,112,265},{18,24,68,74,80,95},{70,75,76,81,82,96},{72,77,78,83,84,97},{24,42,61,80,92,98,104},{81,82,93,99,101,105,120},{83,84,94,100,102,106,121},{80,86,89,95,101,104,107},{82,87,90,96,102,105,108},{84,88,91,97,103,106,109},{81,86,89,96,98,110,120},{83,87,90,97,99,111,121},{85,88,91,100,112,122,156},{61,95,98,107,113},{96,99,108,114,120},{97,100,109,115,121},{89,98,104,113,263,272,278},{90,99,105,114,264,273,279},{91,100,106,115,265,274,280},{89,101,114,120,263,275,285},{90,102,115,121,264,276,286},{91,103,122,174,265,277,287},{51,61,104,107,235,278},{105,108,110,120,279,285},{106,109,111,121,280,286},{63,67,70,71,117},{63,65,71,72,116},{63,65,123,125,340},{65,73,125,127,129},{96,101,105,110,114},{97,102,106,111,115},{103,112,156,165,174},{118,124,125,128,340},{123,126,128,177,178,179,340},{65,118,119,123,127,128},{124,133,134,178,179,180},{119,125,128,129,130},{123,124,125,127,130,131,177},{73,79,119,127,130,135,153},{127,128,129,131,135,136,147},{128,130,132,136,137,154,177},{131,133,137,138,148,177,178},{126,132,134,138,139,155,178},{126,133,139,140,149,180},{129,130,141,147,153},{130,131,142,147,154},{131,132,143,148,154},{132,133,144,148,155},{133,134,145,149,155},{134,146,149},{135,147,153,156,159},{136,147,154,157,162},{137,148,154,157,160},{138,148,155,158,163},{139,149,155,158,161},{140,149,164},{130,135,136,141,142,159,162},{132,137,138,143,144,160,163},{134,139,140,145,146,161,164},{159,162,168,171,315},{160,163,169,172,316},{161,164,170,173,317},{79,85,129,135,141,156},{131,136,137,142,143,157},{133,138,139,144,145,158},{85,103,122,141,153,159,165},{142,143,154,160,162,166,181},{144,145,155,161,163,167,182},{141,147,150,156,162,165,168},{143,148,151,157,163,166,169},{145,149,152,158,164,167,170},{142,147,150,157,159,171,181},{144,148,151,158,160,172,182},{146,149,152,161,173,183},{122,156,159,168,174},{157,160,169,175,181},{158,161,170,176,182},{150,159,165,174,315,324,330},{151,160,166,175,316,325,331},{152,161,167,176,317,326,332},{150,162,175,181,315,327,337},{151,163,176,182,316,328,338},{152,164,183,317,329,339},{112,122,165,168,287,330},{166,169,171,181,331,337},{167,170,172,182,332,338},{124,128,131,132,178},{124,126,132,133,177},{124,126,340},{126,134},{157,162,166,171,175},{158,163,167,172,176},{164,173},{185,186,189,341},{184,187,189,229,230,231,341},{184,188,189},{185,194,195,230,231,232,238},{186,189,190,191},{184,185,186,188,191,192,229},{188,191,196,214},{188,189,190,192,196,197,208},{189,191,193,197,198,215,229},{192,194,198,199,209,229,230},{187,193,195,199,200,216,230},{187,194,200,201,210,232,242},{190,191,202,208,214},{191,192,203,208,215},{192,193,204,209,215},{193,194,205,209,216},{194,195,206,210,216},{195,207,210,242,266},{196,208,214,217,220},{197,208,215,218,223},{198,209,215,218,221},{199,209,216,219,224},{200,210,216,219,222},{201,210,225,266,269},{191,196,197,202,203,220,223},{193,198,199,204,205,221,224},{195,200,201,206,207,222,225},{28,46,49,220,223},{29,47,50,221,224},{30,48,51,222,225},{190,196,202,217},{192,197,198,203,204,218},{194,199,200,205,206,219},{202,214,220,226},{203,204,215,221,223,227,233},{205,206,216,222,224,228,234},{46,202,208,211,217,223,226},{47,204,209,212,218,224,227},{48,206,210,213,219,225,228},{49,203,208,211,218,220,233},{50,205,209,212,219,221,234},{51,207,210,213,222,235,269},{46,52,217,220},{47,53,218,221,233},{48,54,219,222,234},{185,189,192,193,230},{185,187,193,194,229},{185,187,236,238,341},{187,195,238,240,242},{49,53,218,223,227},{50,54,219,224,228},{51,113,225,269,278},{231,237,238,241,341},{236,239,241,281,282,283,341},{187,231,232,236,240,241},{237,246,247,282,283,284,290},{232,238,241,242,243},{236,237,238,240,243,244,281},{195,201,232,240,243,248,266},{240,241,242,244,248,249,260},{241,243,245,249,250,267,281},{244,246,250,251,261,281,282},{239,245,247,251,252,268,282},{239,246,252,253,262,284,294},{242,243,254,260,266},{243,244,255,260,267},{244,245,256,261,267},{245,246,257,261,268},{246,247,258,262,268},{247,259,262,294,318},{248,260,266,269,272},{249,260,267,270,275},{250,261,267,270,273},{251,261,268,271,276},{252,262,268,271,274},{253,262,277,318,321},{243,248,249,254,255,272,275},{245,250,251,256,257,273,276},{247,252,253,258,259,274,277},{89,107,110,272,275},{90,108,111,273,276},{91,109,112,274,277},{201,207,242,248,254,269},{244,249,250,255,256,270},{246,251,252,257,258,271},{207,225,235,254,266,272,278},{255,256,267,273,275,279,285},{257,258,268,274,276,280,286},{107,254,260,263,269,275,278},{108,256,261,264,270,276,279},{109,258,262,265,271,277,280},{110,255,260,263,270,272,285},{111,257,261,264,271,273,286},{112,259,262,265,274,287,321},{107,113,235,269,272},{108,114,270,273,285},{109,115,271,274,286},{237,241,244,245,282},{237,239,245,246,281},{237,239,288,290,341},{239,247,290,292,294},{110,114,270,275,279},{111,115,271,276,280},{112,174,277,321,330},{283,289,290,293,341},{288,291,293,333,334,335,341},{239,283,284,288,292,293},{289,298,299,334,335,336},{284,290,293,294,295},{288,289,290,292,295,296,333},{247,253,284,292,295,300,318},{292,293,294,296,300,301,312},{293,295,297,301,302,319,333},{296,298,302,303,313,333,334},{291,297,299,303,304,320,334},{291,298,304,305,314,336},{294,295,306,312,318},{295,296,307,312,319},{296,297,308,313,319},{297,298,309,313,320},{298,299,310,314,320},{299,311,314},{300,312,318,321,324},{301,312,319,322,327},{302,313,319,322,325},{303,313,320,323,328},{304,314,320,323,326},{305,314,329},{295,300,301,306,307,324,327},{297,302,303,308,309,325,328},{299,304,305,310,311,326,329},{150,168,171,324,327},{151,169,172,325,328},{152,170,173,326,329},{253,259,294,300,306,321},{296,301,302,307,308,322},{298,303,304,309,310,323},{259,277,287,306,318,324,330},{307,308,319,325,327,331,337},{309,310,320,326,328,332,338},{168,306,312,315,321,327,330},{169,308,313,316,322,328,331},{170,310,314,317,323,329,332},{171,307,312,315,322,324,337},{172,309,313,316,323,325,338},{173,311,314,317,326,339},{168,174,287,321,324},{169,175,322,325,337},{170,176,323,326,338},{289,293,296,297,334},{289,291,297,298,333},{289,291,341},{291,299},{171,175,322,327,331},{172,176,323,328,332},{173,329},{1,2,57,62,63,118,123,124,179},{184,185,231,236,237,283,288,289,335}}]],{{1,1},{6,2},{0,3},{9,3},{1,4},{2.5,3},{0,6},{2,6},{4,6},{6,6},{8,6},{10,6},{1,7},{3,7},{5,7},{7,7},{9,7},{11,7},{1,9},{3,9},{5,9},{7,9},{9,9},{11,9},{2,8.5},{6,8.5},{10,8.5},{2,13},{6,13},{10,13},{0,8},{4,8},{8,8},{0,10.5},{4,10.5},{8,10.5},{1.5,11},{5.5,11},{9.5,11},{2.5,11},{6.5,11},{10.5,11},{0.5,12},{4.5,12},{8.5,12},{1.25,14},{5.25,14},{9.25,14},{3,14},{7,14},{11,14},{0,14},{4,14},{8,14},{5,4},{7,4},{11,1},{11,4},{3.75,12},{7.75,12},{11.75,12},{13,1},{18,2},{12,3},{21,3},{13,4},{14.5,3},{12,6},{14,6},{16,6},{18,6},{20,6},{22,6},{13,7},{15,7},{17,7},{19,7},{21,7},{23,7},{13,9},{15,9},{17,9},{19,9},{21,9},{23,9},{14,8.5},{18,8.5},{22,8.5},{14,13},{18,13},{22,13},{12,8},{16,8},{20,8},{12,10.5},{16,10.5},{20,10.5},{13.5,11},{17.5,11},{21.5,11},{14.5,11},{18.5,11},{22.5,11},{12.5,12},{16.5,12},{20.5,12},{13.25,14},{17.25,14},{21.25,14},{15,14},{19,14},{23,14},{12,14},{16,14},{20,14},{17,4},{19,4},{23,1},{23,4},{15.75,12},{19.75,12},{23.75,12},{25,1},{30,2},{24,3},{33,3},{25,4},{26.5,3},{24,6},{26,6},{28,6},{30,6},{32,6},{34,6},{25,7},{27,7},{29,7},{31,7},{33,7},{35,7},{25,9},{27,9},{29,9},{31,9},{33,9},{35,9},{26,8.5},{30,8.5},{34,8.5},{26,13},{30,13},{34,13},{24,8},{28,8},{32,8},{24,10.5},{28,10.5},{32,10.5},{25.5,11},{29.5,11},{33.5,11},{26.5,11},{30.5,11},{34.5,11},{24.5,12},{28.5,12},{32.5,12},{25.25,14},{29.25,14},{33.25,14},{27,14},{31,14},{35,14},{24,14},{28,14},{32,14},{29,4},{31,4},{35,1},{35,4},{27.75,12},{31.75,12},{35.75,12},{1,27},{6,26},{0,25},{9,25},{1,24},{2.5,25},{0,22},{2,22},{4,22},{6,22},{8,22},{10,22},{1,21},{3,21},{5,21},{7,21},{9,21},{11,21},{1,19},{3,19},{5,19},{7,19},{9,19},{11,19},{2,19.5},{6,19.5},{10,19.5},{2,15},{6,15},{10,15},{0,20},{4,20},{8,20},{0,17.5},{4,17.5},{8,17.5},{1.5,17},{5.5,17},{9.5,17},{2.5,17},{6.5,17},{10.5,17},{0.5,16},{4.5,16},{8.5,16},{5,24},{7,24},{11,27},{11,24},{3.75,16},{7.75,16},{11.75,16},{13,27},{18,26},{12,25},{21,25},{13,24},{14.5,25},{12,22},{14,22},{16,22},{18,22},{20,22},{22,22},{13,21},{15,21},{17,21},{19,21},{21,21},{23,21},{13,19},{15,19},{17,19},{19,19},{21,19},{23,19},{14,19.5},{18,19.5},{22,19.5},{14,15},{18,15},{22,15},{12,20},{16,20},{20,20},{12,17.5},{16,17.5},{20,17.5},{13.5,17},{17.5,17},{21.5,17},{14.5,17},{18.5,17},{22.5,17},{12.5,16},{16.5,16},{20.5,16},{17,24},{19,24},{23,27},{23,24},{15.75,16},{19.75,16},{23.75,16},{25,27},{30,26},{24,25},{33,25},{25,24},{26.5,25},{24,22},{26,22},{28,22},{30,22},{32,22},{34,22},{25,21},{27,21},{29,21},{31,21},{33,21},{35,21},{25,19},{27,19},{29,19},{31,19},{33,19},{35,19},{26,19.5},{30,19.5},{34,19.5},{26,15},{30,15},{34,15},{24,20},{28,20},{32,20},{24,17.5},{28,17.5},{32,17.5},{25.5,17},{29.5,17},{33.5,17},{26.5,17},{30.5,17},{34.5,17},{24.5,16},{28.5,16},{32.5,16},{29,24},{31,24},{35,27},{35,24},{27.75,16},{31.75,16},{35.75,16},{18,-2},{18,30}}];

g1=MooreGraphPartial/.PlanarGraph[x_,y_]:>Graph[x,List/@y]

ShowGraph[g1,VertexStyle->Disk[.015],EdgeStyle->Thin]

GraphData

GraphDataString[g1,
"Name"->"Moore's partial graph",
"StandardName"->"MooresPartialGraph",
TimeConstraint->60,
Debug->True
]

"MooreGraph"

From Stan Wagon's
Mathematica in Action, 2nd ed.

MooreGraph is a 341-vertex graph due to E. F. Moore that is difficult to four-color by hand

MooreGraph is a 341-vertex planar graph that is a little resistant to 4-coloring.

GraphData

GraphData["MooreGraph","V"]

GraphData["MooreGraph"]//StyleGraphs[#,VertexSize->{"Scaled",.008},EdgeStyle->Directive[GrayLevel[.6]],ImageSize->Large]&

GraphData["MooreGraph","ChromaticNumber"]

(col=FindVertexColoring[GraphData["MooreGraph"]])//Timing

Max[col]

ColorGraph[GraphData["MooreGraph"],VertexSize->{"Scaled",.008},EdgeStyle->Directive[GrayLevel[.6]],ImageSize->Large]

Construction

MooreGraph=Module[{},th=-114. Degree;
rot={{Cos[th],-Sin[th]},{Sin[th],Cos[th]}};
rot1={{Cos[th],Sin[th]},{-Sin[th],Cos[th]}};
pts=MooreGraphPartial[[2]];
pts[[340]]={18,-26};
Scan[(pts=ReplacePart[pts,rot.((pts[[#]]/.{x_,y_}:>{0,y})-{0,7}-pts[[184]])+pts[[184]],#])&,{1,3,5,7,31,34,43,52,226,217,214,190,188,186,184}];
Scan[(pts=ReplacePart[pts,rot1.((pts[[#]]/.{x_,y_}:>{35,y})-{0,7}-pts[[335]])+pts[[335]],#])&,{179,126,180,134,140,146,164,183,173,339,329,311,305,299,336,291,335}];
pts[[341]]={18,29.5};
Scan[(pts=ReplacePart[pts,pts[[#]]/.{x_,y_}:>{1,y},#])&,{2,6,8,13,37,46,191,189,220}];
Scan[(pts=ReplacePart[pts,pts[[#]]/.{x_,y_}:>{34,y},#])&,{124,133,139,149,152,161,178,289,298,304,314,317,326,334}];
mooretemp=PlanarGraph@@AddEdges[Graph@@MooreGraphPartial,{{1,179},{3,179},{3,126},{3,180},{5,180},{7,134},{7,140},{7,180},{31,140},{31,146},{34,183},{34,146},{34,164},{43,183},{52,183},{52,173},{52,339},{226,339},{217,339},{217,329},{217,311},{214,311},{214,305},{190,305},{190,299},{190,336},{188,336},{186,336},{186,291},{186,335},{184,335}}];
pts[[185]]=pts[[185]]+{0,2};
pts[[289]]=pts[[289]]+{0,-1};
pts[[134]]=pts[[134]]+{1.2,0};
pts[[126]]=pts[[126]]+{0.7,0.2};
pts[[180]]=pts[[180]]+{-2,0};
pts[[173]]=pts[[173]]+{.2,-0.6};
pts[[329]]=pts[[329]]+{.2,-0.6};
pts[[183]]=pts[[183]]+{-2,0};
pts[[339]]=pts[[339]]+{-2,0};
pts[[291]]=pts[[291]]+{-3,-0.5};
pts[[336]]=pts[[336]]+{-6,0};
pts[[299]]=pts[[299]]+{-2,0};
pts[[2]]=pts[[2]]+{-.5,-1};
pts[[184]]=pts[[184]]+{1,0.2};
pts[[185]]=pts[[185]]+{2,-1};
pts[[236]]=pts[[236]]+{2,-0.2};
pts[[237]]=pts[[237]]+{0,-0.2};
pts[[231]]=pts[[231]]+{1.5,-0.2};
pts[[283]]=pts[[283]]+{-2,-0.2};
pts[[288]]=pts[[288]]+{-1.5,-0.2};
pts[[341]]=pts[[341]]+{0,-1};
pts[[184]]=pts[[184]]+{6,-0.8};
pts[[335]]=pts[[335]]+{-11,-0.5};
pts[[186]]=pts[[186]]+{3,-0.3};
pts[[185]]=pts[[185]]+{0,1.5};
pts[[289]]=pts[[289]]+{0,1.5};
pts[[124]]=pts[[124]]+{1.5,-1};
PlanarGraph[mooretemp[[1]],pts]];

g2=MooreGraph/.PlanarGraph[x_,y_]:>Graph[x,List/@y]

ShowGraph[g2,VertexStyle->Disk[.015],EdgeStyle->Thin]

GraphData

GraphDataString[g2,
"Name"->"Moore's graph",
"StandardName"->"MooresGraph",
TimeConstraint->60,
Debug->True
]

Embeddings

GraphData["MooreGraph","StandardName"]

All

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

Halin

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

LCF

GraphData["MooreGraph","LCFSignature"]

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

UnitDistance

GraphData["MooreGraph","UnitDistance"]

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

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

Matchstick

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

MinimalCrossing

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

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

Default embedding

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

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

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData["MooreGraph"]]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData["MooreGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

3D Canonical

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

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

3D Polyhedron construction

Graphics3D[{FaceForm[Green,Red],Opacity[.5],poly=GraphPolyhedron[GraphData["MooreGraph"],1],Yellow,Sphere[]}]

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->100,MaxIterations->1000,PrecisionGoal->20,"ProgressInterval"->100,"TangentFactor"->1/10,"PlanarFactor"->1/10,Debug->True])//Timing

(can=FindCanonicalPolyhedron[can,WorkingPrecision->100,MaxIterations->100000,PrecisionGoal->20,"ProgressInterval"->100,"TangentFactor"->1/10,"PlanarFactor"->1/10,Debug->True])//Timing

Graphics3D[can=Polyhedron[]]

(can=FindCanonicalPolyhedron[can,WorkingPrecision->50,MaxIterations->100000,PrecisionGoal->20,"ProgressInterval"->5000,"TangentFactor"->1/5,"PlanarFactor"->1/5,Debug->True])//Timing

(can=FindCanonicalPolyhedron[can,WorkingPrecision->50,MaxIterations->100000,PrecisionGoal->20,"ProgressInterval"->5000,"TangentFactor"->1/5,"PlanarFactor"->1/5,Debug->True])//Timing

(can=FindCanonicalPolyhedron[can,WorkingPrecision->50,MaxIterations->100000,PrecisionGoal->20,"ProgressInterval"->5000,"TangentFactor"->1/5,"PlanarFactor"->1/5,Debug->True])//Timing

(can=FindCanonicalPolyhedron[can,WorkingPrecision->50,MaxIterations->100000,PrecisionGoal->20,"ProgressInterval"->5000,"TangentFactor"->1/5,"PlanarFactor"->1/5,Debug->True])//Timing

SimplePolyhedronQ[can]

(can=FindCanonicalPolyhedron[can,WorkingPrecision->50,MaxIterations->100000,PrecisionGoal->20,"ProgressInterval"->5000,"TangentFactor"->1/5,"PlanarFactor"->1/5,Debug->True])//Timing

Graphics3D[can=Polyhedron[]]

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]

EmbeddingClasses3D[g]

RecognizeGraph[g]