Box Graph

Author

Eric W. Weisstein
May 13, 2026

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

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

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

Figure

emb=GraphData["BoxGraph","Graph","All"]//StyleGraphs

GraphicsGrid[Partition[Join[Take[emb,5],emb[[{-5,-3}]]],UpTo[4]],Dividers->All]

Embeddings

<<MathWorld`Graphs`

Names

GraphData["BoxGraph","StandardName"]

GraphData["BoxGraph","StandardNames"]

HouseOfGraphs

hogid=GraphData[{"Cage",{3,13}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Cage",{3,13}},"WikidataID"]

GraphData[{"Cage",{3,13}},"WikidataID","URL"]

Robertson et al. 2019 (curved edge)

v={{0,2},{1,2},{2,2},{3,2},{5,2},{1,1},{3,1},{4,1},{5,1},{0,0},{1,0},{2,0},{3,0},{5,0}};
g=CurvedEdgeAnnotate[
Graph[Range[Length[v]],UndirectedEdge@@@Sort[{{10,11},{11,12},{12,13},{13,14},{9,14},{5,9},{1,2},{2,3},{3,4},{4,5},{1,10},{6,11},{2,6},{3,12},{7,13},{4,7},{7,8},{8,9},{1,5},{10,14},{6,8}}],VertexCoordinates->v,VertexLabels->"Name"],
{{{6,8},1/2,1/2},{{1,5},1/2,1},{{10,14},1/2,-1}}
]

CubicGraphQ[g]

RecognizeGraph[g]

Primary

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

All

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

CurvedEdge

GraphData["BoxGraph","Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["BoxGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

Bilateral

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

Circular

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

Planar

GraphData["BoxGraph","Planar"]

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

MinimalCrossing

GraphData["BoxGraph","CN"]

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

MinimalCrossing construction

(cn=CrossingNumber[GraphData["BoxGraph"],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData["BoxGraph"],TimeConstraint->60]//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["BoxGraph"],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

g=RotateGraph[MinimalCrossingGraph[GraphData["BoxGraph"],"CrossingNumber"->cn]]

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData["BoxGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,500}],Max[OuterFace[#]]<=GraphData["BoxGraph","V"]&]]//Timing

GraphEmbedding[g0=]

g=Annotate[g0,VertexCoordinates->({#/2,#2}&@@@GraphEmbedding[g0])]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["BoxGraph","Circulant"]

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

Halin

GraphData["BoxGraph","Halin"]

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

LCF

GraphData["BoxGraph","LCF"]

GraphData["BoxGraph","HamiltonianCycleCount"]

GraphData["BoxGraph","LCFSignature"]

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

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

LCF compute

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

Tally[(lcf=LCF[GraphData["BoxGraph"],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["BoxGraph","UnitDistance"]

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

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

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["BoxGraph","VertexList"],GraphData["BoxGraph","EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData["BoxGraph","Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData["BoxGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData["BoxGraph"],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{"BoxGraph",l=FindSubgraphUnitDistanceEmbedding[GraphData["BoxGraph"],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

RotateGraph[,{321,387}]

g=IndexGraph@

Matchstick

GraphData["BoxGraph","Matchstick"]

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

3D default

Graph3D[GraphData["BoxGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["BoxGraph","Polyhedral"]

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

Construction

MinimalRectilinearCrossing

pg=MinimalCrossingGraph[box,"CrossingNumber"->2]

VertexDelete[pg,{15,16}]

GraphPlot[SetProperty[box,VertexLabels->None]]

v={{0,0},{2,0},{2,1/2},{2,1},{0,1},{1/2,1/4},{1/2,1/2},{1/2,3/4},{1,1/4},{1,3/4},{3/2,1/4},{3/2,3/8},{3/2,3/4},{5/4,1/2}};
g=Graph[Range[Length[v]],UndirectedEdge@@@Sort[{Sequence@@Partition[Range[5],2,1,1],{1,6},{6,9},{9,11},{11,12},{12,13},{10,13},{8,10},{6,7},{7,8},{2,11},{4,13},{5,8},{9,10},{7,14},{3,14},{12,14}}],VertexCoordinates->v,VertexLabels->"Name"
]

r=RecognizeGraph@g

IsomorphicGraphQ[g,box]

RectilinearCrossingCount@g

Graph

ToCommonEdges[g,GraphData[r]]

UnitDistance

(nsoln=NSolve[{
(c-1/2)^2+d^2==1,
(x-1/2)^2+y^2==1,
(i-c)^2+(d-j)^2==1,
(x+i)^2+(y-j)^2==1,
(c-1/2)^2+(d-f)^2==1,
(x-a)^2+(y-b)^2==1,
(a-1/2)^2+(f-b)^2==1,
(i-1/2)^2+(j-h)^2==1,
(a-1/2)^2+(b-h)^2==1,
d==1},{h,x,y,a,b,c,d,f,i,j},Reals])//Timing

gs=DeleteDuplicatesBy[Select[Graph[Range[14],UndirectedEdge@@@{{1,2},{1,3},{1,9},{2,4},{2,10},{3,5},{3,7},{4,6},{4,8},{5,6},{5,11},{6,12},{7,10},{7,13},{8,9},{8,14},{9,11},{10,12},{11,13},{12,14},{13,14}},VertexCoordinates->({{-1/2,h},{1/2,h},{-a,b},{a,b},{-1/2,f},{1/2,f},{-x,y},{x,y},{-i,j},{i,j},{-c,d},{c,d},{-1/2,0},{1/2,0}}/.#),VertexLabels->"Name"]&/@nsoln,UnitDistanceGraphEmbeddingQ],Sort[Round[10^4GraphEmbedding[#]]]&]

RecognizeGraph/@gs//Union

(soln=Solve[{
(c-1/2)^2+d^2==1,
(x-1/2)^2+y^2==1,
(i-c)^2+(d-j)^2==1,
(x+i)^2+(y-j)^2==1,
(c-1/2)^2+(d-f)^2==1,
(x-a)^2+(y-b)^2==1,
(a-1/2)^2+(f-b)^2==1,
(i-1/2)^2+(j-h)^2==1,
(a-1/2)^2+(b-h)^2==1,
d==1},{h,x,y,a,b,c,d,f,i,j},Reals])//Timing

gs=Select[Graph[Range[14],UndirectedEdge@@@{{1,2},{1,3},{1,9},{2,4},{2,10},{3,5},{3,7},{4,6},{4,8},{5,6},{5,11},{6,12},{7,10},{7,13},{8,9},{8,14},{9,11},{10,12},{11,13},{12,14},{13,14}},VertexCoordinates->({{-1/2,h},{1/2,h},{-a,b},{a,b},{-1/2,f},{1/2,f},{-x,y},{x,y},{-i,j},{i,j},{-c,d},{c,d},{-1/2,0},{1/2,0}}/.#),VertexLabels->"Name"]&/@soln,UnitDistanceGraphEmbeddingQ]

RecognizeGraph/@gs

nsoln=NSolve[{
(c-1/2)^2+d^2==1,
(x-1/2)^2+y^2==1,
(i-c)^2+(d-j)^2==1,
(x+i)^2+(y-j)^2==1,
(c-1/2)^2+(d-f)^2==1,
(x-a)^2+(y-b)^2==1,
(a-1/2)^2+(f-b)^2==1,
(i-1/2)^2+(j-h)^2==1,
(a-1/2)^2+(b-h)^2==1},{h,x,y,a,b,c,d,f,i,j},Reals]

Do[
soln=NSolve[{
(c-1/2)^2+d^2==1,
(x-1/2)^2+y^2==1,
(i-c)^2+(d-j)^2==1,
(x+i)^2+(y-j)^2==1,
(c-1/2)^2+(d-f)^2==1,
(x-a)^2+(y-b)^2==1,
(a-1/2)^2+(f-b)^2==1,
(i-1/2)^2+(j-h)^2==1,
(a-1/2)^2+(b-h)^2==1},{h,x,y,a,b,c,f,i,j},Reals];
gs=Graph[Range[14],UndirectedEdge@@@{{1,2},{1,3},{1,9},{2,4},{2,10},{3,5},{3,7},{4,6},{4,8},{5,6},{5,11},{6,12},{7,10},{7,13},{8,9},{8,14},{9,11},{10,12},{11,13},{12,14},{13,14}},VertexCoordinates->({{-1/2,h},{1/2,h},{-a,b},{a,b},{-1/2,f},{1/2,f},{-x,y},{x,y},{-i,j},{i,j},{-c,d},{c,d},{-1/2,0},{1/2,0}}/.#),VertexLabels->"Name"]&/@soln;
Print[d->DeleteDuplicatesBy[Select[gs,UnitDistanceGraphEmbeddingQ],Sort[Round[10^8GraphEmbedding[#]]]&]],
{d,-1,1,.1}]

gs={,,,,,};