Fully Forested Graph

Author

Eric W. Weisstein
January 31, 2025

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

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

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

Code

FullyForestedGraphQ[g_Graph,n_]:=AllTrue[Trees[n],IsomorphicSubgraphQ[#,g]&]

Clear[SmallestFullyForestedGraphs

SmallestFullyForestedGraphs[n_Integer?Positive]:=Module[
{
m={0,1,2,4,6,8,11,13,16,18}[[n]]
},
Select[
Graphs[n],
And[
EdgeCount[#]==m,
FullyForestedGraphQ[#,n]
]&
]
]/;n<11

minimal (i.e., not still can't remove any edges while still containing all trees)

MinimalSmallestFullyForestedGraphs[n_Integer?Positive]:=Module[{smallest=SmallestFullyForestedGraphs[n]},
Pick[smallest,MinimalGraphQ[#,smallest]&/@smallest]
]

MinimalGraphQ[g_Graph,l_List]:=Module[
{
subg=Union[CanonicalGraph[Graph[#]]&/@Subsets[EdgeList[g]]],cg=CanonicalGraph/@Select[l,EdgeCount[#]<EdgeCount[g]&]
},
DisjointQ[subg,cg]
]

Sources

Chung and Graham 1978

Question 1:

From Chung and Graham (1978): "Note that all examples given thus far for optimal elements of 𝒮((Subscript[𝒯, n])) have just n+1 vertices, the minimum number possible. Whether this always
happens is not known."  The following code only checks n-node graphs, so assumes so.

where n is the edge count of the tree; but OEIS and MW consider the et of trees with n vertices

Agrees with A004401

<<MathWorld`Graphs`

BFileSequence[004401]

Table[2n-4,{n,10}]

Note (SuperStar[G])(3) is erroneous since it does not contain (Subscript[P, 3])

Chung et al. 1976

Chung, F.~R.~K.; Graham, R.~L.; and Pippenger, N.  ``On Graphs Which Contain All Small Trees. II.''  {\it Colloq.\ Math.\ Soc.\ Janos Bolyai} {\bf 18}, 213--223, 1976.

https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=2050&context=hmc_fac_pub

Minimum number of edges in a *tree* containing containing all trees with n edges

{1,2,4,6,9,13,17}

Possibly not in OEIS?

https://oeis.org/search?q=1%2c2%2c4%2c6%2c9%2c13%2c17

But that minus 1 matches

https://oeis.org/search?q=0%2C1%2C3%2C5%2C8%2C12%2C16&go=Search

https://oeis.org/A000212

{1,2,4,6,9,13,17}-1

Table[Floor[n^2/3],{n,10}]

Figures

Example

GraphicsRow[trees=HighlightGraph[#,EdgeList[#]]&/@(Annotate[#,{VertexSize->{"Scaled",.04},VertexStyle->Black,EdgeStyle->Gray}]&/@Trees[6]),Dividers->All]

g=GraphData[{"SmallestFullyForested",{6,1}}]

GraphicsRow[forestedgraphs=HighlightGraph[Annotate[g,{VertexSize->.07,VertexStyle->Black,EdgeStyle->Gray}],#]&/@(EdgeList@@FindIsomorphicSubgraph[g,#]&/@trees)]

GraphicsGrid[{trees,forestedgraphs},Dividers->All]

Fully n-forested

LabeledGraphDataGraph[r_?DataPaclets`GraphDataDump`MyGraphQ]:=Module[{not,lab,std,},
lab=Which[
!MissingQ[not=GraphData[r,"Notation"]/.s_String?(StringMatchQ[#,LetterCharacter]&):>Style[s,Italic]],
	not,
True,
	Style[StringReplace[GraphData[r,"Name"],"smallest "|" graph"->""],Italic]
];
StyleGraphs[GraphData[r],PlotLabel->Style[lab,Directive[14,Black,FontFamily->"Times New Roman"]]]
]

LabeledGraphDataGraph[g_Graph]:=LabeledGraphDataGraph[RecognizeGraph[g]]

smallest=SplitBy[SortBy[DeleteCases[{GraphData[#,"NotationRules","SmallestFullyForested"],#}&/@GraphData["SmallestFullyForested"],{_Missing,_}],First],#[[1,1]]&][[All,All,2]]

GraphicsGrid[Map[LabeledGraphDataGraph,Take[smallest,7],{2}],Dividers->{{Thick,{True},Thick},Thick},Alignment->Top,ItemAspectRatio->1,ImageSize->800]

Counts

smallest=SplitBy[SortBy[DeleteCases[{GraphData[#,"NotationRules","SmallestFullyForested"],#}&/@GraphData["SmallestFullyForested"],{_Missing,_}],First],#[[1,1]]&][[All,All,2]]

A004401

cnts=BFileSequence[4401]

cnts==(GraphData[#,"EdgeCount"]&/@smallest[[All,1]])

Bound from Chung and Graham (1978)

Table[2n-4,{n,10}]

A380740

BFileSequence[380740]==(Length/@smallest)

Tally[Sort[GraphData["SmallestFullyForested","V"]]]

%[[All,2]]

Compute

Preload

<<MathWorld`Graphs`

Preload trees:

Do[Print[{n,Length[Trees[n]]//Timing}],{n,7,8}]

Preload graphs:

Do[Print[{n,Length[Graphs[n]]//Timing}],{n,10}]

1-6 nodes

Do[Print[{n,SmallestFullyForestedGraphs[n]//Timing}],{n,6}]

7 nodes

GraphData["SmallestFullyForested",7]

GraphData/@%//StyleGraphs

smallest7=SmallestFullyForestedGraphs[7]

Tally[EdgeCount/@smallest7]

GraphIndex/@smallest7

RecognizeGraph/@smallest7

Select[GraphData[7],!FreeQ[GraphData[#,"NotationRules"],"SmallestFullyForested"]&]

MinimalGraphQ[#,smallest7]&/@smallest7

FullyForestedGraphQ[#,7]&/@smallest7

FullyForestedGraphQ[#,8]&/@smallest7

Chung and Graham 1978

v={{270,190},{274,236},{205,213},{155,267},{95,267},{130,212},{127,176}};
g=Graph[Range@Length@v,UndirectedEdge@@@{e[7,3,2,1,3,4,6,5,3,6,7],{4,5}},VertexCoordinates->v,VertexLabels->Automatic]

GraphIndex@g

8 nodes

GraphData["SmallestFullyForested",8]

GraphData/@%//StyleGraphs

Length[smallest8=SmallestFullyForestedGraphs[8]]//Timing

smallest8

FirstPosition[smallest8,_?(IsomorphicGraphQ[#,g]&)]

RecognizeGraph/@smallest8

Tally[EdgeCount/@smallest8]

GraphIndex/@smallest8

FullyForestedGraphQ[#,8]&/@smallest8

FullyForestedGraphQ[#,9]&/@smallest8

Chung and Graham 1978

v={{690,212},{630,210},{629,153},{582,161},{548,191},{547,234},{581,259},{630,279}};
g8=Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,8,7,6,5,4,3,2,7,4,2],e[5,2,6]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g8

FirstPosition[smallest8,_?(IsomorphicGraphQ[#,g8]&)]

9 nodes

GraphData["SmallestFullyForested",9]

GraphData/@%//StyleGraphs

Length[smallest9=SmallestFullyForestedGraphs[9]]//Timing

smallest9

RecognizeGraph/@smallest9

Tally[EdgeCount/@smallest9]

GraphIndex/@smallest9

FullyForestedGraphQ[#,9]&/@smallest9

FullyForestedGraphQ[#,10]&/@smallest9

Import["https://oeis.org/A004401/a004401.png"]

v={{385,58},{278,75},{515,253},{405,189},{285,258},{389,377},{258,451},{125,386},{65,267}};
g9=Graph[Range@Length@v,UndirectedEdge@@@{e[2,1,4,5,6,7,8,9,5,3],e[8,5,7],e[2,5,1],e[2,4,6],{4,3}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g9

FirstPosition[smallest9,_?(IsomorphicGraphQ[#,g9]&)]

10 nodes

GraphData["SmallestFullyForested",10]

GraphData/@%//StyleGraphs

Length[smallest10=SmallestFullyForestedGraphs[10]]//Timing

smallest10

RecognizeGraph/@smallest10

Tally[EdgeCount/@smallest10]

GraphIndex/@smallest10

FullyForestedGraphQ[#,10]&/@smallest10

FullyForestedGraphQ[#,11]&/@smallest10

Import["https://oeis.org/A004401/a004401_1.png"]

v={{187,20},{253,132},{139,106},{187,203},{369,217},{329,298},{240,266},{113,360},{108,249},{18,241}};
g10=Graph[Range@Length@v,UndirectedEdge@@@{e[1,4,3,1],e[9,10,4,8,9,4,2,3,9,7,6,4,5,6],e[2,7,4]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g10

FirstPosition[smallest10,_?(IsomorphicGraphQ[#,g10]&)]

Embeddings

<<MathWorld`Graphs`

GraphData["SmallestFullyForested"]

{"SmallestFullyForested", {1, 1}} == "SingletonGraph"

Names

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

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

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

Names

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

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

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

Names

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

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

{"SmallestFullyForested", {4, 1}} == "PawGraph"

Names

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

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

{"SmallestFullyForested", {5, 1}} == "DartGraph"

Names

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

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

{"SmallestFullyForested", {5, 2}} == "ButterflyGraph"

Names

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

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

{"SmallestFullyForested", {6, 1}} == {"Matchstick", {8, 4}}

Names

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

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

{"SmallestFullyForested", {6, 2}} == {"Matchstick", {8, 1}}

Names

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

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

{"SmallestFullyForested", {7, 1}}

Names

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

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

Primary

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

All

GraphData[{"SmallestFullyForested",{7,1}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"SmallestFullyForested",{7,1}}]]

Default embedding

RotateGraph[GraphPlot[Graph[GraphData[{"SmallestFullyForested",{7,1}},"VertexList"],GraphData[{"SmallestFullyForested",{7,1}},"Edges"]]],-Pi/2]

v={{-1,0},{0,0},{1,0},{0,-1},{0,Sqrt[3]}};
v=Join[v,Mean[v[[{5,#}]]]&/@{1,3}];
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

RotateGraph[GraphPlot[Graph[GraphData[{"SmallestFullyForested",{7,1}},"VertexList"],GraphData[{"SmallestFullyForested",{7,1}},"Edges"]],GraphLayout->"RadialEmbedding"],-2Pi/3+Pi]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphPlot@

RotateGraph[,-.1]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"SmallestFullyForested",{7,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"SmallestFullyForested",{7,1}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"SmallestFullyForested",{7,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"SmallestFullyForested",{7,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"SmallestFullyForested",{7,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"SmallestFullyForested",{7,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"SmallestFullyForested",{7,1}},"Hamiltonian"]

GraphData[{"SmallestFullyForested",{7,1}},"LCF"]

GraphData[{"SmallestFullyForested",{7,1}},"HamiltonianCycleCount"]

Planar

GraphData[{"SmallestFullyForested",{7,1}},"Planar"]

GraphData[{"SmallestFullyForested",{7,1}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"SmallestFullyForested",{7,1}}]],10]

PlanarGraphEmbeddings

GraphData[{"SmallestFullyForested",{7,1}},"PlanarEmbeddingCount"]

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

Length[plemb]

MinimalCrossing

GraphData[{"SmallestFullyForested",{7,1}},{"RCN","CN"}]

GraphData[{"SmallestFullyForested",{7,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"SmallestFullyForested",{7,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{7,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"SmallestFullyForested",{7,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{7,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"SmallestFullyForested",{7,1}},"Circulant"]

GraphData[{"SmallestFullyForested",{7,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"SmallestFullyForested",{7,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"SmallestFullyForested",{7,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"SmallestFullyForested",{7,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"SmallestFullyForested",{7,1}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"SmallestFullyForested",{7,1}},"Line"]

LineGraphQ[GraphData[{"SmallestFullyForested",{7,1}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"SmallestFullyForested",{7,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"SmallestFullyForested",{7,1}},"Halin"]

GraphData[{"SmallestFullyForested",{7,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"SmallestFullyForested",{7,1}},"Rigid"]

GraphData[{"SmallestFullyForested",{7,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"SmallestFullyForested",{7,1}},"Flexible"]

GraphData[{"SmallestFullyForested",{7,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"SmallestFullyForested",{7,1}},"LCF"]

GraphData[{"SmallestFullyForested",{7,1}},"HamiltonianCycleCount"]

GraphData[{"SmallestFullyForested",{7,1}},"LCFSignature"]

GraphData[{"SmallestFullyForested",{7,1}},"LCFNotations"]

GraphData[{"SmallestFullyForested",{7,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"SmallestFullyForested",{7,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"SmallestFullyForested",{7,1}}],Debug->True]//Timing

GraphData[{"SmallestFullyForested",{7,1}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"SmallestFullyForested",{7,1}},"Matchstick"]

GraphData[{"SmallestFullyForested",{7,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"SmallestFullyForested",{7,1}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"SmallestFullyForested",{7,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"SmallestFullyForested",{7,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"SmallestFullyForested",{7,1}},"Polyhedral"]

GraphData[{"SmallestFullyForested",{7,1}},"Graph",{"3D","Polyhedron"}]

{"SmallestFullyForested", {7, 2}} == {"KTree", {2, {7, 4}}}

Names

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

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

{"SmallestFullyForested", {7, 3}}

Names

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

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

Primary

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

All

GraphData[{"SmallestFullyForested",{7,3}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"SmallestFullyForested",{7,3}}]]

Default embedding

GraphPlot[Graph[GraphData[{"SmallestFullyForested",{7,3}},"VertexList"],GraphData[{"SmallestFullyForested",{7,3}},"Edges"]]]

RotateGraph[,-1.35]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"SmallestFullyForested",{7,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"SmallestFullyForested",{7,3}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"SmallestFullyForested",{7,3}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"SmallestFullyForested",{7,3}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"SmallestFullyForested",{7,3}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"SmallestFullyForested",{7,3}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"SmallestFullyForested",{7,3}},"Hamiltonian"]

GraphData[{"SmallestFullyForested",{7,3}},"LCF"]

GraphData[{"SmallestFullyForested",{7,3}},"HamiltonianCycleCount"]

Planar

GraphData[{"SmallestFullyForested",{7,3}},"Planar"]

GraphData[{"SmallestFullyForested",{7,3}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"SmallestFullyForested",{7,3}}]],10]

PlanarGraphEmbeddings

GraphData[{"SmallestFullyForested",{7,3}},"PlanarEmbeddingCount"]

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

Length[plemb]

MinimalCrossing

GraphData[{"SmallestFullyForested",{7,3}},{"RCN","CN"}]

GraphData[{"SmallestFullyForested",{7,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"SmallestFullyForested",{7,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{7,3}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"SmallestFullyForested",{7,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{7,3}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"SmallestFullyForested",{7,3}},"Circulant"]

GraphData[{"SmallestFullyForested",{7,3}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"SmallestFullyForested",{7,3}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"SmallestFullyForested",{7,3}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"SmallestFullyForested",{7,3}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"SmallestFullyForested",{7,3}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"SmallestFullyForested",{7,3}},"Line"]

LineGraphQ[GraphData[{"SmallestFullyForested",{7,3}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"SmallestFullyForested",{7,3}}]]

RecognizeGraph[%]

Halin

GraphData[{"SmallestFullyForested",{7,3}},"Halin"]

GraphData[{"SmallestFullyForested",{7,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"SmallestFullyForested",{7,3}},"Rigid"]

GraphData[{"SmallestFullyForested",{7,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"SmallestFullyForested",{7,3}},"Flexible"]

GraphData[{"SmallestFullyForested",{7,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"SmallestFullyForested",{7,3}},"LCF"]

GraphData[{"SmallestFullyForested",{7,3}},"HamiltonianCycleCount"]

GraphData[{"SmallestFullyForested",{7,3}},"LCFSignature"]

GraphData[{"SmallestFullyForested",{7,3}},"LCFNotations"]

GraphData[{"SmallestFullyForested",{7,3}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"SmallestFullyForested",{7,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"SmallestFullyForested",{7,3}}],Debug->True]//Timing

GraphData[{"SmallestFullyForested",{7,3}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"SmallestFullyForested",{7,3}},"Matchstick"]

GraphData[{"SmallestFullyForested",{7,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"SmallestFullyForested",{7,3}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"SmallestFullyForested",{7,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"SmallestFullyForested",{7,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"SmallestFullyForested",{7,3}},"Polyhedral"]

GraphData[{"SmallestFullyForested",{7,3}},"Graph",{"3D","Polyhedron"}]

{"SmallestFullyForested", {7, 4}}

Names

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

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

Primary

GraphData[{"SmallestFullyForested",{7,4}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"SmallestFullyForested",{7,4}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"SmallestFullyForested",{7,4}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"SmallestFullyForested",{7,4}}]]

Default embedding

GraphPlot[Graph[GraphData[{"SmallestFullyForested",{7,4}},"VertexList"],GraphData[{"SmallestFullyForested",{7,4}},"Edges"]]]

GraphPlot@

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

RotateGraph[,Pi]

s=Sqrt[3]/2;
g=FindCorrespondingGraph[,{{0,0},{1,0},{2,0},{1,-1},{2,-1},{1/2,s},{3/2,s}}]

RecognizeGraph@g

Degenerate

GraphData[{"SmallestFullyForested",{7,4}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"SmallestFullyForested",{7,4}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"SmallestFullyForested",{7,4}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"SmallestFullyForested",{7,4}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"SmallestFullyForested",{7,4}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"SmallestFullyForested",{7,4}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"SmallestFullyForested",{7,4}},"Hamiltonian"]

GraphData[{"SmallestFullyForested",{7,4}},"LCF"]

GraphData[{"SmallestFullyForested",{7,4}},"HamiltonianCycleCount"]

Planar

GraphData[{"SmallestFullyForested",{7,4}},"Planar"]

GraphData[{"SmallestFullyForested",{7,4}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"SmallestFullyForested",{7,4}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"SmallestFullyForested",{7,4}}]],10]

PlanarGraphEmbeddings

GraphData[{"SmallestFullyForested",{7,4}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"SmallestFullyForested",{7,4}}],Debug->True])//Timing

Length[plemb]

MinimalCrossing

GraphData[{"SmallestFullyForested",{7,4}},{"RCN","CN"}]

GraphData[{"SmallestFullyForested",{7,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"SmallestFullyForested",{7,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{7,4}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"SmallestFullyForested",{7,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{7,4}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"SmallestFullyForested",{7,4}},"Circulant"]

GraphData[{"SmallestFullyForested",{7,4}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"SmallestFullyForested",{7,4}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"SmallestFullyForested",{7,4}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"SmallestFullyForested",{7,4}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"SmallestFullyForested",{7,4}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"SmallestFullyForested",{7,4}},"Line"]

LineGraphQ[GraphData[{"SmallestFullyForested",{7,4}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"SmallestFullyForested",{7,4}}&]

RootGraph[GraphData[{"SmallestFullyForested",{7,4}}]]

RecognizeGraph[%]

Halin

GraphData[{"SmallestFullyForested",{7,4}},"Halin"]

GraphData[{"SmallestFullyForested",{7,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"SmallestFullyForested",{7,4}},"Rigid"]

GraphData[{"SmallestFullyForested",{7,4}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"SmallestFullyForested",{7,4}},"Flexible"]

GraphData[{"SmallestFullyForested",{7,4}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"SmallestFullyForested",{7,4}},"LCF"]

GraphData[{"SmallestFullyForested",{7,4}},"HamiltonianCycleCount"]

GraphData[{"SmallestFullyForested",{7,4}},"LCFSignature"]

GraphData[{"SmallestFullyForested",{7,4}},"LCFNotations"]

GraphData[{"SmallestFullyForested",{7,4}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"SmallestFullyForested",{7,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"SmallestFullyForested",{7,4}}],Debug->True]//Timing

GraphData[{"SmallestFullyForested",{7,4}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"SmallestFullyForested",{7,4}},"VertexList"],GraphData[{"SmallestFullyForested",{7,4}},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"SmallestFullyForested",{7,4}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"SmallestFullyForested",{7,4}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"SmallestFullyForested",{7,4}},"Matchstick"]

GraphData[{"SmallestFullyForested",{7,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"SmallestFullyForested",{7,4}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"SmallestFullyForested",{7,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"SmallestFullyForested",{7,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"SmallestFullyForested",{7,4}},"Polyhedral"]

GraphData[{"SmallestFullyForested",{7,4}},"Graph",{"3D","Polyhedron"}]

{"SmallestFullyForested", {7, 5}}

Names

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

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

Primary

GraphData[{"SmallestFullyForested",{7,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"SmallestFullyForested",{7,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"SmallestFullyForested",{7,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"SmallestFullyForested",{7,5}}]]

Default embedding

RotateGraph[GraphPlot[Graph[GraphData[{"SmallestFullyForested",{7,5}},"VertexList"],GraphData[{"SmallestFullyForested",{7,5}},"Edges"]]],-.5]

v={{0,0},{-1,1},{0,1},{1,1},{-1,2},{0,2},{1,2}};
g=FindCorrespondingGraph[,v]

RecognizeGraph@g

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

RotateGraph[,-2.95]

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

RecognizeGraph@g

GraphPlot@RotateGraph[,.3]

s=Sqrt[3]/2;
v={{0,0},{1,0},{2,0},{1,-1},{1/2,s},{3/2,s}};
AppendTo[v,Mean[v[[{1,2,5}]]]];
Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphPlot@RotateGraph[,-Pi/4]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"SmallestFullyForested",{7,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"SmallestFullyForested",{7,5}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"SmallestFullyForested",{7,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"SmallestFullyForested",{7,5}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"SmallestFullyForested",{7,5}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"SmallestFullyForested",{7,5}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"SmallestFullyForested",{7,5}},"Hamiltonian"]

GraphData[{"SmallestFullyForested",{7,5}},"LCF"]

GraphData[{"SmallestFullyForested",{7,5}},"HamiltonianCycleCount"]

Planar

GraphData[{"SmallestFullyForested",{7,5}},"Planar"]

GraphData[{"SmallestFullyForested",{7,5}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"SmallestFullyForested",{7,5}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"SmallestFullyForested",{7,5}}]],10]

PlanarGraphEmbeddings

GraphData[{"SmallestFullyForested",{7,5}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"SmallestFullyForested",{7,5}}],Debug->True])//Timing

Length[plemb]

MinimalCrossing

GraphData[{"SmallestFullyForested",{7,5}},{"RCN","CN"}]

GraphData[{"SmallestFullyForested",{7,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"SmallestFullyForested",{7,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{7,5}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"SmallestFullyForested",{7,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{7,5}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"SmallestFullyForested",{7,5}},"Circulant"]

GraphData[{"SmallestFullyForested",{7,5}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"SmallestFullyForested",{7,5}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"SmallestFullyForested",{7,5}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"SmallestFullyForested",{7,5}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"SmallestFullyForested",{7,5}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"SmallestFullyForested",{7,5}},"Line"]

LineGraphQ[GraphData[{"SmallestFullyForested",{7,5}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"SmallestFullyForested",{7,5}}&]

RootGraph[GraphData[{"SmallestFullyForested",{7,5}}]]

RecognizeGraph[%]

Halin

GraphData[{"SmallestFullyForested",{7,5}},"Halin"]

GraphData[{"SmallestFullyForested",{7,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"SmallestFullyForested",{7,5}},"Rigid"]

GraphData[{"SmallestFullyForested",{7,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"SmallestFullyForested",{7,5}},"Flexible"]

GraphData[{"SmallestFullyForested",{7,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"SmallestFullyForested",{7,5}},"LCF"]

GraphData[{"SmallestFullyForested",{7,5}},"HamiltonianCycleCount"]

GraphData[{"SmallestFullyForested",{7,5}},"LCFSignature"]

GraphData[{"SmallestFullyForested",{7,5}},"LCFNotations"]

GraphData[{"SmallestFullyForested",{7,5}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"SmallestFullyForested",{7,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"SmallestFullyForested",{7,5}}],Debug->True]//Timing

GraphData[{"SmallestFullyForested",{7,5}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"SmallestFullyForested",{7,5}},"VertexList"],GraphData[{"SmallestFullyForested",{7,5}},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"SmallestFullyForested",{7,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"SmallestFullyForested",{7,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"SmallestFullyForested",{7,5}},"Matchstick"]

GraphData[{"SmallestFullyForested",{7,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"SmallestFullyForested",{7,5}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"SmallestFullyForested",{7,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"SmallestFullyForested",{7,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"SmallestFullyForested",{7,5}},"Polyhedral"]

GraphData[{"SmallestFullyForested",{7,5}},"Graph",{"3D","Polyhedron"}]

{"SmallestFullyForested", {7, 6}} == {"KTree", {2, {7, 6}}}

Names

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

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

{"SmallestFullyForested", {7, 7}} == {"Fan", {1, 6}}

Names

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

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

{"SmallestFullyForested", {8, 1}}

Names

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

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

Primary

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

All

GraphData[{"SmallestFullyForested",{8,1}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"SmallestFullyForested",{8,1}}]]

Default embedding

GraphPlot[Graph[GraphData[{"SmallestFullyForested",{8,1}},"VertexList"],GraphData[{"SmallestFullyForested",{8,1}},"Edges"]]]

RotateGraph[,Pi/2]

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

RecognizeGraph@g

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

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

g=RotateGraph[FindCorrespondingGraph[,v],Pi]

RecognizeGraph@g

gs=UnlabelGraph/@{,,,}

GraphPlot@RotateGraph[,-1.1]

GraphReplot@

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphPlot@

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"SmallestFullyForested",{8,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"SmallestFullyForested",{8,1}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"SmallestFullyForested",{8,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"SmallestFullyForested",{8,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"SmallestFullyForested",{8,1}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"SmallestFullyForested",{8,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"SmallestFullyForested",{8,1}},"Hamiltonian"]

GraphData[{"SmallestFullyForested",{8,1}},"LCF"]

GraphData[{"SmallestFullyForested",{8,1}},"HamiltonianCycleCount"]

Planar

GraphData[{"SmallestFullyForested",{8,1}},"Planar"]

GraphData[{"SmallestFullyForested",{8,1}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"SmallestFullyForested",{8,1}}]],10]

PlanarGraphEmbeddings

GraphData[{"SmallestFullyForested",{8,1}},"PlanarEmbeddingCount"]

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

Length[plemb]

MinimalCrossing

GraphData[{"SmallestFullyForested",{8,1}},{"RCN","CN"}]

GraphData[{"SmallestFullyForested",{8,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"SmallestFullyForested",{8,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{8,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"SmallestFullyForested",{8,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{8,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"SmallestFullyForested",{8,1}},"Circulant"]

GraphData[{"SmallestFullyForested",{8,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"SmallestFullyForested",{8,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"SmallestFullyForested",{8,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"SmallestFullyForested",{8,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"SmallestFullyForested",{8,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"SmallestFullyForested",{8,1}},"Line"]

LineGraphQ[GraphData[{"SmallestFullyForested",{8,1}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"SmallestFullyForested",{8,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"SmallestFullyForested",{8,1}},"Halin"]

GraphData[{"SmallestFullyForested",{8,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"SmallestFullyForested",{8,1}},"Rigid"]

GraphData[{"SmallestFullyForested",{8,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"SmallestFullyForested",{8,1}},"Flexible"]

GraphData[{"SmallestFullyForested",{8,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"SmallestFullyForested",{8,1}},"LCF"]

GraphData[{"SmallestFullyForested",{8,1}},"HamiltonianCycleCount"]

GraphData[{"SmallestFullyForested",{8,1}},"LCFSignature"]

GraphData[{"SmallestFullyForested",{8,1}},"LCFNotations"]

GraphData[{"SmallestFullyForested",{8,1}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"SmallestFullyForested",{8,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"SmallestFullyForested",{8,1}}],Debug->True]//Timing

GraphData[{"SmallestFullyForested",{8,1}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"SmallestFullyForested",{8,1}},"Matchstick"]

GraphData[{"SmallestFullyForested",{8,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"SmallestFullyForested",{8,1}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"SmallestFullyForested",{8,1}},"Polyhedral"]

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

{"SmallestFullyForested", {8, 2}}

Names

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

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

Primary

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

All

GraphData[{"SmallestFullyForested",{8,2}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"SmallestFullyForested",{8,2}}]]

Default embedding

GraphPlot[Graph[GraphData[{"SmallestFullyForested",{8,2}},"VertexList"],GraphData[{"SmallestFullyForested",{8,2}},"Edges"]]]

GraphPlot@RotateGraph[,-.5]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GraphPlot@

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs={,};

Degenerate

GraphData[{"SmallestFullyForested",{8,2}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"SmallestFullyForested",{8,2}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"SmallestFullyForested",{8,2}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"SmallestFullyForested",{8,2}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"SmallestFullyForested",{8,2}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"SmallestFullyForested",{8,2}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"SmallestFullyForested",{8,2}},"Hamiltonian"]

GraphData[{"SmallestFullyForested",{8,2}},"LCF"]

GraphData[{"SmallestFullyForested",{8,2}},"HamiltonianCycleCount"]

Planar

GraphData[{"SmallestFullyForested",{8,2}},"Planar"]

GraphData[{"SmallestFullyForested",{8,2}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"SmallestFullyForested",{8,2}}]],10]

PlanarGraphEmbeddings

GraphData[{"SmallestFullyForested",{8,2}},"PlanarEmbeddingCount"]

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

Length[plemb]

MinimalCrossing

GraphData[{"SmallestFullyForested",{8,2}},{"RCN","CN"}]

GraphData[{"SmallestFullyForested",{8,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"SmallestFullyForested",{8,2}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{8,2}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"SmallestFullyForested",{8,2}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"SmallestFullyForested",{8,2}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"SmallestFullyForested",{8,2}},"Circulant"]

GraphData[{"SmallestFullyForested",{8,2}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"SmallestFullyForested",{8,2}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"SmallestFullyForested",{8,2}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"SmallestFullyForested",{8,2}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"SmallestFullyForested",{8,2}},"ComplementGraph","Name"]

Line graph

GraphData[{"SmallestFullyForested",{8,2}},"Line"]

LineGraphQ[GraphData[{"SmallestFullyForested",{8,2}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"SmallestFullyForested",{8,2}}]]

RecognizeGraph[%]

Halin

GraphData[{"SmallestFullyForested",{8,2}},"Halin"]

GraphData[{"SmallestFullyForested",{8,2}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"SmallestFullyForested",{8,2}},"Rigid"]

GraphData[{"SmallestFullyForested",{8,2}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"SmallestFullyForested",{8,2}},"Flexible"]

GraphData[{"SmallestFullyForested",{8,2}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"SmallestFullyForested",{8,2}},"LCF"]

GraphData[{"SmallestFullyForested",{8,2}},"HamiltonianCycleCount"]

GraphData[{"SmallestFullyForested",{8,2}},"LCFSignature"]

GraphData[{"SmallestFullyForested",{8,2}},"LCFNotations"]

GraphData[{"SmallestFullyForested",{8,2}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"SmallestFullyForested",{8,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"SmallestFullyForested",{8,2}}],Debug->True]//Timing

GraphData[{"SmallestFullyForested",{8,2}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"SmallestFullyForested",{8,2}},"Matchstick"]

GraphData[{"SmallestFullyForested",{8,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"SmallestFullyForested",{8,2}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"SmallestFullyForested",{8,2}},"Polyhedral"]

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

{"SmallestFullyForested", {8, 3}} == {"KTree", {2, {8, 10}}}

Names

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

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

{"SmallestFullyForested", {8, 4}}

Names

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

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

Primary

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

All

GraphData[{"SmallestFullyForested",{8,4}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"SmallestFullyForested",{8,4}}]]

Default embedding

GraphPlot[Graph[GraphData[{"SmallestFullyForested",{8,4}},"VertexList"],GraphData[{"SmallestFullyForested",{8,4}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

gs={,,}

Degenerate

GraphData[{"SmallestFullyForested",{8,4}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"SmallestFullyForested",{8,4}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"SmallestFullyForested",{8,4}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"SmallestFullyForested",{8,4}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"SmallestFullyForested",{8,4}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"SmallestFullyForested",{8,4}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"SmallestFullyForested",{8,4}},"Hamiltonian"]

GraphData[{"SmallestFullyForested",{8,4}},"LCF"]

GraphData[{"SmallestFullyForested",{8,4}},"HamiltonianCycleCount"]

Planar

GraphData[{"SmallestFullyForested",{8,4}},"Planar"]

GraphData[{"SmallestFullyForested",{8,4}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"SmallestFullyForested",{8,4}}]],10]

PlanarGraphEmbeddings

GraphData[{"SmallestFullyForested",{8,4}},"PlanarEmbeddingCount"]

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

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"SmallestFullyForested",{8,4}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"SmallestFullyForested",{8,4}}],"OuterFace"->#]&/@faces

TextGrid[DeleteCases[{#,GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}],Dividers->All]

Grid[DeleteCases[{#,Cases[GraphSymmetryGroup[#],r_Rotation:>r,∞]}&/@gs,{_,{}}],Dividers->All]

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

TutteLayoutManipulate[g_Graph]:=Manipulate[
With[{face=OuterFace[g]},
IGLayoutTutte[IGEdgeMap[(EuclideanDistance@@#)^pow&,EdgeWeight->IGEdgeVertexProp[VertexCoordinates],IGLayoutTutte[g,"OuterFace"->face]],"OuterFace"->face,ImageSize->Automatic]],{{pow,1},.1,2}]

TutteLayoutManipulate[]

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

RecognizeGraph[g]

MinimalCrossing

GraphData[{"SmallestFullyForested",{8,4}},{"RCN","CN"}]

GraphData[{"SmallestFullyForested",{8,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

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

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

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

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

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

GraphData[{"SmallestFullyForested",{8,4}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"SmallestFullyForested",{8,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

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

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

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

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

Circulant

GraphData[{"SmallestFullyForested",{8,4}},"Circulant"]

GraphData[{"SmallestFullyForested",{8,4}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"SmallestFullyForested",{8,4}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"SmallestFullyForested",{8,4}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"SmallestFullyForested",{8,4}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"SmallestFullyForested",{8,4}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"SmallestFullyForested",{8,4}},"Line"]

LineGraphQ[GraphData[{"SmallestFullyForested",{8,4}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"SmallestFullyForested",{8,4}}]]

RecognizeGraph[%]

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

gs=LineGraph/@%

Halin

GraphData[{"SmallestFullyForested",{8,4}},"Halin"]

GraphData[{"SmallestFullyForested",{8,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"SmallestFullyForested",{8,4}},"Rigid"]

GraphData[{"SmallestFullyForested",{8,4}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"SmallestFullyForested",{8,4}},"Flexible"]

GraphData[{"SmallestFullyForested",{8,4}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"SmallestFullyForested",{8,4}},"LCF"]

GraphData[{"SmallestFullyForested",{8,4}},"HamiltonianCycleCount"]

GraphData[{"SmallestFullyForested",{8,4}},"LCFSignature"]

GraphData[{"SmallestFullyForested",{8,4}},"LCFNotations"]

GraphData[{"SmallestFullyForested",{8,4}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"SmallestFullyForested",{8,4}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"SmallestFullyForested",{8,4}}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"SmallestFullyForested",{8,4}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"SmallestFullyForested",{8,4}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"SmallestFullyForested",{8,4}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"SmallestFullyForested",{8,4}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"SmallestFullyForested",{8,4}},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

i=0;
gs={};
t0=AbsoluteTime[];
count=Length[order2];
Monitor[
Do[
If[!MissingQ[g=BilateralLCFGraph[LCFGraph@@order2[[i]]]],AppendTo[gs,g]],
{i,count}
],
Column[{
ProgressIndicator[i,{1,count}],
Row[{i,"/",count}],
Row[{"estimated time remaining: ",Round[(AbsoluteTime[]-t0) (count/i-1)]," s"}],
Row[{Length[gs]," bilateral graphs"}]
}]
];//Timing

UnitDistance

GraphData[{"SmallestFullyForested",{8,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"SmallestFullyForested",{8,4}}],Debug->True]//Timing

GraphData[{"SmallestFullyForested",{8,4}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData[{"SmallestFullyForested",{8,4}},"Matchstick"]

GraphData[{"SmallestFullyForested",{8,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"SmallestFullyForested",{8,4}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"SmallestFullyForested",{8,4}},"Polyhedral"]

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

Graphics3D[{FaceForm[Green,Red],GraphData[{"SmallestFullyForested",{8,4}},"Polyhedron"]}]

3D Canonical

GraphData[{"SmallestFullyForested",{8,4}},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"SmallestFullyForested",{8,4}},"Polyhedron","Canonical"],Yellow,Sphere[]}]

GraphData

GraphDataClassString

GraphDataClassString["SmallestFullyForested"]

AddIndexedClass

*minimal* (i.e., not still can't remove any edges while still containing all trees)

1-6

rules={"SingletonGraph"->{1,1},{"Path",2}->{2,1},{"Path",3}->{3,1},"PawGraph"->{4,1},"DartGraph"->{5,1},"ButterflyGraph"->{5,2},{"Matchstick",{8,4}}->{6,1},{"Matchstick",{8,1}}->{6,2}};

AddIndexedClass["SmallestFullyForested",rules,"14.3"]

RenameGraphFiles[]

7

rules={{7,240}->{7,1},{"KTree",{2,{7,4}}}->{7,2},{7,295}->{7,3},{7,403}->{7,4},{7,418}->{7,5},{"KTree",{2,{7,6}}}->{7,6},{"Fan",{1,6}}->{7,7}};

AddIndexedClass["SmallestFullyForested",rules,"14.3"]

RenameGraphFiles[]

GraphData

8-node

smallest8={,,,,,,,,,,,,};

Through[{VertexCount,EdgeCount}[#]]&/@smallest8//Union

smallest8list=MapIndexed[{#,{VertexCount[#],#2[[1]]},r=RecognizeGraph[#],DataPaclets`GraphDataDump`MyGraphQ[r]}&,smallest8]

rules=Cases[smallest8list,{_,not_,gn_,True}:>Rule[gn,not]]

AddIndexedClass["SmallestFullyForested",rules,"14.3"]

RenameGraphFiles[]

smallest8listtoadd=Cases[smallest8list,{g_,not_,_,False}:>{g,not}]

file=OpenWrite["~/fully-forested.m"]

<<MathWorld`Graphs`

WriteString[file,GraphDataString[
#,
"StandardName"->{"SmallestFullyForested",{n,k}=#2},
"Name"->"smallest fully forested "<>ToString[n]<>"\[Hyphen]graph "<>ToString[k],
"Classes"->{"SmallestFullyForested"},
"Information"->"FullyForestedGraph",
"NotationRules"->{"SmallestFullyForested"->#2},
"Skip"->{"ConstructionNumber","Minors"}
]]&@@@smallest8listtoadd;

9- and 10-node from OEIS

file=OpenWrite["~/fully-forested.m"]

WriteString[file,GraphDataString[
#,
"StandardName"->{"SmallestFullyForested",{n=VertexCount[#],1}},
"Name"->"smallest fully forested "<>ToString[n]<>"\[Hyphen]graph 1",
"Information"->"FullyForestedGraph",
"NotationRules"->{"SmallestFullyForested"->{n,1}}
]]&/@{g9,g10};

Close[file]

9-node

smallest9={,,,,,,,,,,,,,,,,,,,,,,,,};

Through[{VertexCount,EdgeCount}[#]]&/@smallest9//Union

GraphData[];

smallest9list=MapIndexed[{#,{VertexCount[#],#2[[1]]},r=RecognizeGraph[#],DataPaclets`GraphDataDump`MyGraphQ[r]}&,smallest9]

rules=Cases[smallest9list,{_,not_,gn_,True}:>Rule[gn,not]]

AddIndexedClass["SmallestFullyForested",rules,"14.3"]

RenameGraphFiles[]

smallest9listtoadd=Cases[smallest9list,{g_,not_,_,False}:>{g,not}]

file=OpenAppend["~/fully-forested.m"]

WriteString[file,GraphDataString[
#,
"StandardName"->{"SmallestFullyForested",{n,k}=#2},
"Name"->"smallest fully forested "<>ToString[n]<>"\[Hyphen]graph "<>ToString[k],
"Classes"->{"SmallestFullyForested"},
"Information"->"FullyForestedGraph",
"NotationRules"->{"SmallestFullyForested"->#2},
"Skip"->{"ConstructionNumber","ErdosSequence","GracefulLabelings","Minors","PlanarEmbedingCount","RadioLabelings","RadioNumber"}
]]&@@@Drop[smallest9listtoadd,1];

10-node

smallest10={,,,,,,,,,,,,,,,,};

Through[{VertexCount,EdgeCount}[#]]&/@smallest10//Union

smallest10list=MapIndexed[{#,{VertexCount[#],#2[[1]]},r=RecognizeGraph[#],DataPaclets`GraphDataDump`MyGraphQ[r]}&,smallest10]

rules=Cases[smallest10list,{_,not_,gn_,True}:>Rule[gn,not]]

AddIndexedClass["SmallestFullyForested",rules,"14.3"]

RenameGraphFiles[]

smallest10listtoadd=Cases[smallest10list,{g_,not_,_,False}:>{g,not}]

file=OpenWrite["~/fully-forested-10.m"]

WriteString[file,GraphDataString[
#,
"StandardName"->{"SmallestFullyForested",{n,k}=#2},
"Name"->"smallest fully forested "<>ToString[n]<>"\[Hyphen]graph "<>ToString[k],
"Classes"->{"SmallestFullyForested"},
"Information"->"FullyForestedGraph",
"NotationRules"->{"SmallestFullyForested"->#2},
"Skip"->{"ConstructionNumber","CyclicEdgeCuts","EdgeCuts","ErdosSequence","GracefulLabelings","Monirs","PinnacleSets","PlanarEmbedingCount","RadioLabelings","RadioNumber"}
]]&@@@smallest10listtoadd;