Maximally Laman Graph

Author

Eric W. Weisstein
July 11, 2026

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

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

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

Maximally Laman graphs

Precomputed

RecordEdges=<|3->{{{1,2},{1,3},{2,3}}},4->{{{1,3},{1,4},{2,3},{2,4},{3,4}}},5->{{{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5}},{{1,4},{1,5},{2,3},{2,5},{3,4},{3,5},{4,5}},{{1,4},{1,5},{2,4},{2,5},{3,4},{3,5},{4,5}}},6->{{{1,4},{1,5},{1,6},{2,3},{2,5},{2,6},{3,4},{3,6},{4,5}}},7->{{{1,2},{1,5},{1,6},{2,3},{2,4},{3,6},{3,7},{4,5},{4,7},{5,7},{6,7}}},8->{{{1,2},{1,4},{1,8},{2,3},{2,7},{3,6},{3,8},{4,5},{4,7},{5,7},{5,8},{6,7},{6,8}}},9->{{{1,4},{1,6},{1,9},{2,3},{2,5},{2,8},{3,7},{3,9},{4,7},{4,9},{5,7},{5,8},{6,7},{6,8},{8,9}}},10->{{{1,4},{1,8},{1,10},{2,3},{2,7},{2,10},{3,7},{3,9},{4,8},{4,9},{5,7},{5,8},{5,10},{6,7},{6,8},{6,9},{9,10}}},11->{{{1,2},{1,10},{1,11},{2,8},{2,9},{3,7},{3,9},{3,10},{4,7},{4,10},{4,11},{5,7},{5,8},{5,9},{6,7},{6,8},{6,11},{8,11},{9,10}}},12->{{{1,10},{1,11},{1,12},{2,9},{2,11},{2,12},{3,8},{3,10},{3,12},{4,7},{4,9},{4,11},{5,7},{5,8},{5,10},{6,7},{6,8},{6,9},{7,12},{8,11},{9,10}}},
13->{{{1,8},{1,11},{1,13},{2,8},{2,10},{2,13},{3,7},{3,11},{3,12},{4,7},{4,10},{4,12},{5,9},{5,10},{5,13},{6,9},{6,11},{6,12},{7,9},{7,13},{8,9},{8,12},{10,11}}},14->{{{1,11},{1,12},{1,14},{2,9},{2,10},{2,14},{3,7},{3,8},{3,14},{4,9},{4,10},{4,13},{5,7},{5,8},{5,13},{6,11},{6,12},{6,13},{7,10},{7,12},{8,9},{8,11},{9,12},{10,11},{13,14}}}|>;

MaximallyLamanGraphs={#,#2,RecognizeGraph@#2}&@@@(Catenate@KeyValueMap[Function[{n,edgeLists},MapIndexed[{{n,First[#2]},Graph[Range[n],UndirectedEdge@@@#1]}&,edgeLists]],RecordEdges])

Compute

Do[Print[{n,FindMaximalLamanGraph[n,All]//AbsoluteTiming}],{n,3,12}]

Do[Print[{n,FindMaximalLamanGraph[n,All]//AbsoluteTiming}],{n,{13}}]

Quit

n == 14 could need ~77 days of wall time using ~8 cores :(

Figure

GraphicsGrid[
Partition[
With[{r=RecognizeGraph[#2]},
StyleGraphs@Annotate[
GraphData[r],
PlotLabel->Column[
{
Row[{Style["n",Italic]," == ",#[[1]],Sequence@@If[#[[1]]===5,{" #",#[[2]]}]},{}],
With[{name=GraphData[r,"Name"],not=GraphData[r,"Notation"]},
Which[
!MissingQ[not],
	not/.char:("C"|"K"|"P")->Style[char,Italic],
StringContainsQ[name,"maximally Laman"],
	Nothing,
True,
	Style[name,Italic]]
],
Row[{"Laman number: ",GraphData[r,"LamanNumber"]}]
},
Alignment->Center,BaseStyle->Directive[FontFamily->"Times",14]]]
]&@@@MaximallyLamanGraphs,
UpTo[5]
],
Dividers->All,
ImageSize->890,Alignment->Top
]

Laman number computation

Print[{VertexCount[#],LamanNumber[#]//Timing}]&/@RecordGraphs[[All,2,1]]

Print[{VertexCount[#],LamanNumber[#,Method->"C"]//AbsoluteTiming}]&/@RecordGraphs[[All,2,1]]

Unit distance

TextGrid[GraphData[#,{"#","UnitDistance"}]&/@GraphData["MaximallyLaman*"],Dividers->All]

Embeddings

<<MathWorld`Graphs`

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

Names

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

GraphData[{"MaximallyLaman",{3,1}},"StandardNames"]

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

Names

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

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

{"MaximallyLaman", {5, 1}} == {"Beineke", 2}

Names

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

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

{"MaximallyLaman", {5, 2}} == "GemGraph"

Names

GraphData[{"MaximallyLaman",{5,2}},"StandardName"]

GraphData[{"MaximallyLaman",{5,2}},"StandardNames"]

{"MaximallyLaman", {5, 3}} == {"CompleteTripartite", {1, 1, 3}}

Names

GraphData[{"MaximallyLaman",{5,3}},"StandardName"]

GraphData[{"MaximallyLaman",{5,3}},"StandardNames"]

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

Names

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

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

{"MaximallyLaman", {7, 1}} == "HemicubicalGraph"

Names

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

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

{"MaximallyLaman", {8, 1}} == {"HeptahedralDual", 30}

Names

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

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

{"MaximallyLaman", {9, 1}}

Names

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

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

HouseOfGraphs

hogid=GraphData[{"MaximallyLaman",{9,1}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"MaximallyLaman",{9,1}},"WikidataID"]

GraphData[{"MaximallyLaman",{9,1}},"WikidataID","URL"]

Primary

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

All

GraphData[{"MaximallyLaman",{9,1}},"Graph","All"]//StyleGraphs

CurvedEdge

GraphData[{"MaximallyLaman",{9,1}},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

GraphData[{"MaximallyLaman",{9,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyLaman",{9,1}},"Graph","Degenerate"]//Column

Embeddings

GraphDataEmbeddings[GraphData[{"MaximallyLaman",{9,1}}]]

Default embedding

g0=RotateGraph[GraphPlot[Graph[GraphData[{"MaximallyLaman",{9,1}},"VertexList"],GraphData[{"MaximallyLaman",{9,1}},"Edges"],GraphLayout->"SpringEmbedding"]],Pi]

g=FindCorrespondingGraph[,Join[CirclePoints[7],{#/3,0}&/@{-1,1}]]//Quiet

RecognizeGraph@g

g=FindCorrespondingGraph[,{{0,0},{1/3,0},{2/3,0},{1,0},{1,1},{1/2,1},{0,1},{1/3,1/2},{2/3,1/2}}]

RecognizeGraph@g

Configuration

GraphData[{"MaximallyLaman",{9,1}},"Configuration"]

configurations=GraphData[{"MaximallyLaman",{9,1}},"Graph","Configuration"]//StyleGraphs

GeneralizedPetersen

GraphData[{"MaximallyLaman",{9,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyLaman",{9,1}},"Graph","IGraph"]//StyleGraphs

CompleteKPartite

GraphData[{"MaximallyLaman",{9,1}},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"MaximallyLaman",{9,1}},"Bipartite"]

GraphData[{"MaximallyLaman",{9,1}},"Graph","Bipartite"]//StyleGraphs

Bilateral

GraphData[{"MaximallyLaman",{9,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"MaximallyLaman",{9,1}},"Graph","Circular"]//StyleGraphs

Circular construction All

GraphData[{"MaximallyLaman",{9,1}},"Hamiltonian"]

GraphData[{"MaximallyLaman",{9,1}},"HamiltonianCycles"]

GraphData[{"MaximallyLaman",{9,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyLaman",{9,1}},"LCF"]

GraphData[{"MaximallyLaman",{9,1}},"LCFSignature"]

Length[hc=FindHamiltonianCycle[GraphData[{"MaximallyLaman",{9,1}}],All][[All,All,1]]]//Timing

gs=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyLaman",{9,1}}],#]&/@Take[hc,1]

Length[hcsym=SymmetricHamiltonianCycles[GraphData[{"MaximallyLaman",{9,1}}],hc,ProgressReporting->True]]//Timing

groups=GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"MaximallyLaman",{9,1}}],#]&/@hcsym,GraphSymmetryGroup]

gs=Join@@Values[groups]

Planar

GraphData[{"MaximallyLaman",{9,1}},"Planar"]

GraphData[{"MaximallyLaman",{9,1}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyLaman",{9,1}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyLaman",{9,1}}]],10]

PlanarGraphEmbeddings

GraphData[{"MaximallyLaman",{9,1}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyLaman",{9,1}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"MaximallyLaman",{9,1}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"MaximallyLaman",{9,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[]]

g=ToGridEmbedding[]

RecognizeGraph[g]

DegenerateGraphEmbeddingTypes@g

MinimalCrossing

GraphData[{"MaximallyLaman",{9,1}},"CN"]

(gs=GraphData[{"MaximallyLaman",{9,1}},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"MaximallyLaman",{9,1}},"RCN"]

GraphData[{"MaximallyLaman",{9,1}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"MaximallyLaman",{9,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyLaman",{9,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyLaman",{9,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyLaman",{9,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"MaximallyLaman",{9,1}},"Circulant"]

GraphData[{"MaximallyLaman",{9,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyLaman",{9,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyLaman",{9,1}}]])//AbsoluteTiming

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyLaman",{9,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyLaman",{9,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"MaximallyLaman",{9,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyLaman",{9,1}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"MaximallyLaman",{9,1}}]]

Halin

GraphData[{"MaximallyLaman",{9,1}},"Halin"]

GraphData[{"MaximallyLaman",{9,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyLaman",{9,1}},"Rigid"]

GraphData[{"MaximallyLaman",{9,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyLaman",{9,1}},"Flexible"]

GraphData[{"MaximallyLaman",{9,1}},"Graph","Flexible"]//StyleGraphs

Voltage

GraphData[{"MaximallyLaman",{9,1}},"Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData[{"MaximallyLaman",{9,1}}],"MaxResults"->20,Debug->True]

Length[gs]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF

GraphData[{"MaximallyLaman",{9,1}},"LCF"]

GraphData[{"MaximallyLaman",{9,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyLaman",{9,1}},"LCFSignature"]

GraphData[{"MaximallyLaman",{9,1}},"LCFNotations"]

GraphData[{"MaximallyLaman",{9,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"MaximallyLaman",{9,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyLaman",{9,1}}],Debug->True]//Timing

GraphData[{"MaximallyLaman",{9,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{9,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{9,1}},"VertexList"],GraphData[{"MaximallyLaman",{9,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"MaximallyLaman",{9,1}}],50,"ReturnWithMessage"->True];//Quiet//Timing

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

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

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

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

FindUnitDistanceEmbedding[GraphData[{"MaximallyLaman",{9,1}}],"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"MaximallyLaman",{9,1}},"Matchstick"]

GraphData[{"MaximallyLaman",{9,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyLaman",{9,1}},"Edges"]]

3D construction

3D All

GraphData[{"MaximallyLaman",{9,1}},"Graph",{"3D","All"}]

3D UnitDistance refinement from Canonical

UnitDistanceEmbeddingRefine[GraphData[{"MaximallyLaman",{9,1}},"Graph","3D"]]

3D UnitDistance construction Random

GraphData[{"MaximallyLaman",{9,1}},"Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData[{"MaximallyLaman",{9,1}},"VertexList"],
GraphData[{"MaximallyLaman",{9,1}},"EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

GraphData[{"MaximallyLaman",{9,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyLaman",{9,1}},"Polyhedral"]

GraphData[{"MaximallyLaman",{9,1}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"MaximallyLaman",{9,1}},"Polyhedron"]}]

3D Canonical

GraphData[{"MaximallyLaman",{9,1}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"MaximallyLaman",{9,1}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"MaximallyLaman",{9,1}}],1]}]

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

poly//InputForm

SimplePolyhedronQ[can]

If[%===False,Quit[]]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

3D Canonical construction from PolyhedralEmbedding

g=GraphData[{"MaximallyLaman",{9,1}},"Graph","Planar"][[1]]

Show[g2=PolyhedralEmbedding[g,"Circular"->True,"Scale"->3],Boxed->True]//Quiet

With[
{faces=PlanarFaceList[Graph[EdgeList[g2]]],v=GraphEmbedding@g2},
Graphics3D[{Point[{0,0,0}],Opacity[.5],Sphere[],FaceForm[Green,Red],
poly=Polyhedron[1.2v,faces]}]]

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

{"MaximallyLaman", {10, 1}}

Names

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

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

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"MaximallyLaman",{10,1}},"WikidataID"]

GraphData[{"MaximallyLaman",{10,1}},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

GraphData[{"MaximallyLaman",{10,1}},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

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

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

Embeddings

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

Default embedding

g0=GraphPlot[Graph[GraphData[{"MaximallyLaman",{10,1}},"VertexList"],GraphData[{"MaximallyLaman",{10,1}},"Edges"],GraphLayout->"SpringEmbedding"]]

g=FindCorrespondingGraph[,{{0,0},{1/2,0},{1,0},{1/4,1/3},{1/2,1/3},{3/4,1/3},{1/2,2/3},{0,1},{1/2,1},{1,1}}]

RecognizeGraph@g

Configuration

GraphData[{"MaximallyLaman",{10,1}},"Configuration"]

configurations=GraphData[{"MaximallyLaman",{10,1}},"Graph","Configuration"]//StyleGraphs

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData[{"MaximallyLaman",{10,1}},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"MaximallyLaman",{10,1}},"Bipartite"]

GraphData[{"MaximallyLaman",{10,1}},"Graph","Bipartite"]//StyleGraphs

Bilateral

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

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

Circular

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

Circular construction All

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

GraphData[{"MaximallyLaman",{10,1}},"HamiltonianCycles"]

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

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

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

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

gs=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyLaman",{10,1}}],#]&/@Take[hc,1]

Length[hcsym=SymmetricHamiltonianCycles[GraphData[{"MaximallyLaman",{10,1}}],hc,ProgressReporting->True]]//Timing

groups=GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"MaximallyLaman",{10,1}}],#]&/@hcsym,GraphSymmetryGroup]

gs=Join@@Values[groups]

Planar

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

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

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyLaman",{10,1}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyLaman",{10,1}}]],10]

PlanarGraphEmbeddings

GraphData[{"MaximallyLaman",{10,1}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyLaman",{10,1}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"MaximallyLaman",{10,1}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"MaximallyLaman",{10,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  4 #1

GraphPlot[RotateGraph[,Pi/4]]

v=Join[CirclePoints[{1,Pi/2},4],CirclePoints[1/3,4]];
v=Join[v,Mean[v[[#]]]&/@{{7,8},{5,6}}];
Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph[g]

Tutte embedding construction  4 #2

GraphPlot[RotateGraph[,Pi/2]]

v={{-1,0},{1,0},{-1,2},{1,2},{0,Sqrt[3]}}/2;
v=Join[v,Mean[v[[{5,#}]]]&/@{1,2}];
AppendTo[v,Mean[v[[{6,7}]]]];
s=1/8;
v=Join[v,Threaded[v[[8]]]+{# s,-s Sqrt[3]}&/@{-1,1}];
Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph[g]

Tutte embedding construction  4 #3

GraphPlot[RotateGraph[]]

v=Join[CirclePoints[3],CirclePoints[{0,0},1/3,4]];
AppendTo[v,Mean[v[[{5,6}]]]];
s=1/8;
v=Join[v,Threaded[v[[8]]]+s{#,-Sqrt[3]}&/@{-1,1}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph[g]

MinimalCrossing

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

(gs=GraphData[{"MaximallyLaman",{10,1}},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

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

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

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

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

Circulant

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

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

Circulant construction

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

(ci=CirculantIndices[GraphData[{"MaximallyLaman",{10,1}}]])//AbsoluteTiming

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

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

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

RootGraph

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

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

Halin

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

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

Rigid

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

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

Flexible

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

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

Voltage

GraphData[{"MaximallyLaman",{10,1}},"Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData[{"MaximallyLaman",{10,1}}],"MaxResults"->20,Debug->True]

Length[gs]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{10,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{10,1}},"VertexList"],GraphData[{"MaximallyLaman",{10,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"MaximallyLaman",{10,1}}],50,"ReturnWithMessage"->True];//Quiet//Timing

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

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

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

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

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

Matchstick

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

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

3D default

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

3D construction

g0=GraphData[{"MaximallyLaman",{10,1}}];
a=(2+Sqrt[2])/4;
coords=<|1->{1/2,1,0},2->{1/2,-1,0},3->{-1/2,-1,0},4->{-1/2,1,0},5->{1/2,0,1},6->{-1/2,0,1},7->{0,-a,a},8->{0,a,a},9->{-1/2,0,0},10->{1/2,0,0}|>;

g=Graph3D[VertexList[g0],EdgeList[g0],VertexCoordinates->(coords/@VertexList[g]),VertexLabels->"Name"]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

g0=GraphData[{"MaximallyLaman",{10,1}}];

s=Sqrt[-5/2+2 Sqrt[2]];
a=-1+Sqrt[2]+s;
c=1-Sqrt[2]+s;
h=Sqrt[1/4+1/Sqrt[2]];

coords=<|1->{1/2,a,c},2->{1/2,-a,c},3->{-1/2,-a,c},4->{-1/2,a,c},5->{1/Sqrt[2],0,h},6->{-1/Sqrt[2],0,h},7->{0,-1/Sqrt[2],h},8->{0,1/Sqrt[2],h},9->{-1/2,0,0},10->{1/2,0,0}|>;

Graph3D[VertexList[g0],EdgeList[g0],VertexCoordinates->(coords/@VertexList[g0]),VertexLabels->"Name"]

gs={,};

UnitDistanceGraphEmbeddingQ/@gs

3D All

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

3D UnitDistance construction Random

GraphData[{"MaximallyLaman",{10,1}},"Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData[{"MaximallyLaman",{10,1}},"VertexList"],
GraphData[{"MaximallyLaman",{10,1}},"EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

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

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

Graphics3D[{FaceForm[Green,Red],GraphData[{"MaximallyLaman",{10,1}},"Polyhedron"]}]

3D Canonical

GraphData[{"MaximallyLaman",{10,1}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"MaximallyLaman",{10,1}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"MaximallyLaman",{10,1}}],1]}]

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

can[[1]]//N

SimplePolyhedronQ[can]

If[%===False,Quit[]]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

3D Canonical construction from PolyhedralEmbedding

g=GraphData[{"MaximallyLaman",{10,1}},"Graph","Planar"][[1]]

Show[g2=PolyhedralEmbedding[g,"Circular"->True,"Scale"->3],Boxed->True]//Quiet

With[
{faces=PlanarFaceList[Graph[EdgeList[g2]]],v=GraphEmbedding@g2},
Graphics3D[{Point[{0,0,0}],Opacity[.5],Sphere[],FaceForm[Green,Red],
poly=Polyhedron[1.2v,faces]}]]

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

{"MaximallyLaman", {11, 1}}

Names

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

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

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"MaximallyLaman",{11,1}},"WikidataID"]

GraphData[{"MaximallyLaman",{11,1}},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

GraphData[{"MaximallyLaman",{11,1}},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

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

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

Embeddings

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

Default embedding

g0=RotateGraph[GraphPlot[Graph[GraphData[{"MaximallyLaman",{11,1}},"VertexList"],GraphData[{"MaximallyLaman",{11,1}},"Edges"]]],Pi]

v=Join[CirclePoints[7],CirclePoints[1/2,4]];
g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphPlot@

g=ToGridEmbedding[]

RecognizeGraph@g

Configuration

GraphData[{"MaximallyLaman",{11,1}},"Configuration"]

configurations=GraphData[{"MaximallyLaman",{11,1}},"Graph","Configuration"]//StyleGraphs

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData[{"MaximallyLaman",{11,1}},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"MaximallyLaman",{11,1}},"Bipartite"]

GraphData[{"MaximallyLaman",{11,1}},"Graph","Bipartite"]//StyleGraphs

Bilateral

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

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

Circular

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

Circular construction All

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

GraphData[{"MaximallyLaman",{11,1}},"HamiltonianCycles"]

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

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

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

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

gs=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyLaman",{11,1}}],#]&/@Take[hc,1]

Length[hcsym=SymmetricHamiltonianCycles[GraphData[{"MaximallyLaman",{11,1}}],hc,ProgressReporting->True]]//Timing

groups=GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"MaximallyLaman",{11,1}}],#]&/@hcsym,GraphSymmetryGroup]

gs=Join@@Values[groups]

Planar

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

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

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyLaman",{11,1}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyLaman",{11,1}}]],10]

PlanarGraphEmbeddings

GraphData[{"MaximallyLaman",{11,1}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyLaman",{11,1}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"MaximallyLaman",{11,1}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"MaximallyLaman",{11,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 4 #1

GraphPlot[RotateGraph[,-Pi/4]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph[g]

Tutte embedding construction 4 #2

GraphPlot[RotateGraph[,-Pi/2]]

g=ToGridEmbedding[]

RecognizeGraph[g]

Tutte embedding construction  3

GraphPlot[RotateGraph[,2Pi/3]]

v=Join[{{-1,0},{1,0},{0,Sqrt[3]},{-1/4,1/4},{1/4,1/4}},Subdivide[{-1/3,1/2+1/8},{1/3,1/2+1/8},3],{{0,1},{0,5/4+1/8}}];
Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph[g]

MinimalCrossing

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

(gs=GraphData[{"MaximallyLaman",{11,1}},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

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

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

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

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

Circulant

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

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

Circulant construction

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

(ci=CirculantIndices[GraphData[{"MaximallyLaman",{11,1}}]])//AbsoluteTiming

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

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

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

RootGraph

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

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

Halin

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

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

Rigid

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

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

Flexible

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

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

Voltage

GraphData[{"MaximallyLaman",{11,1}},"Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData[{"MaximallyLaman",{11,1}}],"MaxResults"->20,Debug->True]

Length[gs]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{11,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{11,1}},"VertexList"],GraphData[{"MaximallyLaman",{11,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

g=;

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

//InputForm

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"MaximallyLaman",{11,1}}],50,"ReturnWithMessage"->True];//Quiet//Timing

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

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

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

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

Graph[{1,2,3,4,5,6,7,8,9,10,11},{UndirectedEdge[1,2],UndirectedEdge[1,10],UndirectedEdge[1,11],UndirectedEdge[2,8],UndirectedEdge[2,9],UndirectedEdge[3,7],UndirectedEdge[3,9],UndirectedEdge[3,10],UndirectedEdge[4,7],UndirectedEdge[4,10],UndirectedEdge[4,11],UndirectedEdge[5,7],UndirectedEdge[5,8],UndirectedEdge[5,9],UndirectedEdge[6,7],UndirectedEdge[6,8],UndirectedEdge[6,11],UndirectedEdge[8,11],UndirectedEdge[9,10]},FormatType->TraditionalForm,VertexCoordinates->{{-1/2,0},{1/2,0},{-4/5,3/5+Sqrt[3]/2},{-1/2,6/5},{1/2,6/5},{4/5,3/5+Sqrt[3]/2},{0,6/5+Sqrt[3]/2},{13/10,3/5},{-3/10,3/5},{-13/10,3/5},{3/10,3/5}}]

gs={,RotateGraph[,-Pi/2],}

Matchstick

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

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

3D default

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

3D construction

g0=GraphData[{"MaximallyLaman",{11,1}},"Graph"];

h=Sqrt[3]/2;

coords=<|1->{1/2,0,h},2->{-1/2,0,h},3->{0,-1/2,h},4->{1/2,0,-h},5->{-1/2,0,-h},6->{0,1/2,h},7->{0,0,0},8->{-1/2,1/2,0},9->{-1/2,-1/2,0},10->{1/2,-1/2,0},11->{1/2,1/2,0}|>;

g=Graph3D[VertexList[g0],EdgeList[g0],VertexCoordinates->(VertexList[g0]/. Normal[coords]),VertexLabels->"Name",Boxed->False]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

3D All

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

3D UnitDistance construction Random

GraphData[{"MaximallyLaman",{11,1}},"Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData[{"MaximallyLaman",{11,1}},"VertexList"],
GraphData[{"MaximallyLaman",{11,1}},"EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

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

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

Graphics3D[{FaceForm[Green,Red],GraphData[{"MaximallyLaman",{11,1}},"Polyhedron"]}]

3D Canonical

GraphData[{"MaximallyLaman",{11,1}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"MaximallyLaman",{11,1}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"MaximallyLaman",{11,1}}],1]}]

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

3D Canonical construction from PolyhedralEmbedding

g=GraphData[{"MaximallyLaman",{11,1}},"Graph","Planar"][[1]]

Show[g2=PolyhedralEmbedding[g,"Circular"->True,"Scale"->3],Boxed->True]//Quiet

With[
{faces=PlanarFaceList[Graph[EdgeList[g2]]],v=GraphEmbedding@g2},
Graphics3D[{Point[{0,0,0}],Opacity[.5],Sphere[],FaceForm[Green,Red],
poly=Polyhedron[1.2v,faces]}]]

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

SimplePolyhedronQ[can]

If[%===False,Quit[]]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

{"MaximallyLaman", {12, 1}}

Names

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

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

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"MaximallyLaman",{12,1}},"WikidataID"]

GraphData[{"MaximallyLaman",{12,1}},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

GraphData[{"MaximallyLaman",{12,1}},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

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

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

Embeddings

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

Default embedding

g0=GraphPlot[Graph[GraphData[{"MaximallyLaman",{12,1}},"VertexList"],GraphData[{"MaximallyLaman",{12,1}},"Edges"]]]

Mean[v[[{1,3}]]]

v=Join[CirclePoints[6],CirclePoints[1/2,6]];
Graph[Range@Length@v,{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

DegenerateGraphEmbeddingTypes@g

Configuration

GraphData[{"MaximallyLaman",{12,1}},"Configuration"]

configurations=GraphData[{"MaximallyLaman",{12,1}},"Graph","Configuration"]//StyleGraphs

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData[{"MaximallyLaman",{12,1}},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"MaximallyLaman",{12,1}},"Bipartite"]

GraphData[{"MaximallyLaman",{12,1}},"Graph","Bipartite"]//StyleGraphs

Bilateral

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

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

Circular

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

Circular construction All

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

GraphData[{"MaximallyLaman",{12,1}},"HamiltonianCycles"]

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

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

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

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

gs=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyLaman",{12,1}}],#]&/@Take[hc,1]

Length[hcsym=SymmetricHamiltonianCycles[GraphData[{"MaximallyLaman",{12,1}}],hc,ProgressReporting->True]]//Timing

groups=GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"MaximallyLaman",{12,1}}],#]&/@hcsym,GraphSymmetryGroup]

gs=Join@@Values[groups]

Planar

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

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

MinimalCrossingNumber crossings.uos.de [verified 3]

CrossingNumber[GraphData[{"MaximallyLaman",{12,1}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossing

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

(gs=GraphData[{"MaximallyLaman",{12,1}},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

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

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

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"MaximallyLaman",{12,1}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

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

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

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

Take[diagrams1,UpTo[10]]

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

v=Join[{{-1,0},{1,0},{0,Sqrt[3]}},Subdivide[{-1,1/4},{1,1/4},6][[2;;-2]]];
v=Join[v,Subdivide[{v[[5,1]],3/4},{v[[7,1]],3/4},2],{{0,5/4}}];
Graph[Range@Length@v,{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphCrossingCount@g

GraphCrossingDiagram@g

Rectil

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

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

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"MaximallyLaman",{12,1}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

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

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

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

Take[diagrams1,UpTo[10]]

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

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

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"MaximallyLaman",{12,1}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

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

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

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

Take[diagrams1,UpTo[10]]

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

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

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 1k [old]

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k [old]

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

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

Circulant

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

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

Circulant construction

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

(ci=CirculantIndices[GraphData[{"MaximallyLaman",{12,1}}]])//AbsoluteTiming

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

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

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

RootGraph

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

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

Halin

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

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

Rigid

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

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

Flexible

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

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

Voltage

GraphData[{"MaximallyLaman",{12,1}},"Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData[{"MaximallyLaman",{12,1}}],"MaxResults"->20,Debug->True]

Length[gs]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{12,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{12,1}},"VertexList"],GraphData[{"MaximallyLaman",{12,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"MaximallyLaman",{12,1}}],50,"ReturnWithMessage"->True];//Quiet//Timing

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

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

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

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

Matchstick

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

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

3D default

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

3D construction

3D All

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

3D UnitDistance from refinement

UnitDistanceEmbeddingRefine[Graph3D[GraphData[{"MaximallyLaman",{12,1}},"Edges"]]]

3D UnitDistance construction Random

GraphData[{"MaximallyLaman",{12,1}},"Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData[{"MaximallyLaman",{12,1}},"VertexList"],
GraphData[{"MaximallyLaman",{12,1}},"EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

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

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

{"MaximallyLaman", {13, 1}}

Names

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

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

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"MaximallyLaman",{13,1}},"WikidataID"]

GraphData[{"MaximallyLaman",{13,1}},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

GraphData[{"MaximallyLaman",{13,1}},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

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

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

Embeddings

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

Default embedding

g0=GraphPlot[Graph[GraphData[{"MaximallyLaman",{13,1}},"VertexList"],GraphData[{"MaximallyLaman",{13,1}},"Edges"]]]

Configuration

GraphData[{"MaximallyLaman",{13,1}},"Configuration"]

configurations=GraphData[{"MaximallyLaman",{13,1}},"Graph","Configuration"]//StyleGraphs

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData[{"MaximallyLaman",{13,1}},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"MaximallyLaman",{13,1}},"Bipartite"]

GraphData[{"MaximallyLaman",{13,1}},"Graph","Bipartite"]//StyleGraphs

Bilateral

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

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

Circular

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

Circular construction All

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

GraphData[{"MaximallyLaman",{13,1}},"HamiltonianCycles"]

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

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

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

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

gs=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyLaman",{13,1}}],#]&/@Take[hc,1]

Length[hcsym=SymmetricHamiltonianCycles[GraphData[{"MaximallyLaman",{13,1}}],hc,ProgressReporting->True]]//Timing

groups=GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"MaximallyLaman",{13,1}}],#]&/@hcsym,GraphSymmetryGroup]

gs=Join@@Values[groups]

Planar

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

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

MinimalCrossingNumber crossings.uos.de [verified 4]

CrossingNumber[GraphData[{"MaximallyLaman",{13,1}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossing

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

(gs=GraphData[{"MaximallyLaman",{13,1}},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

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

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

MinimalCrossing construction Random 1k [97 s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"MaximallyLaman",{13,1}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

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

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

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

Take[diagrams1,UpTo[10]]

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

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

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [469 s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"MaximallyLaman",{13,1}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

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

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

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

Take[diagrams1,UpTo[10]]

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

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

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [1988 s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"MaximallyLaman",{13,1}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

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

Take[diagrams0,UpTo[10]]

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

g=GraphicsToGraph@

g=ToGridEmbedding[]

RecognizeGraph@g

GraphCrossingCount@g

One crossing point on the boundary:

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

Take[diagrams1,UpTo[10]]

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

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

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 1k [old]

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k [old]

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

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

MinimaRectilinearlLocalCrossing construction 1000

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

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

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

MinimaRectilinearlLocalCrossing construction 20000

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

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

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

Circulant

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

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

Circulant construction

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

(ci=CirculantIndices[GraphData[{"MaximallyLaman",{13,1}}]])//AbsoluteTiming

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

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

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

RootGraph

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

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

Halin

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

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

Rigid

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

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

Flexible

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

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

Voltage

GraphData[{"MaximallyLaman",{13,1}},"Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData[{"MaximallyLaman",{13,1}}],"MaxResults"->20,Debug->True]

Length[gs]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{13,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{13,1}},"VertexList"],GraphData[{"MaximallyLaman",{13,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"MaximallyLaman",{13,1}}],50,"ReturnWithMessage"->True];//Quiet//Timing

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

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

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

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

Matchstick

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

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

3D default

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

3D construction

3D All

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

3D UnitDistance construction Random

GraphData[{"MaximallyLaman",{13,1}},"Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData[{"MaximallyLaman",{13,1}},"VertexList"],
GraphData[{"MaximallyLaman",{13,1}},"EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

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

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

{"MaximallyLaman", {14, 1}}

Names

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

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

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"MaximallyLaman",{14,1}},"WikidataID"]

GraphData[{"MaximallyLaman",{14,1}},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

GraphData[{"MaximallyLaman",{14,1}},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

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

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

Embeddings

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

Default embedding

g0=GraphPlot[Graph[GraphData[{"MaximallyLaman",{14,1}},"VertexList"],GraphData[{"MaximallyLaman",{14,1}},"Edges"]]]

Configuration

GraphData[{"MaximallyLaman",{14,1}},"Configuration"]

configurations=GraphData[{"MaximallyLaman",{14,1}},"Graph","Configuration"]//StyleGraphs

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData[{"MaximallyLaman",{14,1}},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"MaximallyLaman",{14,1}},"Bipartite"]

GraphData[{"MaximallyLaman",{14,1}},"Graph","Bipartite"]//StyleGraphs

Bilateral

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

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

Circular

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

Circular construction All

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

GraphData[{"MaximallyLaman",{14,1}},"HamiltonianCycles"]

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

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

GraphData[{"MaximallyLaman",{14,1}},"LCFSignature"]

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

gs=CircularEmbeddingFromHamiltonianCycle[GraphData[{"MaximallyLaman",{14,1}}],#]&/@Take[hc,1]

Length[hcsym=SymmetricHamiltonianCycles[GraphData[{"MaximallyLaman",{14,1}}],hc,ProgressReporting->True]]//Timing

groups=GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"MaximallyLaman",{14,1}}],#]&/@hcsym,GraphSymmetryGroup]

gs=Join@@Values[groups]

Planar

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

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

MinimalCrossingNumber crossings.uos.de [verified 7]

CrossingNumber[GraphData[{"MaximallyLaman",{14,1}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossing

GraphData[{"MaximallyLaman",{14,1}},"CN"]

(gs=GraphData[{"MaximallyLaman",{14,1}},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"MaximallyLaman",{14,1}},"RCN"]

GraphData[{"MaximallyLaman",{14,1}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [100 s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"MaximallyLaman",{14,1}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

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

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

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

Take[diagrams1,UpTo[10]]

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

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

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

g=RotateGraph[,-Pi/2]

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

g=ScaleGraph@GraphicsToGraph@

GraphCrossingCount@g

GraphPlot@

GraphPlot@ScaleGraph@GraphicsToGraph@

g=ToGridEmbedding@

GraphCrossingCount@g

GraphCrossingDiagram@g

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"MaximallyLaman",{14,1}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

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

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

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

Take[diagrams1,UpTo[10]]

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

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

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"MaximallyLaman",{14,1}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

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

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

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

Take[diagrams1,UpTo[10]]

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

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

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 1k [old]

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k [old]

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

GraphData[{"MaximallyLaman",{14,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyLaman",{14,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyLaman",{14,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyLaman",{14,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction 1000

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

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

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

MinimaRectilinearlLocalCrossing construction 20000

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

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

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

Circulant

GraphData[{"MaximallyLaman",{14,1}},"Circulant"]

GraphData[{"MaximallyLaman",{14,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyLaman",{14,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyLaman",{14,1}}]])//AbsoluteTiming

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyLaman",{14,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyLaman",{14,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"MaximallyLaman",{14,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyLaman",{14,1}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"MaximallyLaman",{14,1}}]]

Halin

GraphData[{"MaximallyLaman",{14,1}},"Halin"]

GraphData[{"MaximallyLaman",{14,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyLaman",{14,1}},"Rigid"]

GraphData[{"MaximallyLaman",{14,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyLaman",{14,1}},"Flexible"]

GraphData[{"MaximallyLaman",{14,1}},"Graph","Flexible"]//StyleGraphs

Voltage

GraphData[{"MaximallyLaman",{14,1}},"Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData[{"MaximallyLaman",{14,1}}],"MaxResults"->20,Debug->True]

Length[gs]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF

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

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

GraphData[{"MaximallyLaman",{14,1}},"LCFSignature"]

GraphData[{"MaximallyLaman",{14,1}},"LCFNotations"]

GraphData[{"MaximallyLaman",{14,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"MaximallyLaman",{14,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyLaman",{14,1}}],Debug->True]//Timing

GraphData[{"MaximallyLaman",{14,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{14,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyLaman",{14,1}},"VertexList"],GraphData[{"MaximallyLaman",{14,1}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"MaximallyLaman",{14,1}}],50,"ReturnWithMessage"->True];//Quiet//Timing

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

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

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

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

FindUnitDistanceEmbedding[GraphData[{"MaximallyLaman",{14,1}}],"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

Matchstick

GraphData[{"MaximallyLaman",{14,1}},"Matchstick"]

GraphData[{"MaximallyLaman",{14,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyLaman",{14,1}},"Edges"]]

3D construction

3D All

GraphData[{"MaximallyLaman",{14,1}},"Graph",{"3D","All"}]

3D UnitDistance construction Random

GraphData[{"MaximallyLaman",{14,1}},"Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData[{"MaximallyLaman",{14,1}},"VertexList"],
GraphData[{"MaximallyLaman",{14,1}},"EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

GraphData[{"MaximallyLaman",{14,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyLaman",{14,1}},"Polyhedral"]

GraphData[{"MaximallyLaman",{14,1}},"Graph",{"3D","Polyhedron"}]

GraphData

AddIndexedClass

rules=Rule[#3,#]&@@@DeleteCases[MaximallyLamanGraphs,{_,_,{}}]

AddIndexedClass["MaximallyLaman",rules,"15.1","AddClass"->False]

RenameGraphFiles[]

GraphDataString

new=DeleteCases[MaximallyLamanGraphs,{_,_,_?DataPaclets`GraphDataDump`MyGraphQ}]

<<MathWorld`Graphs`

stream=OpenWrite["~/maximally-laman.m"]

WriteString[
stream,
GraphDataString[
#2,
"StandardName"->{"MaximallyLaman",#},
"Name"->ToString[#[[1]]]<>"\[Hyphen]mximally Laman graph "<>ToString[#[[2]]],
"Information"->"LamanNumber"
]
]&@@@new;