Mančinska-Roberson Graphs

Author

Eric W. Weisstein
June 9, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/Mancinska-RobersonGraphs.nb.

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

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

Source

Mančinska, L. and Roberson, D. E. "Oddities of Quantum Colorings." Baltic Journal of Modern Computing 4, 846-859, 2016. https://doi.org/10.22364/bjmc.2016.4.4.16.

Figure

GraphicsRow[StyleGraphs[GraphData/@GraphData["MancinskaRobersonGraph*"]],Dividers->All,ImageSize->500]

Embeddings

<<MathWorld`Graphs`

"MancinskaRobersonGraph13"

Names

GraphData["MancinskaRobersonGraph13","StandardName"]

GraphData["MancinskaRobersonGraph13","StandardNames"]

HouseOfGraphs

hogid=GraphData["MancinskaRobersonGraph13","NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData["MancinskaRobersonGraph13","WikidataID"]

GraphData["MancinskaRobersonGraph13","WikidataID","URL"]

Primary

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

All

Quit

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

CurvedEdge

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

Inexact

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

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData["MancinskaRobersonGraph13","Graph","Degenerate"]//Column

Embeddings

GraphDataEmbeddings[GraphData["MancinskaRobersonGraph13"]]

Default embedding

g0=GraphPlot[Graph[GraphData["MancinskaRobersonGraph13","VertexList"],GraphData["MancinskaRobersonGraph13","Edges"]],GraphLayout->"HighDimensionalEmbedding"]

GraphPlot@RotateGraph[,Pi]

v=Join[CirclePoints[3],CirclePoints[{2/5,-Pi/2},9],{{0,0}}];
Graph[Range@Length@v,{},VertexCoordinates->v]

g=FindCorrespondingGraph[,v]//Quiet

RecognizeGraph[g]

Configuration

GraphData["MancinskaRobersonGraph13","Configuration"]

configurations=GraphData["MancinskaRobersonGraph13","Graph","Configuration"]//StyleGraphs

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData["MancinskaRobersonGraph13","Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData["MancinskaRobersonGraph13","Bipartite"]

GraphData["MancinskaRobersonGraph13","Graph","Bipartite"]//StyleGraphs

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData["MancinskaRobersonGraph13","Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]//Quiet

Circular

GraphData["MancinskaRobersonGraph13","Graph","Circular"]

Circular construction All

GraphData["MancinskaRobersonGraph13","Hamiltonian"]

GraphData["MancinskaRobersonGraph13","HamiltonianCycles"]

GraphData["MancinskaRobersonGraph13","HamiltonianCycleCount"]

GraphData["MancinskaRobersonGraph13","LCF"]

GraphData["MancinskaRobersonGraph13","LCFSignature"]

Length[hc=FindHamiltonianCycle[GraphData["MancinskaRobersonGraph13"],All][[All,All,1]]]//Timing

g=CircularEmbeddingFromHamiltonianCycle[GraphData["MancinskaRobersonGraph13"],hc[[1]]]

Length[hcsym=SymmetricHamiltonianCycles[GraphData["MancinskaRobersonGraph13"],hc,ProgressReporting->True]]//Timing

GroupBy[SymmetricHamiltonianCycleGraph[GraphData["MancinskaRobersonGraph13"],#]&/@hcsym,GraphSymmetryGroup]

Planar

GraphData["MancinskaRobersonGraph13","Planar"]

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

MinimalCrossingNumber crossings.uos.de [verified 5]

CrossingNumber[GraphData["MancinskaRobersonGraph13"],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData["MancinskaRobersonGraph13","CN"]

(gs=GraphData["MancinskaRobersonGraph13","Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData["MancinskaRobersonGraph13","RCN"]

GraphData["MancinskaRobersonGraph13","Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Tutte

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

TutteGraphs=BilateralGraph[CenterGraph@IGLayoutTutte[g,"OuterFace"->#],"ReturnNonbilateralGraph"->True]&/@faces

TutteGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["MancinskaRobersonGraph13","V"]])]
}&/@TutteGraphs;

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

LocalCrossingNumberWithEmbeddings=
{1+Max[Length/@DeleteCases[
Drop[AdjacencyList[#],GraphData["MancinskaRobersonGraph13","V"]],
_Integer?(LessEqualThan[GraphData["MancinskaRobersonGraph13","V"]]),
{2}
]],#}&/@TutteGraphs

TutteGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData["MancinskaRobersonGraph13","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@TutteGraphs;

SymmetricEmbeddingsWithOrientations=DeleteCases[
TutteGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]

Select[SymmetricEmbeddingsWithOrientations[[All,1]],Count[OuterFace[#],_?(GreaterThan[GraphData["MancinskaRobersonGraph13","V"]])]==0&]

MinimalCrossing construction Random 1k [124 s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["MancinskaRobersonGraph13"],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [702 s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["MancinskaRobersonGraph13"],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

diagrams0

g=;

RecognizeGraph@g

GraphCrossingCount@g

GraphCrossingDiagram@g

GraphPlot@With[{g=},Graph[VertexList[g],EdgeList[g],VertexCoordinates->GraphEmbedding[g]]]

g=GraphicsToGraph[]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

diagrams1

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [2736 s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["MancinskaRobersonGraph13"],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 1k [old]

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

(RandomGraphs=Table[MinimalCrossingGraph[GraphData["MancinskaRobersonGraph13"],"CrossingNumber"->cn,RandomSeed->n],{n,1000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["MancinskaRobersonGraph13","V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData["MancinskaRobersonGraph13","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalCrossing construction Random 20k [old]

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

(RandomGraphs=Table[MinimalCrossingGraph[GraphData["MancinskaRobersonGraph13"],"CrossingNumber"->cn,RandomSeed->n],{n,20000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["MancinskaRobersonGraph13","V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData["MancinskaRobersonGraph13","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalLocalCrossing

GraphData["MancinskaRobersonGraph13",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData["MancinskaRobersonGraph13",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["MancinskaRobersonGraph13","Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction 1000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData["MancinskaRobersonGraph13"],"CrossingNumber"->cn,RandomSeed->i],{i,1000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

MinimaRectilinearlLocalCrossing construction 20000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData["MancinskaRobersonGraph13"],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Circulant

GraphData["MancinskaRobersonGraph13","Circulant"]

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

Circulant construction

GraphData["MancinskaRobersonGraph13","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["MancinskaRobersonGraph13"]])//AbsoluteTiming

CirculantGraph1@@@ci

Cases[GraphData["MancinskaRobersonGraph13","StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData["MancinskaRobersonGraph13","Line"]

LineGraphQ[GraphData["MancinskaRobersonGraph13"]]//Timing

RootGraph

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

RootGraph[GraphData["MancinskaRobersonGraph13"]]

Halin

GraphData["MancinskaRobersonGraph13","Halin"]

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

Rigid

GraphData["MancinskaRobersonGraph13","Rigid"]

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

Flexible

GraphData["MancinskaRobersonGraph13","Flexible"]

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

Voltage

GraphData["MancinskaRobersonGraph13","Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData["MancinskaRobersonGraph13"],"MaxResults"->20,Debug->True]

Length[gs]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF

GraphData["MancinskaRobersonGraph13","LCF"]

GraphData["MancinskaRobersonGraph13","HamiltonianCycleCount"]

GraphData["MancinskaRobersonGraph13","LCFSignature"]

GraphData["MancinskaRobersonGraph13","LCFNotations"]

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

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

UnitDistance

GraphData["MancinskaRobersonGraph13","UnitDistance"]

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData["MancinskaRobersonGraph13","EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData["MancinskaRobersonGraph13","VertexList"],GraphData["MancinskaRobersonGraph13","EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

gs=UnitDistanceEmbeddingRefine[Graph[VertexList[#],EdgeList[#],VertexCoordinates->GraphEmbedding[#]],MaxIterations->500]&/@Complement@@(GraphData["MancinskaRobersonGraph13","Graph",#]&/@{"All","UnitDistance"})

TextGrid[
gdata=SortBy[
{#,DegenerateGraphEmbeddingQ[#],GraphSymmetryGroup[#],Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
],
Dividers->All
]

Cases[gdata,{__,0.}]

Symmetric:

gs=Cases[
gdata,
{g_,_,sym:Except[TransformationGroup[{}]],diff_}:>{
HighlightGraph[g1=BilateralGraph[CenterGraph[g],"ReturnNonbilateralGraph"->True],Flatten[FindCoincidentVertices[g1]]],
sym,
diff
}]

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData["MancinskaRobersonGraph13"],50,"ReturnWithMessage"->True];//Quiet//Timing

gdata=SortBy[
{#,Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
]

Cases[gdata,{g_?UnitDistanceGraphEmbeddingQ,_}:>g]

SymmetricEmebddings=Select[gdata,GraphSymmetryGroup[#[[1]]]=!=TransformationGroup[{}]&]

UnitDistance by FindUnitDistanceEmbedding  (random embedding waiting until UD is found)

FindUnitDistanceEmbedding[GraphData["MancinskaRobersonGraph13"],"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

Select[IndexGraph/@gs,!DegenerateGraphEmbeddingQ[#]&&GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]//Timing

Matchstick

GraphData["MancinskaRobersonGraph13","Matchstick"]

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

3D default

Graph3D[GraphData["MancinskaRobersonGraph13","Edges"]]

3D construction

3D All

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

3D UnitDistance construction Random

GraphData["MancinskaRobersonGraph13","Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData["MancinskaRobersonGraph13","VertexList"],
GraphData["MancinskaRobersonGraph13","EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

GraphData["MancinskaRobersonGraph13","Polyhedral"]

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

"MancinskaRobersonGraph14"

Names

GraphData["MancinskaRobersonGraph14","StandardName"]

GraphData["MancinskaRobersonGraph14","StandardNames"]

HouseOfGraphs

hogid=GraphData["MancinskaRobersonGraph14","NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData["MancinskaRobersonGraph14","WikidataID"]

GraphData["MancinskaRobersonGraph14","WikidataID","URL"]

Primary

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

All

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

CurvedEdge

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

Inexact

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

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData["MancinskaRobersonGraph14","Graph","Degenerate"]//Column

Embeddings

GraphDataEmbeddings[GraphData["MancinskaRobersonGraph14"]]

Default embedding

g0=GraphPlot[Graph[GraphData["MancinskaRobersonGraph14","VertexList"],GraphData["MancinskaRobersonGraph14","Edges"]]]

Configuration

GraphData["MancinskaRobersonGraph14","Configuration"]

configurations=GraphData["MancinskaRobersonGraph14","Graph","Configuration"]//StyleGraphs

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData["MancinskaRobersonGraph14","Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData["MancinskaRobersonGraph14","Bipartite"]

GraphData["MancinskaRobersonGraph14","Graph","Bipartite"]//StyleGraphs

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData["MancinskaRobersonGraph14","Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]//Quiet

Circular

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

Circular construction All

GraphData["MancinskaRobersonGraph14","Hamiltonian"]

GraphData["MancinskaRobersonGraph14","HamiltonianCycles"]

GraphData["MancinskaRobersonGraph14","HamiltonianCycleCount"]

GraphData["MancinskaRobersonGraph14","LCF"]

GraphData["MancinskaRobersonGraph14","LCFSignature"]

Length[hc=FindHamiltonianCycle[GraphData["MancinskaRobersonGraph14"],All][[All,All,1]]]//Timing

g=RotateGraph[CircularEmbeddingFromHamiltonianCycle[GraphData["MancinskaRobersonGraph14"],hc[[1]]],Pi+2Pi 7/15]

Length[hcsym=SymmetricHamiltonianCycles[GraphData["MancinskaRobersonGraph14"],hc,ProgressReporting->True]]//Timing

GroupBy[SymmetricHamiltonianCycleGraph[GraphData["MancinskaRobersonGraph14"],#]&/@hcsym,GraphSymmetryGroup]

Planar

GraphData["MancinskaRobersonGraph14","Planar"]

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

MinimalCrossingNumber crossings.uos.de [verified 18]

CrossingNumber[GraphData["MancinskaRobersonGraph14"],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData["MancinskaRobersonGraph14","CN"]

(gs=GraphData["MancinskaRobersonGraph14","Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData["MancinskaRobersonGraph14","RCN"]

GraphData["MancinskaRobersonGraph14","Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Tutte

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

TutteGraphs=BilateralGraph[CenterGraph@IGLayoutTutte[g,"OuterFace"->#],"ReturnNonbilateralGraph"->True]&/@faces

TutteGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["MancinskaRobersonGraph14","V"]])]
}&/@TutteGraphs;

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

LocalCrossingNumberWithEmbeddings=
{1+Max[Length/@DeleteCases[
Drop[AdjacencyList[#],GraphData["MancinskaRobersonGraph14","V"]],
_Integer?(LessEqualThan[GraphData["MancinskaRobersonGraph14","V"]]),
{2}
]],#}&/@TutteGraphs

TutteGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData["MancinskaRobersonGraph14","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@TutteGraphs;

SymmetricEmbeddingsWithOrientations=DeleteCases[
TutteGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]

Select[SymmetricEmbeddingsWithOrientations[[All,1]],Count[OuterFace[#],_?(GreaterThan[GraphData["MancinskaRobersonGraph14","V"]])]==0&]

MinimalCrossing construction Random 1k [157 s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["MancinskaRobersonGraph14"],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [756 s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["MancinskaRobersonGraph14"],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

diagrams1

g=;

GraphCrossingCount@g

GraphCrossingDiagram@g

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [3188 XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["MancinskaRobersonGraph14"],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

graphs=#["Graph"]&/@diagrams

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 1k [old]

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

(RandomGraphs=Table[MinimalCrossingGraph[GraphData["MancinskaRobersonGraph14"],"CrossingNumber"->cn,RandomSeed->n],{n,1000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["MancinskaRobersonGraph14","V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData["MancinskaRobersonGraph14","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalCrossing construction Random 20k [old]

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

(RandomGraphs=Table[MinimalCrossingGraph[GraphData["MancinskaRobersonGraph14"],"CrossingNumber"->cn,RandomSeed->n],{n,20000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["MancinskaRobersonGraph14","V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData["MancinskaRobersonGraph14","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalLocalCrossing

GraphData["MancinskaRobersonGraph14",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData["MancinskaRobersonGraph14",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["MancinskaRobersonGraph14","Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction 1000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData["MancinskaRobersonGraph14"],"CrossingNumber"->cn,RandomSeed->i],{i,1000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

MinimaRectilinearlLocalCrossing construction 20000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData["MancinskaRobersonGraph14"],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Circulant

GraphData["MancinskaRobersonGraph14","Circulant"]

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

Circulant construction

GraphData["MancinskaRobersonGraph14","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["MancinskaRobersonGraph14"]])//AbsoluteTiming

CirculantGraph1@@@ci

Cases[GraphData["MancinskaRobersonGraph14","StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData["MancinskaRobersonGraph14","Line"]

LineGraphQ[GraphData["MancinskaRobersonGraph14"]]//Timing

RootGraph

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

RootGraph[GraphData["MancinskaRobersonGraph14"]]

Halin

GraphData["MancinskaRobersonGraph14","Halin"]

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

Rigid

GraphData["MancinskaRobersonGraph14","Rigid"]

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

Flexible

GraphData["MancinskaRobersonGraph14","Flexible"]

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

Voltage

GraphData["MancinskaRobersonGraph14","Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData["MancinskaRobersonGraph14"],"MaxResults"->20,Debug->True]

Length[gs]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF

GraphData["MancinskaRobersonGraph14","LCF"]

GraphData["MancinskaRobersonGraph14","HamiltonianCycleCount"]

GraphData["MancinskaRobersonGraph14","LCFSignature"]

GraphData["MancinskaRobersonGraph14","LCFNotations"]

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

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

UnitDistance

GraphData["MancinskaRobersonGraph14","UnitDistance"]

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData["MancinskaRobersonGraph14","EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData["MancinskaRobersonGraph14","VertexList"],GraphData["MancinskaRobersonGraph14","EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

gs=UnitDistanceEmbeddingRefine[Graph[VertexList[#],EdgeList[#],VertexCoordinates->GraphEmbedding[#]],MaxIterations->500]&/@Complement@@(GraphData["MancinskaRobersonGraph14","Graph",#]&/@{"All","UnitDistance"})

TextGrid[
gdata=SortBy[
{#,DegenerateGraphEmbeddingQ[#],GraphSymmetryGroup[#],Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
],
Dividers->All
]

Cases[gdata,{__,0.}]

Symmetric:

gs=Cases[
gdata,
{g_,_,sym:Except[TransformationGroup[{}]],diff_}:>{
HighlightGraph[g1=BilateralGraph[CenterGraph[g],"ReturnNonbilateralGraph"->True],Flatten[FindCoincidentVertices[g1]]],
sym,
diff
}]

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData["MancinskaRobersonGraph14"],50,"ReturnWithMessage"->True];//Quiet//Timing

gdata=SortBy[
{#,Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
]

Cases[gdata,{g_?UnitDistanceGraphEmbeddingQ,_}:>g]

SymmetricEmebddings=Select[gdata,GraphSymmetryGroup[#[[1]]]=!=TransformationGroup[{}]&]

UnitDistance by FindUnitDistanceEmbedding  (random embedding waiting until UD is found)

FindUnitDistanceEmbedding[GraphData["MancinskaRobersonGraph14"],"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData["MancinskaRobersonGraph14","Matchstick"]

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

3D default

Graph3D[GraphData["MancinskaRobersonGraph14","Edges"]]

3D construction

3D All

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

3D UnitDistance construction Random

GraphData["MancinskaRobersonGraph14","Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData["MancinskaRobersonGraph14","VertexList"],
GraphData["MancinskaRobersonGraph14","EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

GraphData["MancinskaRobersonGraph14","Polyhedral"]

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

Construction

MancinskaRoberson13Vectors = {
	{1, 0, 0}, {0, 1, 0}, {0, 0, 1},
	{1, 1, 0}, {1, -1, 0}, {1, 0, 1}, {1, 0, -1}, {0, 1, 1}, {0, 1, -1},
	{1, 1, 1}, {1, 1, -1}, {1, -1, 1}, {-1, 1, 1}
};

MancinskaRoberson13Graph = Graph[
	Range[13],
	UndirectedEdge @@@ Select[
		Subsets[Range[13], {2}],
		MancinskaRoberson13Vectors[[#[[1]]]].MancinskaRoberson13Vectors[[#[[2]]]] == 0&
	],
	VertexLabels -> Automatic
]

MancinskaRoberson14Graph = Graph[
	Range[14],
	Join[
		EdgeList[MancinskaRoberson13Graph],
		UndirectedEdge @@@ Thread[{14, Range[13]}]
	],
	VertexLabels -> Automatic
]

MancinskaRobersonGraphs={MancinskaRoberson13Graph,MancinskaRoberson14Graph};

GraphData

GraphDataClassString

GraphDataClassString["MancinskaRobersonGraph*"]

GraphDataString

outstream=OpenWrite["~/MancinskaRobersonGraphs.m"]

WriteString[
outstream,
GraphDataString[
#,
"StandardName"->"MancinskaRobersonGraph"<>ToString[VertexCount[#]],
"Name"->"Mancinska\[Hyphen]Roberson graph "<>ToString[VertexCount[#]],
"Information"->"Mancinska-RobersonGraphs",
"QuantumChromaticNumber"->4
]
]&/@MancinskaRobersonGraphs;

Close[outstream]