Maximally Dense Unit-Distance Graph

Author

Eric W. Weisstein
August 3, 2025

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/MaximallyDenseUnit-DistanceGraph.nb.

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

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

Source

Boris Alexeev, Dustin G. Mixon, Hans Parshall.  The Erdős unit distance problem for small point sets.  16 Dec 2024.  https://arxiv.org/abs/2412.11914

P. Engel, O. Hammond-Lee, Y. Su, D. Varga, P. Zsémboki, Diverse beam search to find densest-known planar unit distance graphs, arXiv:2406.15317

Figure

gs=Select[
GraphData[All],
!FreeQ[GraphData[#,"StandardNames"],{"MaximallyDenseUnitDistance",_}]&
]

cnts=Sort[GraphData[#,{"V","M"}]&/@gs]

https://oeis.org/A186705

Take[Tally[cnts],9][[All,-1]]

bym=SplitBy[Sort[FirstCase[GraphData[#,"StandardNames"],{"MaximallyDenseUnitDistance",i_}:>i]&/@gs],First]

GraphicsGrid[Map[
StyleGraphs@GraphData[{"MaximallyDenseUnitDistance",#}]&,
Take[bym,10],
{2}],
Dividers->All]

Graphs

Embeddings

images=Import["/Users/eww/Downloads/arXiv-2412.11914v2/figure.pdf"]

images={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

Length[images]

FindImageShapes "Circle" [fails]

images[[7]]

FindImageShapes[ColorNegate@Binarize[images[[7]],.9],"Circle"]

Thinning[ColorNegate@Binarize[images[[7]],.9],Method->"Morphological"]

MorphologicalGraph@%

MorphologicalGraph [fails]

Binarize[images[[4]],#]&/@{Automatic,.9}

images[[7]]

FindImageShapes[images[[7]],"Circle"]

ColorNegate@Binarize[images[[7]],.9]

ImageToGraph[images[[7]],"BinaryThreshold"->.9]

RecognizeGraph@%

<<MathWorld`Graphs`

gs1=ImageToGraph[#,"BinaryThreshold"->.9]&/@Rest[gs]

RecognizeGraph/@%

ColorReplace + ComponentMeasurements "Centroid"

images[[7]]

img=ColorNegate@ColorReplace[images[[7]],{Black->Black,_->White}]

points=ComponentMeasurements[img,{"Centroid"}]

pts=Flatten[points[[All,2]],1]

distances=Round[EuclideanDistance@@@Subsets[pts,{2}],2]

Commonest[distances]

ImageToUnitDistanceGraph[img_Image,opts___?OptionQ]:=Module[
{
pointimage=ColorNegate@ColorReplace[img,{Black->Black,_->White}],
points,vertices,edges,distances,ud,scale,
eps=2,
debug=Lookup[{opts},Debug,False],
n
},
points=ComponentMeasurements[pointimage,{"Centroid"}];
If[debug,Print["points: ",points]];

n=Length[points];
If[n==1,Return[Graph[{1},{},VertexCoordinates->{{0,0}}],Module]];

vertices=Flatten[points[[All,2]],1];
If[debug,Print["vertices: ",vertices]];

distances=Round[EuclideanDistance@@@Subsets[vertices,{2}],2];
If[debug,Print["distances: ",distances]];

ud=Commonest[distances][[1]];
If[debug,Print["commonost distance: ",ud]];

edges=Select[
Subsets[Range[n],{2}],
Abs[ud-EuclideanDistance@@vertices[[#]]]<eps&
];

scale=Mean[EuclideanDistance@@vertices[[#]]&/@edges];
If[debug,Print["scale: ",scale]];

vertices=(#-vertices[[1]])&/@vertices/scale;
Graph[Range[n],UndirectedEdge@@@edges,VertexCoordinates->vertices]
]

ImageToUnitDistanceGraph[images[[7]],Debug->True]

EdgeLengths[%]

emb=GraphEmbedding[%190]

RecognizeGraph@%

UnitDistanceGraphsFromVertices=ImageToUnitDistanceGraph/@Rest[images]

And@@(UnitDistanceGraphEmbeddingQ[#,Tolerance->.01]&/@UnitDistanceGraphsFromVertices)

{gs3[[-5]],GraphData[{"UnitDistance",{21,1}}]}

GraphSymmetryGroup/@%

gs3[[-5]]//RecognizeGraph

GraphEmbedding[gs3[[-5]]]

images[[-5]]

TextGrid[RecognizedUnitDistanceGraphsFromVertices={g=#,RecognizeGraph[#]}&/@UnitDistanceGraphsFromVertices,Dividers->All]

Table[cnt[n]:=0,{n,30}];
data={#,#2,{n=VertexCount[#],++cnt[n]}}&@@@RecognizedUnitDistanceGraphsFromVertices

u(n); solutions to Erdos problem

https://oeis.org/A186705

EdgeCount/@SplitBy[data,#[[3,1]]&][[All,1,1]]

Number of solutions to Erdos problem:

Max[#[[All,-1]]]&/@SplitBy[data[[All,-1]],First]

renamerules=Rule[#2,{"MaximallyDenseUnitDistance",#3}]&@@@Cases[data,{_,{"UnitDistance",_},_}]

indexrules=Rule[#2,#3[[2]]]&@@@DeleteCases[data,{_,{"UnitDistance",_}|{},_}]

new=Rule[#,#3]&@@@DeleteCases[data,{_,_?DataPaclets`GraphDataDump`MyGraphQ,_}]

Graphs from Graph6

Table 3: graph6 codes of unit-distance graphs of maximum density.

str=Import["/Users/eww/Downloads/arXiv-2412.11914v2/anc/graph6.txt","String"]

g6=StringReplace[str,{NumberString~~" ":>"","‘"->"`"}];

TextGrid[
data={VertexCount[#],RecognizeGraph[#],#}&/@Rest[ImportString[g6,"Graph6"]],
Dividers->All]

gsfromg6=data[[All,3]]

Length/@{gsfromg6,gs3}

IsomorphicGraphQ@@@Transpose[{gsfromg6,gs3}]

Length/@SplitBy[data,First]

GraphData[#2,"UnitDistance"]&@@@Cases[data,{_,_?DataPaclets`GraphDataDump`MyGraphQ,_}]

Embeddings

<<MathWorld`Graphs`

GraphData["MaximallyDenseUnitDistance*"]

Intersection[GraphData["MaximallyDenseUnitDistance*"],GraphData["Regular"]]

{"MaximallyDenseUnitDistance", {1,1}} == "SingletonGraph"

Names

GraphData[{"MaximallyDenseUnitDistance",{1,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{1,1}},"StandardNames"]

{"MaximallyDenseUnitDistance", {2, 1}} == {"Path", 2}

Names

GraphData[{"MaximallyDenseUnitDistance",{2,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{2,1}},"StandardNames"]

{"MaximallyDenseUnitDistance", {3, 1}} == "TriangleGraph"

Names

GraphData[{"MaximallyDenseUnitDistance",{3,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{1,1}},"StandardNames"]

{"MaximallyDenseUnitDistance", {4, 1}} == "DiamondGraph"

Names

GraphData[{"MaximallyDenseUnitDistance",{4,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{4,1}},"StandardNames"]

{"MaximallyDenseUnitDistance", {5, 1}} == "GemGraph"

Names

GraphData[{"MaximallyDenseUnitDistance",{5,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{5,1}},"StandardNames"]

{"MaximallyDenseUnitDistance", {6, 1}} == {"Prism", 3}

Names

GraphData[{"MaximallyDenseUnitDistance",{6,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{6,1}},"StandardNames"]

{"MaximallyDenseUnitDistance", {6, 2}} == {"Fan", {1, 5}}

Names

GraphData[{"MaximallyDenseUnitDistance",{6,2}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{6,2}},"StandardNames"]

{"MaximallyDenseUnitDistance", {6, 3}} == {"Beineke", 8}

Names

GraphData[{"MaximallyDenseUnitDistance",{6,3}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{6,3}},"StandardNames"]

{"MaximallyDenseUnitDistance", {6, 4}} == {"TriangularGrid", 2}

Names

GraphData[{"MaximallyDenseUnitDistance",{6,4}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{6,4}},"StandardNames"]

{"MaximallyDenseUnitDistance", {7, 1}} == {"Wheel", 7}

Names

GraphData[{"MaximallyDenseUnitDistance",{7,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{7,1}},"StandardNames"]

{"MaximallyDenseUnitDistance", {8, 1}} == {"SelfComplementary", {8, 10}}

Names

GraphData[{"MaximallyDenseUnitDistance",{8,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{8,1}},"StandardNames"]

{"MaximallyDenseUnitDistance", {8, 2}} == {"JohnsonSkeleton", 26}

Names

GraphData[{"MaximallyDenseUnitDistance",{8,2}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{8,2}},"StandardNames"]

{"MaximallyDenseUnitDistance", {8, 3}}

Names

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"StandardNames"]

Primary

GraphData[{"MaximallyDenseUnitDistance",{8,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{8,3}}]]

Default embedding

RotateGraph[Graph[GraphData[{"MaximallyDenseUnitDistance",{8,3}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Edges"]],Pi/2]

v=Join[CirclePoints[6],{{0,0},{0,Sqrt[3]}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphPlot@RotateGraph[Graph[GraphData[{"MaximallyDenseUnitDistance",{8,3}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Edges"],GraphLayout->"TutteEmbedding"],-1.8]

v=Append[CirclePoints[7],{0,0}];
g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs={,,};

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{8,3}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{8,3}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{8,3}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[BilateralOrRotationalGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

RotateGraph[,Pi]

g=FindCorrespondingGraph[,CirclePoints[{1,Pi/2},8]]

Planar

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyDenseUnitDistance",{8,3}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyDenseUnitDistance",{8,3}}]],10]

PlanarGraphEmbeddings

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{8,3}}],Debug->True])//Timing

Length[plemb]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{8,3}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{8,3}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{8,3}},"ComplementGraph","Name"]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{8,3}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{8,3}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{8,3}}]]

RecognizeGraph[%]

Halin

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{8,3}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{8,3}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{8,3}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{8,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{8,3}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{8,3}},"Graph",{"3D","Polyhedron"}]

{"MaximallyDenseUnitDistance", {9, 1}} == {"GeneralizedQuadrangle", {2, 1}}

Names

GraphData[{"MaximallyDenseUnitDistance",{9,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{9,1}},"StandardNames"]

{"MaximallyDenseUnitDistance", {10, 1}}

Names

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"StandardNames"]

Alexeev et al. (2024)

Primary

GraphData[{"MaximallyDenseUnitDistance",{10,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{10,1}}]]

Default embedding

GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{10,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{10,1}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[BilateralOrRotationalGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

gs={,};

RecognizeGraph/@gs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Planar

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"CN"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"RCN"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"CrossingNumber"->cn])//PolyhedralGraphQ

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{10,1}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{10,1}},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{10,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

g0=LabelGraph@GraphData[{"GeneralizedQuadrangle",{2,1}},"Graph","MinimalCrossing"][[1]]

v=GraphEmbedding[g0];
AppendTo[v,{v[[4,1]],v[[5,2]]}];
g=Graph[Range[Length[v]],Join[EdgeList[g0],UndirectedEdge@@@{{5,10},{4,10}}],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{10,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{10,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],TimeConstraint->10])//AbsoluteTiming

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{10,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{10,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{10,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{10,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{10,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{10,1}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{10,1}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{10,1}}]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{10,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{10,1}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{10,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

UnitDistance construction from GQ2,1

RecognizeGraph@VertexDelete[LabelGraph@,212]

LabelGraph/@GraphData[{"GeneralizedQuadrangle",{2,1}},"Graph","UnitDistance"]

v0=GraphEmbedding[];

v=Append[v0,UnitDistancePoint[Sequence@@v0[[{3,9}]]]];

g=Graph[Range@Length@v,UnitEdges[v],VertexCoordinates->v]

RecognizeGraph@g

v0=GraphEmbedding[];

v=Append[v0,UnitDistancePoint[Sequence@@v0[[{1,2}]]]];

g=Graph[Range@Length@v,UnitEdges[v],VertexCoordinates->v]

RecognizeGraph@g

gs={,};

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{10,1}},"Graph",{"3D","Polyhedron"}]

{"MaximallyDenseUnitDistance", {11, 1}}

Names

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"StandardNames"]

Alexeev et al. (2024)

Primary

GraphData[{"MaximallyDenseUnitDistance",{11,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{11,1}}]]

Default embedding

GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{11,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{11,1}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],#]&/@hc);//Timing

circ

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[BilateralOrRotationalGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Planar

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"CN"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"RCN"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{11,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{11,1}},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{11,1}},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{11,1}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{11,1}},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{11,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

GraphPlot@

v={#,1-#2}&@@@{{0,0},{1,0},{1,1},{1/2,1},{0,1},{1/2,1/8},{3/8,1/2},{5/8,1/2},{3/8,3/4},{1/2,3/4},{5/8,3/4}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,1,7,11,10,9,8,2],e[9,4,11,3,6,5,9],e[6,7,10,8,6],{5,7},{3,8}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

GraphPlot@RotateGraph[,2Pi/5]

GraphPlot@RotateGraph[,4Pi/5]

GraphPlot@RotateGraph[,-4Pi/5]

MinimalLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{11,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{11,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],TimeConstraint->10])//AbsoluteTiming

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{11,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{11,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{11,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{11,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{11,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{11,1}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{11,1}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{11,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{11,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{11,1}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{11,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{11,1}},"Graph",{"3D","Polyhedron"}]

{"MaximallyDenseUnitDistance", {11, 2}}

Names

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"StandardNames"]

Alexeev et al. (2024)

RecognizeGraph@%

Primary

GraphData[{"MaximallyDenseUnitDistance",{11,2}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{11,2}}]]

Default embedding

GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{11,2}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{11,2}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

gs=SymmetricGraphs[[All,1]]

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Planar

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"CN"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"RCN"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{11,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{11,2}},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{11,2}},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{11,2}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{11,2}},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{11,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

RotateGraph[,-2Pi/3]

GraphPlot@

GraphPlot@RotateGraph[,-Pi/2]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{11,2}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{11,2}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],TimeConstraint->10])//AbsoluteTiming

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{11,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{11,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{11,2}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{11,2}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{11,2}},"ComplementGraph","Name"]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{11,2}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{11,2}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{11,2}}]]

Halin

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{11,2}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{11,2}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{11,2}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{11,2}},"Graph",{"3D","Polyhedron"}]

{"MaximallyDenseUnitDistance", {12, 1}}

Names

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"StandardNames"]

Alexeev et al. (2024)

RecognizeGraph[%]

Primary

GraphData[{"MaximallyDenseUnitDistance",{12,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{12,1}}]]

Default embedding

RotateGraph[ GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{12,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Edges"]]],Pi/2]

v=Join[CirclePoints[7],CirclePoints[{1/4,-Pi/2},5]];
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{12,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Edges"],GraphLayout->"SpringEmbedding"]]

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{12,1}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

gs=Rest[BilateralGraphs]

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Planar

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"CN"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"RCN"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{12,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{12,1}},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{12,1}},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{12,1}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{12,1}},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{12,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{12,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{12,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],TimeConstraint->10])//AbsoluteTiming

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{12,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{12,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{12,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{12,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{12,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{12,1}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{12,1}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{12,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{12,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{12,1}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{12,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Edges"]]

3D construction

v

v=Join@@Table[Append[#,t]&/@CirclePoints[{1,0},3],{t,{-1,1}}];
v=Join[v,Append[#,0]&/@Append[CirclePoints[{1,0},5],{0,0}]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,1],e[4,5,6,4],e[7,8,9,10,11,7],e[1,7,4],e[6,11,3,10,6],e[2,8,5,9,2],e[10,12,9],{7,12},{8,11}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{12,1}},"Graph",{"3D","Polyhedron"}]

{"MaximallyDenseUnitDistance", {13, 1}}

Names

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"StandardNames"]

Alexeev et al. (2024)

RecognizeGraph@%

Primary

GraphData[{"MaximallyDenseUnitDistance",{13,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{13,1}}]]

Default embedding

GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{13,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{13,1}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],#]&/@hc);//Timing

Take[circ,10]

g=;

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Planar

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"CN"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"RCN"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{13,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{13,1}},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{13,1}},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{13,1}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{13,1}},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{13,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{13,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{13,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],TimeConstraint->10])//AbsoluteTiming

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{13,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{13,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{13,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{13,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{13,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{13,1}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{13,1}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{13,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{13,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{13,1}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{13,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{13,1}},"Graph",{"3D","Polyhedron"}]

{"MaximallyDenseUnitDistance", {14, 1}}

Names

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"StandardNames"]

Alexeev et al. (2024)

RecognizeGraph@%

Primary

GraphData[{"MaximallyDenseUnitDistance",{14,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{14,1}}]]

Default embedding

GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{14,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Edges"],GraphLayout->"SpringEmbedding"]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{14,1}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Planar

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"CN"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"RCN"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{14,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{14,1}},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{14,1}},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{14,1}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{14,1}},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{14,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{14,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{14,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],TimeConstraint->10])//AbsoluteTiming

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{14,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{14,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{14,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{14,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{14,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{14,1}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{14,1}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{14,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{14,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{14,1}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{14,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{14,1}},"Graph",{"3D","Polyhedron"}]

{"MaximallyDenseUnitDistance", {14, 2}}

Names

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"StandardNames"]

Alexeev et al. (2024)

RecognizeGraph@%

Primary

GraphData[{"MaximallyDenseUnitDistance",{14,2}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{14,2}}]]

Default embedding

GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{14,2}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{14,2}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Circular construction old

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyDenseUnitDistance",{14,2}}]],10]

PlanarGraphEmbeddings

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"MaximallyDenseUnitDistance",{14,2}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"OuterFace"->#]&/@faces

TextGrid[DeleteCases[{#,GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}],Dividers->All]

Grid[DeleteCases[{#,Cases[GraphSymmetryGroup[#],r_Rotation:>r,∞]}&/@gs,{_,{}}],Dividers->All]

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

TutteLayoutManipulate[g_Graph]:=Manipulate[
With[{face=OuterFace[g]},
IGLayoutTutte[IGEdgeMap[(EuclideanDistance@@#)^pow&,EdgeWeight->IGEdgeVertexProp[VertexCoordinates],IGLayoutTutte[g,"OuterFace"->face]],"OuterFace"->face,ImageSize->Automatic]],{{pow,1},.1,2}]

TutteLayoutManipulate[]

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

RecognizeGraph[g]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"CN"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"RCN"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{14,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{14,2}},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{14,2}},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{14,2}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{14,2}},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{14,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{14,2}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{14,2}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],TimeConstraint->10])//AbsoluteTiming

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{14,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{14,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{14,2}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{14,2}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{14,2}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{14,2}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{14,2}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{14,2}}]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],TimeConstraint->120]

LCF compute 10^5 [XX GB]

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"MaximallyDenseUnitDistance",{14,2}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^6 [XX GB]

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"MaximallyDenseUnitDistance",{14,2}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"MaximallyDenseUnitDistance",{14,2}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"MaximallyDenseUnitDistance",{14,2}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{14,2}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{14,2}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{14,2}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance construction via UnitDistanceEmbeddingRefine of exact construction

(unitdistancegraphs=Flatten[With[{step=.1},
Table[
{{a,b,c},
UnitDistanceEmbeddingRefine@Graph[Range[40],ee,VertexCoordinates->N@Join[Sequence@@Table[CirclePoints[Through[{Cos,Sin}[Pi/2-2Pi i/5]],{a,Pi/2-2Pi i/5+2Pi i/6},6],{i,0,4}],CirclePoints[b,5],CirclePoints[c,5]]]},
{a,step,2,step},{b,step,2,step},{c,step,2,step}
]],2]);//Quiet//Timing

{Length[unitdistancegraphs],Count[unitdistancegraphs,_?(UnitDistanceGraphEmbeddingQ[Last[#]]&)]}

RandomSample[unitdistancegraphs,10]

Select[unitdistancegraphs,DegenerateGraphEmbeddingQ[Last[#]]===False&]//Timing

MinimumDistance[v_]:=Min[EuclideanDistance@@@Subsets[v,{2}]]

distances=MinimumDistance[GraphEmbedding[#]]&/@unitdistancegraphs[[All,-1]];

Histogram[distances]

Max[distances]

Position[distances,Max[distances]]

Take[ReverseSortBy[Transpose[{distances,unitdistancegraphs}],First],10]

UnitDistanceGraphEmbeddingQ/@gs

DegenerateGraphEmbeddingTypes/@gs

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{14,2}},"Graph",{"3D","Polyhedron"}]

{"MaximallyDenseUnitDistance", {15, 1}}

Names

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"StandardNames"]

Alexeev et al. (2024)

RecognizeGraph@%

Primary

GraphData[{"MaximallyDenseUnitDistance",{15,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{15,1}}]]

Default embedding

GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{15,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{15,1}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],#]&/@hc);//Timing

Take[circ,10]

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Circular construction old

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyDenseUnitDistance",{15,1}}]],10]

PlanarGraphEmbeddings

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"MaximallyDenseUnitDistance",{15,1}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"OuterFace"->#]&/@faces

TextGrid[DeleteCases[{#,GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}],Dividers->All]

Grid[DeleteCases[{#,Cases[GraphSymmetryGroup[#],r_Rotation:>r,∞]}&/@gs,{_,{}}],Dividers->All]

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

TutteLayoutManipulate[g_Graph]:=Manipulate[
With[{face=OuterFace[g]},
IGLayoutTutte[IGEdgeMap[(EuclideanDistance@@#)^pow&,EdgeWeight->IGEdgeVertexProp[VertexCoordinates],IGLayoutTutte[g,"OuterFace"->face]],"OuterFace"->face,ImageSize->Automatic]],{{pow,1},.1,2}]

TutteLayoutManipulate[]

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

RecognizeGraph[g]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"CN"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"RCN"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{15,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{15,1}},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{15,1}},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{15,1}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{15,1}},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{15,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{15,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{15,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],TimeConstraint->10])//AbsoluteTiming

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{15,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{15,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{15,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{15,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{15,1}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{15,1}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{15,1}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{15,1}}]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],TimeConstraint->120]

LCF compute 10^5 [XX GB]

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"MaximallyDenseUnitDistance",{15,1}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^6 [XX GB]

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"MaximallyDenseUnitDistance",{15,1}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"MaximallyDenseUnitDistance",{15,1}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"MaximallyDenseUnitDistance",{15,1}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{15,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{15,1}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{15,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance construction via UnitDistanceEmbeddingRefine of exact construction

(unitdistancegraphs=Flatten[With[{step=.1},
Table[
{{a,b,c},
UnitDistanceEmbeddingRefine@Graph[Range[40],ee,VertexCoordinates->N@Join[Sequence@@Table[CirclePoints[Through[{Cos,Sin}[Pi/2-2Pi i/5]],{a,Pi/2-2Pi i/5+2Pi i/6},6],{i,0,4}],CirclePoints[b,5],CirclePoints[c,5]]]},
{a,step,2,step},{b,step,2,step},{c,step,2,step}
]],2]);//Quiet//Timing

{Length[unitdistancegraphs],Count[unitdistancegraphs,_?(UnitDistanceGraphEmbeddingQ[Last[#]]&)]}

RandomSample[unitdistancegraphs,10]

Select[unitdistancegraphs,DegenerateGraphEmbeddingQ[Last[#]]===False&]//Timing

MinimumDistance[v_]:=Min[EuclideanDistance@@@Subsets[v,{2}]]

distances=MinimumDistance[GraphEmbedding[#]]&/@unitdistancegraphs[[All,-1]];

Histogram[distances]

Max[distances]

Position[distances,Max[distances]]

Take[ReverseSortBy[Transpose[{distances,unitdistancegraphs}],First],10]

UnitDistanceGraphEmbeddingQ/@gs

DegenerateGraphEmbeddingTypes/@gs

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{15,1}},"Graph",{"3D","Polyhedron"}]

{"MaximallyDenseUnitDistance",{17,1}}

Names

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"StandardNames"]

Alexeev et al. (2024)

GraphData[{"MaximallyDenseUnitDistance",{17,1}}]//StyleGraphs

Primary

GraphData[{"MaximallyDenseUnitDistance",{17,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{17,1}}]]

Default embedding

GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{17,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{17,1}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Circular construction old

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyDenseUnitDistance",{17,1}}]],10]

PlanarGraphEmbeddings

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"MaximallyDenseUnitDistance",{17,1}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"OuterFace"->#]&/@faces

TextGrid[DeleteCases[{#,GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}],Dividers->All]

Grid[DeleteCases[{#,Cases[GraphSymmetryGroup[#],r_Rotation:>r,∞]}&/@gs,{_,{}}],Dividers->All]

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

TutteLayoutManipulate[g_Graph]:=Manipulate[
With[{face=OuterFace[g]},
IGLayoutTutte[IGEdgeMap[(EuclideanDistance@@#)^pow&,EdgeWeight->IGEdgeVertexProp[VertexCoordinates],IGLayoutTutte[g,"OuterFace"->face]],"OuterFace"->face,ImageSize->Automatic]],{{pow,1},.1,2}]

TutteLayoutManipulate[]

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

RecognizeGraph[g]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"CN"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"RCN"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{17,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{17,1}},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{17,1}},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{17,1}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{17,1}},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{17,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{17,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{17,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],TimeConstraint->10])//AbsoluteTiming

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{17,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{17,1}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{17,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{17,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{17,1}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{17,1}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{17,1}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{17,1}}]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],TimeConstraint->120]

LCF compute 10^5 [XX GB]

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"MaximallyDenseUnitDistance",{17,1}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^6 [XX GB]

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"MaximallyDenseUnitDistance",{17,1}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"MaximallyDenseUnitDistance",{17,1}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"MaximallyDenseUnitDistance",{17,1}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{17,1}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{17,1}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{17,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance construction via UnitDistanceEmbeddingRefine of exact construction

(unitdistancegraphs=Flatten[With[{step=.1},
Table[
{{a,b,c},
UnitDistanceEmbeddingRefine@Graph[Range[40],ee,VertexCoordinates->N@Join[Sequence@@Table[CirclePoints[Through[{Cos,Sin}[Pi/2-2Pi i/5]],{a,Pi/2-2Pi i/5+2Pi i/6},6],{i,0,4}],CirclePoints[b,5],CirclePoints[c,5]]]},
{a,step,2,step},{b,step,2,step},{c,step,2,step}
]],2]);//Quiet//Timing

{Length[unitdistancegraphs],Count[unitdistancegraphs,_?(UnitDistanceGraphEmbeddingQ[Last[#]]&)]}

RandomSample[unitdistancegraphs,10]

Select[unitdistancegraphs,DegenerateGraphEmbeddingQ[Last[#]]===False&]//Timing

MinimumDistance[v_]:=Min[EuclideanDistance@@@Subsets[v,{2}]]

distances=MinimumDistance[GraphEmbedding[#]]&/@unitdistancegraphs[[All,-1]];

Histogram[distances]

Max[distances]

Position[distances,Max[distances]]

Take[ReverseSortBy[Transpose[{distances,unitdistancegraphs}],First],10]

UnitDistanceGraphEmbeddingQ/@gs

DegenerateGraphEmbeddingTypes/@gs

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Polyhedron"]}]

3D Canonical

GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"MaximallyDenseUnitDistance",{17,1}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

{"MaximallyDenseUnitDistance", {17, 2}}

Names

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"StandardName"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"StandardNames"]

Alexeev et al. (2024)

RecognizeGraph@%

Primary

GraphData[{"MaximallyDenseUnitDistance",{17,2}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{17,2}}]]

Default embedding

GraphPlot[Graph[GraphData[{"MaximallyDenseUnitDistance",{17,2}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","Degenerate"]

HouseOfGraphs

hogid=GraphData[{"MaximallyDenseUnitDistance",{17,2}},"NotationRules","HouseOfGraphs"]

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

GeneralizedPetersen

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Hamiltonian"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Circular construction old

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Planar"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyDenseUnitDistance",{17,2}}]],10]

PlanarGraphEmbeddings

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"MaximallyDenseUnitDistance",{17,2}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"OuterFace"->#]&/@faces

TextGrid[DeleteCases[{#,GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}],Dividers->All]

Grid[DeleteCases[{#,Cases[GraphSymmetryGroup[#],r_Rotation:>r,∞]}&/@gs,{_,{}}],Dividers->All]

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

TutteLayoutManipulate[g_Graph]:=Manipulate[
With[{face=OuterFace[g]},
IGLayoutTutte[IGEdgeMap[(EuclideanDistance@@#)^pow&,EdgeWeight->IGEdgeVertexProp[VertexCoordinates],IGLayoutTutte[g,"OuterFace"->face]],"OuterFace"->face,ImageSize->Automatic]],{{pow,1},.1,2}]

TutteLayoutManipulate[]

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

RecognizeGraph[g]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"CN"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"RCN"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{17,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{17,2}},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{17,2}},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{17,2}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"MaximallyDenseUnitDistance",{17,2}},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{17,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{17,2}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyDenseUnitDistance",{17,2}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

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

(cn=CrossingNumber[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],TimeConstraint->10])//AbsoluteTiming

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{17,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"MaximallyDenseUnitDistance",{17,2}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Circulant"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyDenseUnitDistance",{17,2}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyDenseUnitDistance",{17,2}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyDenseUnitDistance",{17,2}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Line"]

LineGraphQ[GraphData[{"MaximallyDenseUnitDistance",{17,2}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyDenseUnitDistance",{17,2}}&]

RootGraph[GraphData[{"MaximallyDenseUnitDistance",{17,2}}]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Halin"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Rigid"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Flexible"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"LCF"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"HamiltonianCycleCount"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"LCFSignature"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"LCFNotations"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],TimeConstraint->120]

LCF compute 10^5 [XX GB]

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"MaximallyDenseUnitDistance",{17,2}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^6 [XX GB]

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"MaximallyDenseUnitDistance",{17,2}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"MaximallyDenseUnitDistance",{17,2}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"MaximallyDenseUnitDistance",{17,2}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],Debug->True]//Timing

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyDenseUnitDistance",{17,2}},"VertexList"],GraphData[{"MaximallyDenseUnitDistance",{17,2}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyDenseUnitDistance",{17,2}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance construction via UnitDistanceEmbeddingRefine of exact construction

(unitdistancegraphs=Flatten[With[{step=.1},
Table[
{{a,b,c},
UnitDistanceEmbeddingRefine@Graph[Range[40],ee,VertexCoordinates->N@Join[Sequence@@Table[CirclePoints[Through[{Cos,Sin}[Pi/2-2Pi i/5]],{a,Pi/2-2Pi i/5+2Pi i/6},6],{i,0,4}],CirclePoints[b,5],CirclePoints[c,5]]]},
{a,step,2,step},{b,step,2,step},{c,step,2,step}
]],2]);//Quiet//Timing

{Length[unitdistancegraphs],Count[unitdistancegraphs,_?(UnitDistanceGraphEmbeddingQ[Last[#]]&)]}

RandomSample[unitdistancegraphs,10]

Select[unitdistancegraphs,DegenerateGraphEmbeddingQ[Last[#]]===False&]//Timing

MinimumDistance[v_]:=Min[EuclideanDistance@@@Subsets[v,{2}]]

distances=MinimumDistance[GraphEmbedding[#]]&/@unitdistancegraphs[[All,-1]];

Histogram[distances]

Max[distances]

Position[distances,Max[distances]]

Take[ReverseSortBy[Transpose[{distances,unitdistancegraphs}],First],10]

UnitDistanceGraphEmbeddingQ/@gs

DegenerateGraphEmbeddingTypes/@gs

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Matchstick"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Polyhedral"]

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Polyhedron"]}]

3D Canonical

GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"MaximallyDenseUnitDistance",{17,2}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

GraphData

GraphDataString

file=OpenAppend["~/maximally-dense.m"]

WriteString[file,
GraphDataString[#,
"StandardName"->{"MaximallyDenseUnitDistance",#2},
"Name"->ToString[#2[[1]]]<>"\[Hyphen]maximally dense unit\[Hyphen]distance graph "<>ToString[#2[[2]]],
"Classes"->{"UnitDistance"},
"NotationRules"->{"MaximallyDenseUnitDistance"->#2},
"Skip"->{"ConstructionNumber","MinorCount","QuadraticEmbeddingConstant"},
TimeConstraint->10
]]&@@@new;

Close[file]