Robertson Diamond Graph

Author

Eric W. Weisstein
July 26, 2026

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

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

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

Figure

GraphicsGrid[
Partition[
StyleGraphs[
GraphData["RobertsonDiamondGraph","Graph","All"]
],
UpTo[6]
],
Dividers->All
]

Embeddings

<<MathWorld`Graphs`

Names

GraphData["RobertsonDiamondGraph","StandardName"]

GraphData["RobertsonDiamondGraph","StandardNames"]

Robertson et al. 2019 construction

v[[13]]-v[[9]]

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

CubicGraphQ[g]

RecognizeGraph[g]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["RobertsonDiamondGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData["RobertsonDiamondGraph","Configuration"]

GraphData["RobertsonDiamondGraph","Graph","Configuration"]//StyleGraphs

Perspective

GraphData["RobertsonDiamondGraph","Graph","Perspective"]//StyleGraphs

HoneycombToroidal construction

GraphData["RobertsonDiamondGraph","NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData["RobertsonDiamondGraph","Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData["RobertsonDiamondGraph","Graph","IGraph"]//StyleGraphs

Bilateral

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

Circular

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

Planar

GraphData["RobertsonDiamondGraph","Planar"]

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

MinimalLocalCrossing

GraphData["RobertsonDiamondGraph","LocalCrossingNumber"]

GraphData["RobertsonDiamondGraph","Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalLocalCrossing construction

GraphPlot@

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

RecognizeGraph@g

LocalCrossingCount@g

MinimalCrossing

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

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

MinimalCrossing construction

(cn=CrossingNumber[GraphData["RobertsonDiamondGraph"],TimeConstraint->1])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData["RobertsonDiamondGraph"],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["RobertsonDiamondGraph"],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["RobertsonDiamondGraph"],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["RobertsonDiamondGraph"],TimeConstraint->86400])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData["RobertsonDiamondGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["RobertsonDiamondGraph","Circulant"]

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

Complement graph

compl=GraphData["RobertsonDiamondGraph","ComplementGraph","Name"]

Line graph

GraphData["RobertsonDiamondGraph","Line"]

LineGraphQ[GraphData["RobertsonDiamondGraph"]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== "RobertsonDiamondGraph"&]

RootGraph[GraphData["RobertsonDiamondGraph"]]

RecognizeGraph[%]

Halin

GraphData["RobertsonDiamondGraph","Halin"]

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

Rigid

GraphData["RobertsonDiamondGraph","Rigid"]

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

Flexible

GraphData["RobertsonDiamondGraph","Flexible"]

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

LCF

GraphData["RobertsonDiamondGraph","LCF"]

GraphData["RobertsonDiamondGraph","HamiltonianCycleCount"]

GraphData["RobertsonDiamondGraph","LCFSignature"]

GraphData["RobertsonDiamondGraph","LCFNotations"]

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

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

LCF compute all

Divisors[GraphData["RobertsonDiamondGraph","V"]]

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

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

lcf

LCFGraph@@@lcf//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData["RobertsonDiamondGraph","UnitDistance"]

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

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

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

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

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

UnitDistance exact construction

GraphData["RobertsonDiamondGraph","Graphics"]

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

soln=NSolve[{
(*1*)(x-1/2)^2+(y-h)^2==1,
(*2*)(a-1/2)^2+(b-h)^2==1,
(*3*)(x-c)^2+(y-d)^2==1,
(*4*)(a+1-c)^2+(b-d)^2==1,
(*5*)(c-1/2)^2+(z-d)^2==1,
(*6*)(e+x)^2+(f-y)^2==1,
(*7*)(e-g)^2+(f-h)^2==1,
(*8*)(g-1/2)^2+(z-h)^2==1,
(*9*)(g-1/2)^2+h^2==1,
(*10*)(a-1/2)^2+b^2==1,
(*11*)(a+1-e)^2+(f-b)^2==1},{h,x,y,z,a,b,c,d,e,f,g,h},Reals]

gs=Graph[Range[18],UndirectedEdge@@@{{1,2},{1,3},{1,8},{2,4},{2,9},{3,5},{3,14},{4,6},{4,11},{5,7},{5,12},{6,10},{6,13},{7,8},{7,11},{8,16},{9,10},{9,17},{10,14},{11,15},{12,13},{12,15},{13,18},{14,18},{15,16},{16,17},{17,18}},VertexCoordinates->({{-1/2,h},{1/2,h},{-x,y},{x,y},{-c,d},{c,d},{-a-1,b},{-a,b},{a,b},{a+1,b},{-e,f},{-1/2,z},{1/2,z},{e,f},{-g,h},{-1/2,0},{1/2,0},{g,h}}/.#),VertexLabels->"Name"]&/@soln

Select[gs,UnitDistanceGraphEmbeddingQ[#]&&!DegenerateEmbeddingQ[#]&]

RecognizeGraph@gs[[1]]

EdgeLengths@gs[[1]]

soln=NSolve[{
(*1*)(x-1/2)^2+(y-h)^2==1,
(*2*)(a-1/2)^2+(b-h)^2==1,
(*3*)(x-c)^2+(y-d)^2==1,
(*4*)(c-i)^2+(d-j)^2==1,
(*5*)(c-1/2)^2+(z-d)^2==1,
(*6*)(e+x)^2+(f-y)^2==1,
(*7*)(e-g)^2+(f-h)^2==1,
(*8*)(g-1/2)^2+(z-h)^2==1,
(*9*)(g-1/2)^2+h^2==1,
(*10*)(a-1/2)^2+b^2==1,
(*11*)(e-i)^2+(f-j)^2==1,
(*12*)(a-i)^2+(b-j)^2==1,
i==a+9/10
},{h,i,j,x,y,z,a,b,c,d,e,f,g,h},Reals]

Length[soln]

gs=Graph[Range[18],UndirectedEdge@@@{{1,2},{1,3},{1,8},{2,4},{2,9},{3,5},{3,14},{4,6},{4,11},{5,7},{5,12},{6,10},{6,13},{7,8},{7,11},{8,16},{9,10},{9,17},{10,14},{11,15},{12,13},{12,15},{13,18},{14,18},{15,16},{16,17},{17,18}},VertexCoordinates->({{-1/2,h},{1/2,h},{-x,y},{x,y},{-c,d},{c,d},{-a-1,b},{-a,b},{a,b},{a+1,b},{-e,f},{-1/2,z},{1/2,z},{e,f},{-g,h},{-1/2,0},{1/2,0},{g,h}}/.#),VertexLabels->"Name"]&/@soln;

Take[gs,10]

soln=NSolve[{
(*1*)(x-1/2)^2+(y-h)^2==1,
(*2*)(a-1/2)^2+(b-h)^2==1,
(*3*)(x-c)^2+(y-d)^2==1,
(*4*)(c-i)^2+(d-j)^2==1,
(*5*)(c-1/2)^2+(z-d)^2==1,
(*6*)(e+x)^2+(f-y)^2==1,
(*7*)(e-g)^2+(f-h)^2==1,
(*8*)(g-1/2)^2+(z-h)^2==1,
(*9*)(g-1/2)^2+h^2==1,
(*10*)(a-1/2)^2+b^2==1,
(*11*)(e-i)^2+(f-j)^2==1,
(*12*)(a-i)^2+(b-j)^2==1,
j==b+1/10
},{h,i,j,x,y,z,a,b,c,d,e,f,g,h},Reals]

Length[soln]

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

Select[gs,UnitDistanceGraphEmbeddingQ[#]&&!DegenerateEmbeddingQ[#]&]

Length[soln=NSolve[{
(*1*)(x-1/2)^2+(y-h)^2==1,
(*2*)(a-1/2)^2+(b-h)^2==1,
(*3*)(x-c)^2+(y-d)^2==1,
(*4*)(c-i)^2+(d-j)^2==1,
(*5*)(c-1/2)^2+(z-d)^2==1,
(*6*)(e+x)^2+(f-y)^2==1,
(*7*)(e-g)^2+(f-h)^2==1,
(*8*)(g-1/2)^2+(z-h)^2==1,
(*9*)(g-1/2)^2+h^2==1,
(*10*)(a-1/2)^2+b^2==1,
(*11*)(e-i)^2+(f-j)^2==1,
(*12*)(a-i)^2+(b-j)^2==1,
j==b+2/10
},{h,i,j,x,y,z,a,b,c,d,e,f,g,h},Reals]]//Timing

Length[soln]

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

Select[gs,UnitDistanceGraphEmbeddingQ[#]&&!DegenerateEmbeddingQ[#]&]

gs={,,,};

RecognizeGraph/@gs

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

gs={,,,,,,,,,,,,,,,,}

Matchstick

GraphData["RobertsonDiamondGraph","Matchstick"]

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

3D default

Graph3D[GraphData["RobertsonDiamondGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["RobertsonDiamondGraph","Polyhedral"]

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

GraphData

GraphDataString

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

WriteString[file,GraphDataString[g,
"StandardName"->"RobertsonDiamondGraph",
"Name"->"Robertson diamond graph",
TimeConstraint->10,
Debug->True,
"Skip"->{"Arboricity"}
]]

Close[file]