Uniquely Graceful Graph

Author

Eric W. Weisstein
December 31, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/UniquelyGracefulGraph.nb.

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

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

Source

Knuth, D.E.  Problem 97 in The Art of Computer Programing, Vol. 4, Pre-Fascicle 7A, §7.2.2.3, pp. 121 and , 2024.

A002494 (simple graphs with no isolated points)

1, 2, 7, 23, 122, 888, 11302

XXX (distinct graceful labelings for n-node graphs)

1, 2, 13, 157, 3292

A not necessarily connected (isolated points allowed)

(uniquelygraceful=Table[Select[GraphData[n],GraphData[#,"GracefulLabelingCount"]===1&],{n,8}])//Column

Length/@uniquelygraceful

fundcounts=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","GracefulLabelingCount","GracefulLabelingCount_0"<>ToString[n]<>".m"}]],{n,8}];

A379574

Count[#,1]&/@fundcounts

UniquelyGracefulRules=Flatten[MapIndexed[
Rule[RecognizeGraph[#],#2]&,
Table[Graphs[n][[Position[fundcounts[[n]],1]//Flatten]],{n,7}],
{2}],1]

AddIndexedClass["UniquelyGraceful",UniquelyGracefulRules,"14.3"]

RenameGraphFiles[]

uniq8=Graphs[8][[Position[fundcounts[[8]],1]//Flatten]]

all=MapIndexed[{{8,#2[[1]]},#,RecognizeGraph[#]}&,uniq8]

ingraphdata=Select[all,DataPaclets`GraphDataDump`MyGraphQ[#[[-1]]]&]

UniquelyGracefulRules8=Rule[#3,#]&@@@ingraphdata

AddIndexedClass["UniquelyGraceful",UniquelyGracefulRules8,"14.3"]

RenameGraphFiles[]

notingraphdata=Append[#,RecognizeGraph/@ConnectedGraphComponents[#[[2]]]]&/@Select[all,!DataPaclets`GraphDataDump`MyGraphQ[#[[-1]]]&]

AddToGraphData={{{8,2},,{8,161},"K1,3+Paw"},{{8,3},,{8,929},"Diamond+2P2"},{{8,4},,{8,959},"Paw+C3+K1"},{{8,5},,{8,962},"K4+P2+2K1"},{{8,6},,{8,966},"Barbell3+2K1"},{{8,7},,{8,1270},"C6+P2"},{{8,9},,{8,2177},"K4+K1,3"},{{8,11},,{8,5622},{"UniquelyGraceful",{8,11}}},{{8,13},,{8,5633},"K4+2P2"},{{8,14},,{8,5746},{"UniquelyGraceful",{8,14}}},{{8,15},,{8,5750},"Lollipop41+C3"},{{8,16},,{8,7410},{"UniquelyGraceful",{8,16}}},{{8,17},,{8,8746},{"UniquelyGraceful",{8,17}}},{{8,20},,{8,9025},{"UniquelyGraceful",{8,20}}},{{8,21},,{8,11549},{"UniquelyGraceful",{8,21}}},{{8,23},,{8,11722},{"UniquelyGraceful",{8,23}}},{{8,25},,{8,11787},{"UniquelyGraceful",{8,25}}},{{8,26},,{8,11840},{"UniquelyGraceful",{8,26}}},{{8,27},,{8,12046},{"UniquelyGraceful",{8,27}}},{{8,28},,{8,12116},{"UniquelyGraceful",{8,28}}},{{8,30},,{8,12178},{"UniquelyGraceful",{8,30}}},{{8,31},,{8,12188},{"UniquelyGraceful",{8,31}}},{{8,32},,{8,12218},{"UniquelyGraceful",{8,32}}},{{8,33},,{8,12219},{"UniquelyGraceful",{8,33}}}};

No isolated points

Knuth 2024

(uniquelygracefulnoisiolatedpoints=Table[Select[GraphData["UniquelyGraceful",n],GraphData[#,"MinimumVertexDegree"]>0&],{n,8}])//Column

Length/@uniquelygracefulnoisiolatedpoints

A379572

fundcounts=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","GracefulLabelingCount","GracefulLabelingCount_0"<>ToString[n]<>".m"}]],{n,8}];

mindegrees=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","MinimumVertexDegree","MinimumVertexDegree_0"<>ToString[n]<>".m"}]],{n,8}];

NoIsolatedPointPositions=Table[Flatten@Position[mindegrees[[n]],_Integer?Positive],{n,8}];

Table[Count[fundcounts[[n]][[NoIsolatedPointPositions[[n]]]],1],{n,8}]

1

GraphData["UniquelyGraceful",1]

2

GraphData["UniquelyGraceful",2]

3

GraphData["UniquelyGraceful",3]

4

GraphData["UniquelyGraceful",4]

5

Select[GraphData["Graceful",5],GraphData[#,"GracefulLabelingCount"]==1&]

6

Select[GraphData["Graceful",6],GraphData[#,"GracefulLabelingCount"]==1&]

7

GraphData["C3+K4-e","StandardNames"]

GraphDisjointUnion[GraphData["K1,1,2"],GraphData["K3"]]//RecognizeGraph

GraphData["C3+K4-e"]

GraphData[{7,992}]

Select[GraphData["Graceful",7],GraphData[#,"GracefulLabelingCount"]==1&]

8

uniq8=GraphData["UniquelyGraceful",8]

GraphData[#,"GracefulLabelingCount"]&/@uniq8

todo=Select[uniq8,!ListQ@GraphData[#,"GracefulLabelings"]&]

Print[{#,SymmetricallyDistinctLabelings[GraphData[#],{FindGracefulLabeling[GraphData[#]]},"AdditivelyConjugateEquivalent"->True]//Timing}]&/@todo;

rules=Rule[#,{1,#2[[2]]}]&@@@{{"Barbell3+2K1",{0.003871`,{{0,2,1,4,5,3,7,6}}}},{"C6+P2",{0.019272`,{{1,0,2,3,5,7,6,4}}}},{"Diamond+2P2",{0.024801`,{{1,3,0,2,4,5,6,7}}}},{"K1,3+Paw",{0.007334`,{{0,3,4,5,2,6,1,7}}}},{"K4+2P2",{0.397653`,{{0,1,3,2,5,6,7,8}}}},{"K4+K1,3",{1.410296`,{{0,3,4,5,1,7,8,9}}}},{"K4+P2+2K1",{0.001937`,{{0,1,3,5,2,4,6,7}}}},{"Lollipop41+C3",{2.327472`,{{0,1,2,6,3,9,8,10}}}},{"Paw+C3+K1",{0.023439`,{{1,2,6,3,4,7,5,0}}}},{{"UniquelyGraceful",{8,11}},{163.146029`,{{0,1,2,17,8,15,12,18}}}},{{"UniquelyGraceful",{8,14}},{28.929144`,{{0,2,5,11,9,13,14,15}}}},{{"UniquelyGraceful",{8,16}},{589.305093`,{{1,5,8,4,11,0,18,20}}}},{{"UniquelyGraceful",{8,17}},{1249.879362`,{{2,7,15,12,4,0,20,21}}}},{{"UniquelyGraceful",{8,20}},{291.899359`,{{0,1,2,9,21,7,17,20}}}},{{"UniquelyGraceful",{8,21}},{67.400446`,{{1,2,3,8,13,0,18,22}}}},{{"UniquelyGraceful",{8,23}},{30.686289`,{{2,0,7,1,5,10,13,14}}}},{{"UniquelyGraceful",{8,25}},{352.121153`,{{1,0,5,9,13,18,16,19}}}},{{"UniquelyGraceful",{8,26}},{153.46577`,{{0,3,1,8,15,10,16,12}}}},{{"UniquelyGraceful",{8,27}},{339.056773`,{{3,5,9,19,13,20,21,0}}}},{{"UniquelyGraceful",{8,28}},{754.910348`,{{1,0,21,17,22,3,6,13}}}},{{"UniquelyGraceful",{8,30}},{1542.44617`,{{4,2,12,16,15,22,0,21}}}},{{"UniquelyGraceful",{8,31}},{264.956363`,{{0,1,8,2,11,20,17,15}}}},{{"UniquelyGraceful",{8,32}},{569.436006`,{{0,6,3,9,21,1,16,20}}}},{{"UniquelyGraceful",{8,33}},{991.595975`,{{0,10,2,8,18,17,22,21}}}}}

Connected

(uniquelygracefulconnected=Table[GraphData[{"UniquelyGraceful","Connected"},n],{n,8}])//Column

fundcounts=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","GracefulLabelingCount","GracefulLabelingCount_0"<>ToString[n]<>".m"}]][[ConnectedGraphIndices[n]]],{n,8}];

A379573

Count[#,1]&/@fundcounts

Classes that are Class

<<MathWorld`Graphs`

GraphClassesThatAre["UniquelyGraceful"]

Intersection@@(GraphData[#,"Classes"]&/@GraphData["UniquelyGraceful"])

Counts

allcounts=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","AllGracefulLabelingCount","GracefulLabelingCount_0"<>ToString[n]<>".m"}]],{n,8}];

fundcounts=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","GracefulLabelingCount","GracefulLabelingCount_0"<>ToString[n]<>".m"}]],{n,8}];

Uniquely graceful (not necessarily connected)

A379574

Count[#,1]&/@fundcounts

Length/@Table[Select[GraphData["Graceful",n],GraphData[#,"GracefulLabelingCount"]==1&],{n,7}]

Uniquely graceful connected

A379573

Table[Count[fundcounts[[n]][[ConnectedGraphIndices[n]]],1],{n,8}]

Length/@Table[Select[GraphData[{"Connected","Graceful"},n],GraphData[#,"GracefulLabelingCount"]==1&],{n,7}]

Uniquely graceful no isolated points

mindegrees=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","MinimumVertexDegree","MinimumVertexDegree_0"<>ToString[n]<>".m"}]],{n,8}];

NoIsolatedPointPositions=Table[Flatten@Position[mindegrees[[n]],_Integer?Positive],{n,8}];

A379572

Table[Count[fundcounts[[n]][[NoIsolatedPointPositions[[n]]]],1],{n,8}]

Length/@Table[Select[GraphData["Graceful",n],GraphData[#,"GracefulLabelingCount"]==1&&GraphData[#,"MinimumVertexDegree"]>0&],{n,7}]

Knuth 2024

D. E. Knuth, The Art of Computer Programming, Section 7.2.2.3, in preparation.

Figure

TextGrid[Table[{n,GraphData["UniquelyGraceful",n]},{n,8}],Dividers->All]

bug(454882): GraphicsGrid's fail to display thin graphs, change widths of columns and rows, display grid element content suboptimally, etc. starting in V14.1

GraphGraphicsGrid[Table[SortBy[GraphData["UniquelyGraceful",n],GraphData[#,"M"]&],{n,7}],Automatic,8]

$Version

GraphGraphicsGrid[Table[SortBy[Select[GraphData["Graceful",n],GraphData[#,"GracefulLabelingCount"]==1&],GraphData[#,"M"]&],{n,7}],Automatic,6,Alignment->Top]

Embeddings

<<MathWorld`Graphs`

{"UniquelyGraceful", {1, 1}} == "SingletonGraph"

Names

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

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

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

Names

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

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

{"UniquelyGraceful", {3, 1}} == {"Path", 3}

Names

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

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

{"UniquelyGraceful", {3, 2}} == "TriangleGraph"

Names

GraphData[{"UniquelyGraceful",{3,2}},"StandardName"]

GraphData[{"UniquelyGraceful",{3,2}},"StandardNames"]

{"UniquelyGraceful", {4, 1}} == "ClawGraph"

Names

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

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

{"UniquelyGraceful", {4, 2}} == "C3+K1"

Names

GraphData[{"UniquelyGraceful",{4,2}},"StandardName"]

GraphData[{"UniquelyGraceful",{4,2}},"StandardNames"]

{"UniquelyGraceful", {4, 3}} == {"Path", 4}

Names

GraphData[{"UniquelyGraceful",{4,3}},"StandardName"]

GraphData[{"UniquelyGraceful",{4,3}},"StandardNames"]

{"UniquelyGraceful", {4, 4}} == "SquareGraph"

Names

GraphData[{"UniquelyGraceful",{4,4}},"StandardName"]

GraphData[{"UniquelyGraceful",{4,4}},"StandardNames"]

{"UniquelyGraceful", {4, 5}} == "TetrahedralGraph"

Names

GraphData[{"UniquelyGraceful",{4,5}},"StandardName"]

GraphData[{"UniquelyGraceful",{4,5}},"StandardNames"]

{"UniquelyGraceful", {5, 1}} == {"Star", 5}

Names

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

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

{"UniquelyGraceful", {5, 2}} == "C4+K1"

Names

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

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

{"UniquelyGraceful", {6, 1}} == {"Star", 6}

Names

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

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

{"UniquelyGraceful", {6, 2}} == "UtilityGraph"

Names

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

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

{"UniquelyGraceful", {6, 3}} == "P2+K4"

Names

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

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

{"UniquelyGraceful", {6, 4}} == {"Barbell", 3}

Names

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

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

{"UniquelyGraceful", {6, 5}} == "OctahedralGraph"

Names

GraphData[{"UniquelyGraceful",{6,5}},"StandardName"]

GraphData[{"UniquelyGraceful",{6,5}},"StandardNames"]

{"UniquelyGraceful", {7, 1}} == {"Star", 7}

Names

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

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

{"UniquelyGraceful", {7, 2}} == "K4+3K1"

Names

GraphData[{"UniquelyGraceful",{7,2}},"StandardName"]

GraphData[{"UniquelyGraceful",{7,2}},"StandardNames"]

{"UniquelyGraceful", {7, 3}} == "C4+P3"

Names

GraphData[{"UniquelyGraceful",{7,3}},"StandardName"]

GraphData[{"UniquelyGraceful",{7,3}},"StandardNames"]

{"UniquelyGraceful", {7, 4}} == "Tadpole3,2+P2"

Names

GraphData[{"UniquelyGraceful",{7,4}},"StandardName"]

GraphData[{"UniquelyGraceful",{7,4}},"StandardNames"]

{"UniquelyGraceful", {7, 5}} == "Paw+C3"

Names

GraphData[{"UniquelyGraceful",{7,5}},"StandardName"]

GraphData[{"UniquelyGraceful",{7,5}},"StandardNames"]

{"UniquelyGraceful", {7, 6}} == "C3+P4"

Names

GraphData[{"UniquelyGraceful",{7,6}},"StandardName"]

GraphData[{"UniquelyGraceful",{7,6}},"StandardNames"]

{"UniquelyGraceful", {7, 7}} == "C4+C3"

Names

GraphData[{"UniquelyGraceful",{7,7}},"StandardName"]

GraphData[{"UniquelyGraceful",{7,7}},"StandardNames"]

{"UniquelyGraceful", {7, 8}} == "C3+K4-e"

Names

GraphData[{"UniquelyGraceful",{7,8}},"StandardName"]

GraphData[{"UniquelyGraceful",{7,8}},"StandardNames"]

{"UniquelyGraceful", {7, 9}} == "P3+K4"

Names

GraphData[{"UniquelyGraceful",{7,9}},"StandardName"]

GraphData[{"UniquelyGraceful",{7,9}},"StandardNames"]

{"UniquelyGraceful", {7, 10}} == "P2+K5"

Names

GraphData[{"UniquelyGraceful",{7,10}},"StandardName"]

GraphData[{"UniquelyGraceful",{7,10}},"StandardNames"]

{"UniquelyGraceful", {7, 11}} == {7, 992}

Names

GraphData[{"UniquelyGraceful",{7,11}},"StandardName"]

GraphData[{"UniquelyGraceful",{7,11}},"StandardNames"]

{"UniquelyGraceful", {8, 1}} == {"Star", 8}

Names

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

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

{"UniquelyGraceful", {8, 2}} == "K1,3+Paw"

Names

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

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

{"UniquelyGraceful", {8, 3}} == "Diamond+2P2"

Names

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

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

{"UniquelyGraceful", {8, 4}} == "Paw+C3+K1"

Names

GraphData[{"UniquelyGraceful",{8,4}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,4}},"StandardNames"]

{"UniquelyGraceful", {8, 5}} == "K4+P2+2K1"

Names

GraphData[{"UniquelyGraceful",{8,5}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,5}},"StandardNames"]

{"UniquelyGraceful", {8, 6}} == "Barbell3+2K1"

Names

GraphData[{"UniquelyGraceful",{8,6}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,6}},"StandardNames"]

{"UniquelyGraceful", {8, 7}} == "C6+P2"

Names

GraphData[{"UniquelyGraceful",{8,7}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,7}},"StandardNames"]

{"UniquelyGraceful", {8, 8}} == "C4+C3+K1"

Names

GraphData[{"UniquelyGraceful",{8,8}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,8}},"StandardNames"]

{"UniquelyGraceful", {8, 9}} == "K4+K1,3"

Names

GraphData[{"UniquelyGraceful",{8,9}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,9}},"StandardNames"]

{"UniquelyGraceful", {8, 10}} == "C5+P3"

Names

GraphData[{"UniquelyGraceful",{8,10}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,10}},"StandardNames"]

{"UniquelyGraceful", {8, 11}}

Names

GraphData[{"UniquelyGraceful",{8,11}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,11}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,11}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,11}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,11}},"VertexList"],GraphData[{"UniquelyGraceful",{8,11}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,11}},"VertexList"],GraphData[{"UniquelyGraceful",{8,11}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]]

GraphPlot@RotateGraph[GraphicsToGraph@,-.6]

g=RotateGraph[FindCorrespondingGraph[,Join[CirclePoints[4],CirclePoints[1/2,4]]],-Pi/4]

RecognizeGraph@g

BilateralGraphEmbeddingQ@g

gs={,,,};

Degenerate

GraphData[{"UniquelyGraceful",{8,11}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,11}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,11}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,11}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,11}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,11}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,11}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,11}},"LCF"]

GraphData[{"UniquelyGraceful",{8,11}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,11}},"Planar"]

GraphData[{"UniquelyGraceful",{8,11}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,11}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,11}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,11}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,11}}],TimeConstraint->3600])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,11}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,11}},"V"]&]

GraphPlot@RotateGraph[,2Pi/3]

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

RecognizeGraph@g

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,11}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

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

GraphPlot@

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

RecognizeGraph@g

GraphPlot@RotateGraph[,-Pi/2]

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

RecognizeGraph[g]

gs=UnlabelGraph/@{,,}

RectilinearCrossingCount/@gs

RectilinearLocalCrossingCount/@gs

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,11}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,11}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,11}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,11}},"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[{"UniquelyGraceful",{8,11}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,11}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,11}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,11}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,11}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,11}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,11}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,11}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,11}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,11}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,11}},"Halin"]

GraphData[{"UniquelyGraceful",{8,11}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,11}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,11}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,11}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,11}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,11}},"LCF"]

GraphData[{"UniquelyGraceful",{8,11}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,11}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,11}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,11}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,11}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,11}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,11}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,11}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,11}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,11}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,11}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 12}} == "C3+P5"

Names

GraphData[{"UniquelyGraceful",{8,12}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,12}},"StandardNames"]

{"UniquelyGraceful", {8, 13}} == "K4+2P2"

Names

GraphData[{"UniquelyGraceful",{8,13}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,13}},"StandardNames"]

{"UniquelyGraceful", {8, 14}}

Names

GraphData[{"UniquelyGraceful",{8,14}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,14}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,14}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,14}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,14}},"VertexList"],GraphData[{"UniquelyGraceful",{8,14}},"Edges"]]]

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

RecognizeGraph@g

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,14}},"VertexList"],GraphData[{"UniquelyGraceful",{8,14}},"Edges"],GraphLayout->"TutteEmbedding"]]

GraphReplot@

v=Join[{{-1,0},{1,0}},Subdivide[{0,-1},{0,1},5]];
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphPlot@

v={{-1,0},{1,0},{0,Sqrt[3]},{-1/2,1/4},{0,1/4},{1/2,1/4},{-1/4,1/4+Sqrt[3]/4},{1/4,1/4+Sqrt[3]/4}};

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"UniquelyGraceful",{8,14}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,14}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,14}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,14}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,14}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,14}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,14}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,14}},"LCF"]

GraphData[{"UniquelyGraceful",{8,14}},"HamiltonianCycleCount"]

Planar

GraphData[{"UniquelyGraceful",{8,14}},"Planar"]

GraphData[{"UniquelyGraceful",{8,14}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"UniquelyGraceful",{8,14}}]],10]

PlanarGraphEmbeddings

GraphData[{"UniquelyGraceful",{8,14}},"PlanarEmbeddingCount"]

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

Length[plemb]

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,14}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,14}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,14}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,14}}],TimeConstraint->3600])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,14}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

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

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,14}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,14}},"V"]&]

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,14}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"UniquelyGraceful",{8,14}},"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[{"UniquelyGraceful",{8,14}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,14}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,14}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,14}},"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[{"UniquelyGraceful",{8,14}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,14}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,14}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,14}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,14}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,14}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,14}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,14}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,14}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,14}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,14}},"Halin"]

GraphData[{"UniquelyGraceful",{8,14}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,14}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,14}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,14}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,14}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,14}},"LCF"]

GraphData[{"UniquelyGraceful",{8,14}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,14}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,14}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,14}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,14}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,14}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,14}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,14}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,14}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,14}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,14}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 15}} == "Lollipop41+C3"

Names

GraphData[{"UniquelyGraceful",{8,15}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,15}},"StandardNames"]

{"UniquelyGraceful", {8, 16}}

Names

GraphData[{"UniquelyGraceful",{8,16}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,16}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,16}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,16}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,16}},"VertexList"],GraphData[{"UniquelyGraceful",{8,16}},"Edges"]]]

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

RecognizeGraph@g

gs={,,};

Degenerate

GraphData[{"UniquelyGraceful",{8,16}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,16}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,16}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,16}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,16}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,16}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,16}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,16}},"LCF"]

GraphData[{"UniquelyGraceful",{8,16}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,16}},"Planar"]

GraphData[{"UniquelyGraceful",{8,16}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,16}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,16}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,16}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,16}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,16}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,16}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,16}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,16}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,16}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,16}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,16}},"V"]&]

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,16}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

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

GraphPlot@RotateGraph[,-4Pi/5]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,16}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,16}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,16}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,16}},"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[{"UniquelyGraceful",{8,16}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,16}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,16}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,16}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,16}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,16}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,16}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,16}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,16}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,16}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,16}},"Halin"]

GraphData[{"UniquelyGraceful",{8,16}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,16}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,16}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,16}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,16}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,16}},"LCF"]

GraphData[{"UniquelyGraceful",{8,16}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,16}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,16}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,16}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,16}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,16}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,16}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

GraphPlot@

v={{0,0},{1/2,0},{1,0},{1,1},{1/2,1},{0,1},{3/8,1/2},{5/8,1/2}};

FindCorrespondingGraph[,v]

RecognizeGraph@%

UnitDistance by FindUnitDistanceEmbedding

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

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

GraphPlot@RotateGraph[,{8,7}]

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

RecognizeGraph@g

Matchstick

GraphData[{"UniquelyGraceful",{8,16}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,16}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,16}},"Edges"],GraphLayout->"SpringEmbedding"]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,16}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 17}}

Names

GraphData[{"UniquelyGraceful",{8,17}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,17}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,17}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,17}}]]

Default embedding

GraphPlot[RotateGraph[Graph[GraphData[{"UniquelyGraceful",{8,17}},"VertexList"],GraphData[{"UniquelyGraceful",{8,17}},"Edges"]],Pi/2]]

v={#,#2/2}&@@@{{0,0},{1,0},{0,1},{1,1},{0,2},{1/2,2},{1,2},{1/2,3/4}};
g=FindCorrespondingGraph[,v]

RecognizeGraph@g

g=FindCorrespondingGraph[,Join[CirclePoints[7],{{0,0}}]]//Quiet

RecognizeGraph@g

gs={,}

RecognizeGraph/@gs

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

RecognizeGraph@g

Degenerate

GraphData[{"UniquelyGraceful",{8,17}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,17}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,17}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,17}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,17}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,17}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,17}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,17}},"LCF"]

GraphData[{"UniquelyGraceful",{8,17}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,17}},"Planar"]

GraphData[{"UniquelyGraceful",{8,17}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,17}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,17}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,17}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,17}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,17}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,17}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,17}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,17}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,17}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,17}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,17}},"V"]&]

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,17}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

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

GraphPlot@RotateGraph[,-Pi/2]

GraphReplot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

gs={,};

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,17}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,17}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,17}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,17}},"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[{"UniquelyGraceful",{8,17}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,17}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,17}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,17}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,17}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,17}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,17}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"UniquelyGraceful",{8,17}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,17}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,17}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,17}},"Halin"]

GraphData[{"UniquelyGraceful",{8,17}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,17}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,17}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,17}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,17}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,17}},"LCF"]

GraphData[{"UniquelyGraceful",{8,17}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,17}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,17}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,17}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,17}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,17}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,17}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,17}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,17}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,17}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,17}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 18}} == "Dipyramid3+C3"

Names

GraphData[{"UniquelyGraceful",{8,18}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,18}},"StandardNames"]

{"UniquelyGraceful", {8, 19}} == "P3+K5"

Names

GraphData[{"UniquelyGraceful",{8,19}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,19}},"StandardNames"]

{"UniquelyGraceful", {8, 20}}

Names

GraphData[{"UniquelyGraceful",{8,20}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,20}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,20}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,20}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,20}},"VertexList"],GraphData[{"UniquelyGraceful",{8,20}},"Edges"]]]

v={{0,0},{1/2,0},{1,0},{3/8,1/2},{5/8,1/2},{0,1},{1/2,1},{1,1}};
g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs={,};

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,20}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,20}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,20}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,20}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,20}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,20}},"LCF"]

GraphData[{"UniquelyGraceful",{8,20}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,20}},"Planar"]

GraphData[{"UniquelyGraceful",{8,20}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,20}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,20}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,20}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,20}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,20}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,20}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,20}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,20}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,20}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,20}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,20}},"V"]&]

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,20}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

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

GraphPlot@RotateGraph[,-Pi/2]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,20}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,20}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,20}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,20}},"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[{"UniquelyGraceful",{8,20}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,20}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,20}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,20}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,20}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,20}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,20}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,20}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,20}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,20}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,20}},"Halin"]

GraphData[{"UniquelyGraceful",{8,20}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,20}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,20}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,20}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,20}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,20}},"LCF"]

GraphData[{"UniquelyGraceful",{8,20}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,20}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,20}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,20}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,20}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,20}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,20}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,20}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,20}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,20}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,20}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 21}}

Names

GraphData[{"UniquelyGraceful",{8,21}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,21}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,21}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,21}}]]

Default embedding

GraphPlot[RotateGraph[Graph[GraphData[{"UniquelyGraceful",{8,21}},"VertexList"],GraphData[{"UniquelyGraceful",{8,21}},"Edges"]],-Pi/2]]

g=FindCorrespondingGraph[,Append[CirclePoints[7],{0,0}]]//Quiet

RecognizeGraph@g

gs={,,};

Degenerate

GraphData[{"UniquelyGraceful",{8,21}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,21}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,21}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,21}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,21}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,21}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,21}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,21}},"LCF"]

GraphData[{"UniquelyGraceful",{8,21}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,21}},"Planar"]

GraphData[{"UniquelyGraceful",{8,21}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,21}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,21}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,21}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,21}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,21}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,21}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,21}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,21}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,21}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,21}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,21}},"V"]&]

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,21}}],"CrossingNumber"->cn,RandomSeed->n]],{n,5000}],Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,21}},"V"]&]])//Timing

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,21}}],"CrossingNumber"->cn,RandomSeed->i],{i,5000}]//Union)//Timing

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

GraphPlot@

GraphPlot@

Take[GraphEmbedding[GraphicsToGraph@],8]

v={{-0.5226827921945832`,-0.1717953918209209`}+{0.03,.0},{0.8660254037844386`,-0.5`},{-0.27622656282206176`,-0.187495958790072`}+{.06,-.03},{0.0061487632546584235`,0.9979705062460111`},{0.2981022321954978`,-0.40607789793498816`},{-0.8660254037844386`,-0.5`},{-0.046039057496825436`,0.4129087482840304`},{0.08352938203528901`,-0.20748567837287246`}+{0,.06}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[6,2,4,6,5,7,4,1,6,3,7,2,8,5,2],e[7,8,3],{6,8},{1,8},{6,7},{1,5},{4,8},{1,7}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

v2=Rationalize[v,.01]

g=Graph[Range[Length[v]],UndirectedEdge@@@{e[6,2,4,6,5,7,4,1,6,3,7,2,8,5,2],e[7,8,3],{6,8},{1,8},{6,7},{1,5},{4,8},{1,7}},VertexCoordinates->v2,VertexLabels->Automatic]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,21}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,21}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,21}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,21}},"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[{"UniquelyGraceful",{8,21}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,21}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,21}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,21}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,21}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,21}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,21}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,21}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,21}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,21}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,21}},"Halin"]

GraphData[{"UniquelyGraceful",{8,21}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,21}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,21}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,21}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,21}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,21}},"LCF"]

GraphData[{"UniquelyGraceful",{8,21}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,21}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,21}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,21}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,21}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,21}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,21}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,21}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,21}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,21}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,21}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 22}} == {"CompleteTripartite", {2, 3, 3}}

Names

GraphData[{"UniquelyGraceful",{8,22}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,22}},"StandardNames"]

{"UniquelyGraceful", {8, 23}}

Names

GraphData[{"UniquelyGraceful",{8,23}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,23}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,23}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,23}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,23}},"VertexList"],GraphData[{"UniquelyGraceful",{8,23}},"Edges"]]]

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

RecognizeGraph@g

s=Sqrt[3]/2;
v={{0,0},{s,-1/2},{s,1/2},{2s,0},{3s,-1/2},{3s,1/2}};
v=Join[v,Mean/@Partition[v,3]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,7,3,1,2,3,4,2,7],e[4,6,5,4,8],e[6,8,5]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

gs={,,,};

Degenerate

GraphData[{"UniquelyGraceful",{8,23}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,23}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,23}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,23}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,23}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,23}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,23}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,23}},"LCF"]

GraphData[{"UniquelyGraceful",{8,23}},"HamiltonianCycleCount"]

Planar

GraphData[{"UniquelyGraceful",{8,23}},"Planar"]

GraphData[{"UniquelyGraceful",{8,23}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"UniquelyGraceful",{8,23}}]],10]

PlanarGraphEmbeddings

GraphData[{"UniquelyGraceful",{8,23}},"PlanarEmbeddingCount"]

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

Length[plemb]

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,23}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,23}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,23}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,23}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,23}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,23}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"UniquelyGraceful",{8,23}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,23}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,23}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,23}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,23}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,23}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"UniquelyGraceful",{8,23}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,23}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,23}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,23}},"Halin"]

GraphData[{"UniquelyGraceful",{8,23}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,23}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,23}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,23}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,23}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,23}},"LCF"]

GraphData[{"UniquelyGraceful",{8,23}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,23}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,23}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,23}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,23}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,23}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,23}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,23}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,23}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,23}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,23}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 24}} == "MGraph"

Names

GraphData[{"UniquelyGraceful",{8,24}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,24}},"StandardNames"]

{"UniquelyGraceful", {8, 25}}

Names

GraphData[{"UniquelyGraceful",{8,25}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,25}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,25}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,25}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,25}},"VertexList"],GraphData[{"UniquelyGraceful",{8,25}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs={,};

Degenerate

GraphData[{"UniquelyGraceful",{8,25}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,25}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,25}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,25}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,25}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,25}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,25}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,25}},"LCF"]

GraphData[{"UniquelyGraceful",{8,25}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,25}},"Planar"]

GraphData[{"UniquelyGraceful",{8,25}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,25}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,25}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,25}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,25}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,25}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,25}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,25}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,25}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,25}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,25}}],"CrossingNumber"->cn])//PolyhedralGraphQ

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,25}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,25}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,25}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,25}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,25}},"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[{"UniquelyGraceful",{8,25}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,25}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,25}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,25}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,25}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,25}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,25}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,25}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,25}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,25}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,25}},"Halin"]

GraphData[{"UniquelyGraceful",{8,25}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,25}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,25}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,25}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,25}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,25}},"LCF"]

GraphData[{"UniquelyGraceful",{8,25}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,25}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,25}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,25}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,25}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,25}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,25}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,25}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,25}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,25}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,25}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 26}}

Names

GraphData[{"UniquelyGraceful",{8,26}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,26}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,26}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,26}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,26}},"VertexList"],GraphData[{"UniquelyGraceful",{8,26}},"Edges"]]]

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

RecognizeGraph@g

s=Sqrt[3]/2;
v={{-s,0},{0,-1/2},{0,1/2},{1,-1/2},{1,1/2},{1/2,-1/6},{1/2,1/6}};
v=Append[v,Mean[Take[v,3]]];
g=FindCorrespondingGraph[,v]

gs={,,,}

RecognizeGraph/@gs

Degenerate

GraphData[{"UniquelyGraceful",{8,26}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,26}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,26}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,26}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,26}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,26}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,26}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,26}},"LCF"]

GraphData[{"UniquelyGraceful",{8,26}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,26}},"Planar"]

GraphData[{"UniquelyGraceful",{8,26}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,26}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,26}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,26}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,26}}],"CrossingNumber"->cn])//PolyhedralGraphQ

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,26}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

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

GraphPlot@RotateGraph[,-2Pi/5]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

gs={,};

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,26}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,26}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,26}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,26}},"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[{"UniquelyGraceful",{8,26}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,26}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,26}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,26}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,26}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,26}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,26}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"UniquelyGraceful",{8,26}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,26}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,26}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,26}},"Halin"]

GraphData[{"UniquelyGraceful",{8,26}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,26}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,26}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,26}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,26}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,26}},"LCF"]

GraphData[{"UniquelyGraceful",{8,26}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,26}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,26}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,26}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,26}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,26}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,26}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,26}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,26}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,26}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,26}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 27}}

Names

GraphData[{"UniquelyGraceful",{8,27}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,27}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,27}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,27}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,27}},"VertexList"],GraphData[{"UniquelyGraceful",{8,27}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs={,,}

Degenerate

GraphData[{"UniquelyGraceful",{8,27}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,27}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,27}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,27}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,27}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,27}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,27}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,27}},"LCF"]

GraphData[{"UniquelyGraceful",{8,27}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,27}},"Planar"]

GraphData[{"UniquelyGraceful",{8,27}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,27}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,27}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,27}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,27}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,27}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,27}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,27}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,27}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,27}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,27}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,27}},"V"]&]

GraphPlot@RotateGraph[,-2Pi/3]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,27}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

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

GraphPlot@RotateGraph[,-Pi/2]

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,27}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,27}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,27}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,27}},"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[{"UniquelyGraceful",{8,27}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,27}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,27}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,27}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,27}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,27}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,27}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,27}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,27}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,27}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,27}},"Halin"]

GraphData[{"UniquelyGraceful",{8,27}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,27}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,27}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,27}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,27}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,27}},"LCF"]

GraphData[{"UniquelyGraceful",{8,27}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,27}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,27}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,27}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,27}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,27}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,27}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,27}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,27}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,27}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,27}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 28}}

Names

GraphData[{"UniquelyGraceful",{8,28}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,28}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,28}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,28}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,28}},"VertexList"],GraphData[{"UniquelyGraceful",{8,28}},"Edges"]]]

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

RecognizeGraph@g

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

RecognizeGraph/@gs

Degenerate

GraphData[{"UniquelyGraceful",{8,28}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,28}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,28}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,28}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,28}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,28}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,28}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,28}},"LCF"]

GraphData[{"UniquelyGraceful",{8,28}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

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[{"UniquelyGraceful",{8,28}},"Planar"]

GraphData[{"UniquelyGraceful",{8,28}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,28}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,28}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,28}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,28}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,28}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,28}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,28}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,28}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,28}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,28}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,28}},"V"]&]

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,28}}],"CrossingNumber"->cn,RandomSeed->n]],{n,5000}],Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,28}},"V"]&]])//Timing

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,28}}],"CrossingNumber"->cn,RandomSeed->i],{i,5000}]//Union)//Timing

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

Quit

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,28}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,28}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,28}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,28}},"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[{"UniquelyGraceful",{8,28}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,28}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,28}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,28}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,28}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,28}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,28}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,28}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,28}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,28}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,28}},"Halin"]

GraphData[{"UniquelyGraceful",{8,28}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,28}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,28}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,28}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,28}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,28}},"LCF"]

GraphData[{"UniquelyGraceful",{8,28}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,28}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,28}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,28}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,28}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,28}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,28}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,28}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,28}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,28}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,28}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 29}} == {"KTree", {4, {8, 5}}}

Names

GraphData[{"UniquelyGraceful",{8,29}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,29}},"StandardNames"]

{"UniquelyGraceful", {8, 30}}

Names

GraphData[{"UniquelyGraceful",{8,30}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,30}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,30}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,30}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,30}},"VertexList"],GraphData[{"UniquelyGraceful",{8,30}},"Edges"]]]

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

RecognizeGraph@g

Degenerate

GraphData[{"UniquelyGraceful",{8,30}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,30}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,30}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,30}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,30}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,30}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,30}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,30}},"LCF"]

GraphData[{"UniquelyGraceful",{8,30}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,30}},"Planar"]

GraphData[{"UniquelyGraceful",{8,30}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,30}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,30}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,30}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,30}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,30}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,30}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,30}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,30}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,30}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,30}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,30}},"V"]&]

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,30}}],"CrossingNumber"->cn,RandomSeed->n]],{n,5000}],Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,30}},"V"]&]])//Timing

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,30}}],"CrossingNumber"->cn,RandomSeed->i],{i,5000}]//Union)//Timing

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

GraphPlot@RotateGraph[,-2Pi/3]

GraphPlot@RotateGraph[,2Pi/3]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,30}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,30}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,30}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,30}},"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[{"UniquelyGraceful",{8,30}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,30}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,30}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,30}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,30}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,30}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,30}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,30}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,30}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,30}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,30}},"Halin"]

GraphData[{"UniquelyGraceful",{8,30}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,30}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,30}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,30}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,30}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,30}},"LCF"]

GraphData[{"UniquelyGraceful",{8,30}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,30}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,30}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,30}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,30}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,30}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,30}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,30}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,30}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,30}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,30}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 31}}

Names

GraphData[{"UniquelyGraceful",{8,31}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,31}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,31}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,31}}]]

Default embedding

GraphPlot[RotateGraph[Graph[GraphData[{"UniquelyGraceful",{8,31}},"VertexList"],GraphData[{"UniquelyGraceful",{8,31}},"Edges"]],-Pi/2]]

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

RecognizeGraph@g

gs={,,};

Degenerate

GraphData[{"UniquelyGraceful",{8,31}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,31}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,31}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,31}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,31}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,31}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,31}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,31}},"LCF"]

GraphData[{"UniquelyGraceful",{8,31}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,31}},"Planar"]

GraphData[{"UniquelyGraceful",{8,31}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,31}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,31}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,31}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,31}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,31}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,31}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,31}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,31}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,31}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,31}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,31}},"V"]&]

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,31}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

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

GraphPlot@RotateGraph[,Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,31}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,31}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,31}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,31}},"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[{"UniquelyGraceful",{8,31}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,31}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,31}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,31}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,31}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,31}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,31}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,31}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,31}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,31}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,31}},"Halin"]

GraphData[{"UniquelyGraceful",{8,31}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,31}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,31}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,31}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,31}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,31}},"LCF"]

GraphData[{"UniquelyGraceful",{8,31}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,31}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,31}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,31}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,31}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,31}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,31}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,31}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,31}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,31}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,31}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 32}}

Names

GraphData[{"UniquelyGraceful",{8,32}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,32}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,32}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,32}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,32}},"VertexList"],GraphData[{"UniquelyGraceful",{8,32}},"Edges"]]]

v=Join[CirclePoints[6],{3/4#,0}&/@{-1,1}];
g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs={,,};

Degenerate

GraphData[{"UniquelyGraceful",{8,32}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,32}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,32}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,32}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,32}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,32}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,32}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,32}},"LCF"]

GraphData[{"UniquelyGraceful",{8,32}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

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[{"UniquelyGraceful",{8,32}},"Planar"]

GraphData[{"UniquelyGraceful",{8,32}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,32}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,32}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,32}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,32}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,32}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,32}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,32}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,32}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,32}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,32}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,32}},"V"]&]

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

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,32}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

gs={,};

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,32}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,32}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,32}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,32}},"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[{"UniquelyGraceful",{8,32}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,32}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,32}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,32}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,32}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,32}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,32}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"UniquelyGraceful",{8,32}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,32}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,32}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,32}},"Halin"]

GraphData[{"UniquelyGraceful",{8,32}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,32}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,32}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,32}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,32}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,32}},"LCF"]

GraphData[{"UniquelyGraceful",{8,32}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,32}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,32}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,32}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,32}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,32}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,32}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,32}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,32}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,32}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,32}},"Polyhedral"]

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

{"UniquelyGraceful", {8, 33}}

Names

GraphData[{"UniquelyGraceful",{8,33}},"StandardName"]

GraphData[{"UniquelyGraceful",{8,33}},"StandardNames"]

Primary

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

All

GraphData[{"UniquelyGraceful",{8,33}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"UniquelyGraceful",{8,33}}]]

Default embedding

GraphPlot[Graph[GraphData[{"UniquelyGraceful",{8,33}},"VertexList"],GraphData[{"UniquelyGraceful",{8,33}},"Edges"],GraphLayout->"SpringEmbedding"]]

v=Join[CirclePoints[6],{{-1/4,-1/8},{1/4,1/8}}];
g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphSymmetryGroup@g

Degenerate

GraphData[{"UniquelyGraceful",{8,33}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"UniquelyGraceful",{8,33}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"UniquelyGraceful",{8,33}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"UniquelyGraceful",{8,33}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"UniquelyGraceful",{8,33}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"UniquelyGraceful",{8,33}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"UniquelyGraceful",{8,33}},"Hamiltonian"]

GraphData[{"UniquelyGraceful",{8,33}},"LCF"]

GraphData[{"UniquelyGraceful",{8,33}},"HamiltonianCycleCount"]

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

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

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

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

(bilaterallyrotatedgraphs={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[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"UniquelyGraceful",{8,33}},"Planar"]

GraphData[{"UniquelyGraceful",{8,33}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"UniquelyGraceful",{8,33}},{"RCN","CN"}]

GraphData[{"UniquelyGraceful",{8,33}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,33}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,33}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,33}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,33}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,33}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,33}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"UniquelyGraceful",{8,33}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,33}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[gs,Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,33}},"V"]&]

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,33}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}],Max[OuterFace[#]]<=GraphData[{"UniquelyGraceful",{8,33}},"V"]&]])//Timing

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

(gs=Table[MinimalCrossingGraph[GraphData[{"UniquelyGraceful",{8,33}}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union)//Timing

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

GraphPlot@RotateGraph[,2Pi/3]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"UniquelyGraceful",{8,33}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,33}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"UniquelyGraceful",{8,33}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"UniquelyGraceful",{8,33}},"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[{"UniquelyGraceful",{8,33}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData[{"UniquelyGraceful",{8,33}},"Circulant"]

GraphData[{"UniquelyGraceful",{8,33}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"UniquelyGraceful",{8,33}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"UniquelyGraceful",{8,33}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"UniquelyGraceful",{8,33}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"UniquelyGraceful",{8,33}},"ComplementGraph","Name"]

Line graph

GraphData[{"UniquelyGraceful",{8,33}},"Line"]

LineGraphQ[GraphData[{"UniquelyGraceful",{8,33}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"UniquelyGraceful",{8,33}}]]

RecognizeGraph[%]

Halin

GraphData[{"UniquelyGraceful",{8,33}},"Halin"]

GraphData[{"UniquelyGraceful",{8,33}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"UniquelyGraceful",{8,33}},"Rigid"]

GraphData[{"UniquelyGraceful",{8,33}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"UniquelyGraceful",{8,33}},"Flexible"]

GraphData[{"UniquelyGraceful",{8,33}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"UniquelyGraceful",{8,33}},"LCF"]

GraphData[{"UniquelyGraceful",{8,33}},"HamiltonianCycleCount"]

GraphData[{"UniquelyGraceful",{8,33}},"LCFSignature"]

GraphData[{"UniquelyGraceful",{8,33}},"LCFNotations"]

GraphData[{"UniquelyGraceful",{8,33}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"UniquelyGraceful",{8,33}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"UniquelyGraceful",{8,33}}],Debug->True]//Timing

GraphData[{"UniquelyGraceful",{8,33}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"UniquelyGraceful",{8,33}},"Matchstick"]

GraphData[{"UniquelyGraceful",{8,33}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"UniquelyGraceful",{8,33}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"UniquelyGraceful",{8,33}},"Polyhedral"]

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

GraphDataCountTable

GraphDataCountTable["UniquelyGraceful"]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"UniquelyGraceful"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"UniquelyGraceful"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"UniquelyGraceful"],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"UniquelyGraceful"],{n,20}]

Antiprism

Entity["Graph",{"Antiprism",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Antiprism",n},"UniquelyGraceful"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"UniquelyGraceful"],{n,5}]

Barbell

seq=Table[GraphData[{"Barbell",n},"UniquelyGraceful"],{n,3,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"UniquelyGraceful"],{n,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"UniquelyGraceful"],{n,20}]

Book

seq=Table[GraphData[{"Book",n},"UniquelyGraceful"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"UniquelyGraceful"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"UniquelyGraceful"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"UniquelyGraceful"],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"UniquelyGraceful"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Complete",n},"UniquelyGraceful"],{n,30}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["UniquelyGraceful"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"UniquelyGraceful"],{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["UniquelyGraceful"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"UniquelyGraceful"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["UniquelyGraceful"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"UniquelyGraceful"],{n,10}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["UniquelyGraceful"]

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"UniquelyGraceful"],
3Max[k,m,n]/2
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"UniquelyGraceful"],{n,2,12}]

Crown

seq=Table[GraphData[{"Crown",n},"UniquelyGraceful"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"UniquelyGraceful"],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Cycle",n},"UniquelyGraceful"],{n,3,30}]

Table[GraphData[{"Cycle",n},"Graceful"],{n,3,30}]

GraphData[{"Cycle",7},"GracefulLabelings"]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"UniquelyGraceful"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"UniquelyGraceful"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"UniquelyGraceful"],{n,3,20}]

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"UniquelyGraceful"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"UniquelyGraceful"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Empty",n},"UniquelyGraceful"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"UniquelyGraceful"],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"UniquelyGraceful"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"UniquelyGraceful"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"UniquelyGraceful"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"UniquelyGraceful"],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"UniquelyGraceful"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"UniquelyGraceful"],{n,3,20}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["UniquelyGraceful"]

seq=Table[GraphData[{"Grid",{n,n}},"UniquelyGraceful"],{n,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["UniquelyGraceful"]

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"UniquelyGraceful"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["UniquelyGraceful"]

seq=Table[GraphData[{"Grid",{n,n,n}},"UniquelyGraceful"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["UniquelyGraceful"]

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"UniquelyGraceful"],
XXX
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"UniquelyGraceful"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"UniquelyGraceful"],{n,6}]

Helm

seq=Table[GraphData[{"Helm",n},"UniquelyGraceful"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Hypercube",n},"UniquelyGraceful"],{n,0,10}]

KC

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KC",{m,n}},"UniquelyGraceful"],
XXX
},{n,10},{m,10}],1],{_,x_,x_}]

Keller

Entity["Graph",{"Keller",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Keller",n},"UniquelyGraceful"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"UniquelyGraceful"],{n,20}]

King m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"UniquelyGraceful"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["UniquelyGraceful"]

seq=Table[GraphData[{"Knight",{n,n}},"UniquelyGraceful"],{n,20}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["UniquelyGraceful"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"UniquelyGraceful"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

KP

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KP",{m,n}},"UniquelyGraceful"],
XXX
},{n,10},{m,10}],1],{_,x_,x_}]

Ladder

Entity["Graph",{"Ladder",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Ladder",n},"UniquelyGraceful"],{n,20}]

Table[GraphData[{"Ladder",n},"Graceful"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"UniquelyGraceful"],{n,20}]

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"UniquelyGraceful"],{n,11}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"UniquelyGraceful"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"UniquelyGraceful"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"MoebiusLadder",n},"UniquelyGraceful"],{n,3,25}]

Table[GraphData[{"MoebiusLadder",n},"Graceful"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Mycielski",n},"UniquelyGraceful"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Odd",n},"UniquelyGraceful"],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"UniquelyGraceful"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Path",n},"UniquelyGraceful"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"UniquelyGraceful"],{n,20}]

Pell

seq=Table[GraphData[{"Pell",n},"UniquelyGraceful"],{n,9}]

PlummerToft

seq=Table[GraphData[{"PlummerToft",n},"UniquelyGraceful"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Prism",n},"UniquelyGraceful"],{n,3,25}]

Table[GraphData[{"Prism",n},"Graceful"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"UniquelyGraceful"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"UniquelyGraceful"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"UniquelyGraceful"],{n,20}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"UniquelyGraceful"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"UniquelyGraceful"],{n,7}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"UniquelyGraceful"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"UniquelyGraceful"],{n,5}]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"UniquelyGraceful"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"UniquelyGraceful"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Star",n},"UniquelyGraceful"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"UniquelyGraceful"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"UniquelyGraceful"],{n,3,20}]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"UniquelyGraceful"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"UniquelyGraceful"],{n,3,20}]

Transposition

Entity["Graph",{"Transposition",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Transposition",n},"UniquelyGraceful"],{n,6}]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Trapezohedron",n},"UniquelyGraceful"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"UniquelyGraceful"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"UniquelyGraceful"],{n,0,20}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"UniquelyGraceful"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"UniquelyGraceful"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"UniquelyGraceful"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"UniquelyGraceful"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"UniquelyGraceful"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"UniquelyGraceful"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"UniquelyGraceful"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["UniquelyGraceful"]

seq=Table[GraphData[{"Wheel",n},"UniquelyGraceful"],{n,4,20}]

Table[GraphData[{"Wheel",n},"Graceful"],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"UniquelyGraceful"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"UniquelyGraceful"],{n,2,20}]

WhiteCamel n×n

seq=Table[GraphData[{"Bishop",{n,n}},"UniquelyGraceful"],{n,{5}}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"UniquelyGraceful"],{n,20}]

GraphData

GraphDataString

file=OpenWrite["~/uniquely-graceful.m"]

WriteString[file,GraphDataString[#2,
"StandardName"->#4,
"AlternateStandardNames"->If[FreeQ[#4,"UniquelyGraceful"],{{"UniquelyGraceful",#}},{}],
"Name"->"8\[Hyphen]uniquely graceful graph "<>ToString[#1[[2]]],
"Classes"->{"Graceful","UniquelyGraceful"},
"Information"->"UniquelyGracefulGraph",
"NotationRules"->{"UniquelyGracefulGraph"->#},
"Skip"->{"ConstructionNumber"}
]]&@@@AddToGraphData;

Close[file]