Fibonacci Cube Graph

Author

Eric W. Weisstein
April 10, 2026

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

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

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

Graphic

GraphicsGrid[Partition[Table[r=RecognizeGraph[g=FibonacciCubeGraph[n]];Show[StyleGraphs@If[r==={},g,GraphData[r]],PlotLabel->Style[HoldForm[n]==n,Directive[14,LightDarkSwitched@Black,FontFamily->"Times"]]],{n,8}],UpTo[4]],Dividers->All,ImageSize->700,Alignment->Top]

Special cases

TextGrid[DeleteCases[Table[{n,RecognizeGraph[FibonacciCubeGraph[n]]},{n,15}],{_,{"FibonacciCube",_}}],Dividers->All]

Embeddings

<<MathWorld`Graphs`

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

Names

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

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

{"FibonacciCube", 2} == {"Path", 3}

Names

GraphData[{"FibonacciCube",2},"StandardName"]

GraphData[{"FibonacciCube",2},"StandardNames"]

{"FibonacciCube", 3} == "BannerGraph"

Names

GraphData[{"FibonacciCube",3},"StandardName"]

GraphData[{"FibonacciCube",3},"StandardNames"]

{"FibonacciCube", 4}

Names

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

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

HouseOfGraphs

hogid=GraphData[{"FibonacciCube",4},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"FibonacciCube",4},"WikidataID"]

GraphData[{"FibonacciCube",4},"WikidataID","URL"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"FibonacciCube",4},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"FibonacciCube",4},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

CompleteKPartite

GraphData[{"FibonacciCube",5},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"FibonacciCube",4},"Bipartite"]

GraphData[{"FibonacciCube",4},"Graph","Bipartite"]//StyleGraphs

Bipartite construction

GraphData[{"FibonacciCube",4},"Bipartite"]

g0=Graph[GraphData[{"FibonacciCube",4},"VertexList"],GraphData[{"FibonacciCube",4},"Edges"],GraphLayout->"BipartiteEmbedding"]

v=With[{n=Ceiling[GraphData[{"FibonacciCube",4},"V"]/2]-1},Flatten[Table[{i,j/n},{i,{-1,1}/2},{j,0,n}],1]];

g=FindCorrespondingGraph[g0,v]

RecognizeGraph@g

Bilateral

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

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

Circular

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

Circular construction

GraphData[{"FibonacciCube",4},"Hamiltonian"]

GraphData[{"FibonacciCube",4},"LCF"]

GraphData[{"FibonacciCube",4},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"FibonacciCube",4}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"FibonacciCube",4}],#]&/@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[{"FibonacciCube",4},"Planar"]

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

MinimalCrossing

GraphData[{"FibonacciCube",4},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"FibonacciCube",4}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"FibonacciCube",4},"Circulant"]

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

Halin

GraphData[{"FibonacciCube",4},"Halin"]

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

Rigid

GraphData[{"FibonacciCube",4},"Rigid"]

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

Flexible

GraphData[{"FibonacciCube",4},"Flexible"]

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

LCF

GraphData[{"FibonacciCube",4},"LCF"]

GraphData[{"FibonacciCube",4},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",4},"LCFSignature"]

GraphData[{"FibonacciCube",4},"LCFNotations"]

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

UnitDistance

GraphData[{"FibonacciCube",4},"UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

gs={,,,};

Matchstick

GraphData[{"FibonacciCube",4},"Matchstick"]

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

3D default

Graph3D[GraphData[{"FibonacciCube",4},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"FibonacciCube",4},"Polyhedral"]

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

{"FibonacciCube", 5}

Names

GraphData[{"FibonacciCube",5},"StandardName"]

GraphData[{"FibonacciCube",5},"StandardNames"]

HouseOfGraphs

hogid=GraphData[{"FibonacciCube",5},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"FibonacciCube",5},"WikidataID"]

GraphData[{"FibonacciCube",5},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

GraphData[{"FibonacciCube",5},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData[{"FibonacciCube",5},"Graph","Degenerate"]//Column

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",5}]]

Default embedding

g0=GraphPlot[Graph[GraphData[{"FibonacciCube",5},"VertexList"],GraphData[{"FibonacciCube",5},"Edges"]]]

v=Join[CirclePoints[6],{#/3,0}&/@{-1,1}];
v=Join[v,{v[[3]]+v[[3]]-v[[7]],v[[1]]+v[[1]]-v[[7]],v[[2]]+v[[2]]-v[[7]]}];
v=Join[v,Mean[v[[#]]]&/@{{9,11},{10,11}}];
ee={};
Graph[Range[Length[v]],UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

g=LabelGraph@FindCorrespondingGraph[,v]

RecognizeGraph@g

g0=LabelGraph@

v=GraphEmbedding[g0];
v=Join[v,{v[[7]]+v[[7]]-v[[8]],v[[6]]+v[[6]]-v[[8]]}];
v=Join[v,{v[[9]]-v[[3]]+v[[1]],v[[10]]-v[[7]]+v[[9]]}];
v=Join[v,{v[[11]]+v[[11]]-v[[9]]}];
g0=Graph[Range[Length[v]],{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

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

RecognizeGraph@g

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData[{"FibonacciCube",5},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"FibonacciCube",5},"Bipartite"]

GraphData[{"FibonacciCube",5},"Graph","Bipartite"]//StyleGraphs

Bipartite construction

GraphData[{"FibonacciCube",5},"Bipartite"]

g=BipartiteGraph[GraphData[{"FibonacciCube",5}]]

RecognizeGraph@g

Bilateral

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

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

Circular

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

Circular construction All

GraphData[{"FibonacciCube",5},"Hamiltonian"]

GraphData[{"FibonacciCube",5},"LCF"]

GraphData[{"FibonacciCube",5},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",5},"HamiltonianCycles"]

Planar

GraphData[{"FibonacciCube",5},"Planar"]

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

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"FibonacciCube",5}]],10]

PlanarGraphEmbeddings

GraphData[{"FibonacciCube",5},"PlanarEmbeddingCount"]

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

Length[plemb]

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"FibonacciCube",5}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossing

GraphData[{"FibonacciCube",5},"CN"]

(gs=GraphData[{"FibonacciCube",5},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",5},"RCN"]

GraphData[{"FibonacciCube",5},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"FibonacciCube",5},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",5},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

Circulant

GraphData[{"FibonacciCube",5},"Circulant"]

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

Circulant construction

GraphData[{"FibonacciCube",5},"NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData[{"FibonacciCube",5},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",5}]]//Timing

RootGraph

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

RootGraph[GraphData[{"FibonacciCube",5}]]

Halin

GraphData[{"FibonacciCube",5},"Halin"]

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

Rigid

GraphData[{"FibonacciCube",5},"Rigid"]

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

Flexible

GraphData[{"FibonacciCube",5},"Flexible"]

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

LCF

GraphData[{"FibonacciCube",5},"LCF"]

GraphData[{"FibonacciCube",5},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",5},"LCFSignature"]

GraphData[{"FibonacciCube",5},"LCFNotations"]

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

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

UnitDistance

GraphData[{"FibonacciCube",5},"UnitDistance"]

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

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

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

UnitDistance construction

GraphData[{"FibonacciCube",5},"Graph","UnitDistance"]

GraphData[{"FibonacciCube",5},{"TriangleCount","SquareCount"}]

GraphData["Q3","Graph","UnitDistance"]

GraphData[{"FibonacciCube",5},"Graphics"]

{x-1,y}+{u,v}-{x,y}

soln=Solve[{
(x-1)^2+y^2==1,
x==1/2},{x,y},Reals]

gs=Graph[Range[13],UndirectedEdge@@@{{1,2},{2,4},{3,4},{1,3},{2,6},{1,5},{5,6},{12,13},{6,13},{5,8},{8,9},{7,9},{9,10},{10,11},{7,11},{3,7},{11,12},{4,13},{5,7},{7,13}},VertexCoordinates->({{0,0},{1,0},{0,-1},{1,-1},{x-1,y},{x,y},{x-1,y-1},{x-2,y},{x-2,y-1},{x-2,y-2},{x-1,y-2},{x,y-2},{x,y-1}}/.#),VertexLabels->"Name"]&/@soln

RecognizeGraph/@gs

UnitDistanceGraphEmbeddingQ/@gs

DegenerateEmbeddingQ/@gs

nicegs=gs

Select[FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",5}],100],UnitDistanceGraphEmbeddingQ]//Timing

UnitDistance by refinement of default embeddings

Graph[edge list]

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

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

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

UnitDistanceGraphEmbeddingQ[g]

GraphData["Q3","Graph","UnitDistance"]

g0=LabelGraph@CenterGraph@RotateGraph[,45Degree]

v0=GraphEmbedding[g0];

dv=v0[[5]]-v0[[1]];

v=Join[v0,{v0[[5]]+dv,v0[[2]]+{1,-1}dv,v0[[6]]+dv,v0[[6]]+{1,-1}dv}];
v=FullSimplify@AppendTo[v,v[[12]]+dv];

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

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",5}],50,"ReturnWithMessage"->True];//Quiet//Timing

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

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

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

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

FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",5}],"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

Matchstick

GraphData[{"FibonacciCube",5},"Matchstick"]

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

3D default

Graph3D[GraphData[{"FibonacciCube",5},"Edges"]]

3D construction

3D All

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

3D UnitDistance construction Random

GraphData[{"FibonacciCube",5},"Dimension"]

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

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

GraphData[{"FibonacciCube",5},"Polyhedral"]

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

{"FibonacciCube", 6}

Names

GraphData[{"FibonacciCube",6},"StandardName"]

GraphData[{"FibonacciCube",6},"StandardNames"]

HouseOfGraphs

hogid=GraphData[{"FibonacciCube",6},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"FibonacciCube",6},"WikidataID"]

GraphData[{"FibonacciCube",6},"WikidataID","URL"]

Primary

GraphData[{"FibonacciCube",6}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"FibonacciCube",6},"Graph","All"]//StyleGraphs

CurvedEdge

GraphData[{"FibonacciCube",6},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

GraphData[{"FibonacciCube",6},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"FibonacciCube",6},"Graph","Degenerate"]//Column

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",6}]]

Default embedding

g=Graph[GraphData[{"FibonacciCube",6},"VertexList"],GraphData[{"FibonacciCube",6},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

DegenerateGraphEmbeddingTypes[g]

GeneralizedPetersen

GraphData[{"FibonacciCube",6},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"FibonacciCube",6},"Graph","IGraph"]//StyleGraphs

CompleteKPartite

GraphData[{"FibonacciCube",6},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"FibonacciCube",6},"Bipartite"]

GraphData[{"FibonacciCube",6},"Graph","Bipartite"]//StyleGraphs

Bipartite construction

GraphData[{"FibonacciCube",6},"Bipartite"]

g=BipartiteGraph[GraphData[{"FibonacciCube",6}]]

RecognizeGraph@g

Bilateral

GraphData[{"FibonacciCube",6},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"FibonacciCube",6},"Graph","Circular"]//StyleGraphs

Circular construction All

GraphData[{"FibonacciCube",6},"Hamiltonian"]

GraphData[{"FibonacciCube",6},"LCF"]

GraphData[{"FibonacciCube",6},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",6},"HamiltonianCycles"]

Planar

GraphData[{"FibonacciCube",6},"Planar"]

GraphData[{"FibonacciCube",6},"Graph","Planar"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de [verified 2]

CrossingNumber[GraphData[{"FibonacciCube",6}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData[{"FibonacciCube",6},"CN"]

(gs=GraphData[{"FibonacciCube",6},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",6},"RCN"]

GraphData[{"FibonacciCube",6},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Tutte

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

(g=MinimalCrossingGraph[GraphData[{"FibonacciCube",6}],"CrossingNumber"->cn])//PolyhedralGraphQ//AbsoluteTiming

MinimalCrossing construction Random 1k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

GraphData[{"FibonacciCube",6},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"FibonacciCube",6},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",6},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"FibonacciCube",6},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction 1000

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

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

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

MinimaRectilinearlLocalCrossing construction 20000

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

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

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

Circulant

GraphData[{"FibonacciCube",6},"Circulant"]

GraphData[{"FibonacciCube",6},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"FibonacciCube",6},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"FibonacciCube",6}]])//Timing

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"FibonacciCube",6},"ComplementGraph","Name"]

Line graph

GraphData[{"FibonacciCube",6},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",6}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"FibonacciCube",6}&]

RootGraph[GraphData[{"FibonacciCube",6}]]

Halin

GraphData[{"FibonacciCube",6},"Halin"]

GraphData[{"FibonacciCube",6},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"FibonacciCube",6},"Rigid"]

GraphData[{"FibonacciCube",6},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"FibonacciCube",6},"Flexible"]

GraphData[{"FibonacciCube",6},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"FibonacciCube",6},"LCF"]

GraphData[{"FibonacciCube",6},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",6},"LCFSignature"]

GraphData[{"FibonacciCube",6},"LCFNotations"]

GraphData[{"FibonacciCube",6},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"FibonacciCube",6},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"FibonacciCube",6}],Debug->True]//Timing

GraphData[{"FibonacciCube",6},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance construction

GraphData[{"FibonacciCube",6},"Graph","All"]

UnitDistanceEmbeddingRefine/@%

Select[%,UnitDistanceGraphEmbeddingQ]

GraphPlot[GraphData[{"FibonacciCube",6},"EdgeList"]]

UnitDistanceEmbeddingRefine@GraphicsToGraph@%

UnitDistanceGraphEmbeddingQ@%

g=RotateGraph[LabelGraph[],{6,13}]

UnitDistanceGraphEmbeddingQ[g]

v={{1,1},{x,y+1},{2,1},{0,1},{a,b},{1,0},{1,2},{x-1,y+1},{c,d-1},{x,y},{x,y+2},{a+1,b},{2,0},{2,2},{0,0},{0,2},{x-1,y},{x-1,y+2},{a,b+1},{c,d},{a+1,b+1}};
ee=EdgeList[g];
eqn=UnitEdgeEquations[v,ee]

soln=NSolve[eqn,{x,y,a,b,c,d},Reals]

soln=Solve[Append[eqn,x==1/2],{x,y,a,b,c,d},Reals]

soln[[1]]

Select[Graph[Range[Length[v]],ee,VertexCoordinates->(v/.#),VertexLabels->Automatic]&/@soln,UnitDistanceGraphEmbeddingQ]

Manipulate[(
soln=Solve[Join[eqn,{x==1/2,c==Rationalize[c0]}],{x,y,a,b,c,d},Reals];
Graph[Range[Length[v]],ee,VertexCoordinates->(v/.#),VertexLabels->Automatic]&/@soln),{c0,-1/2,3/2}]

square=RightAngleEquation[v,{1,2,9}]

soln=Solve[Join[eqn,{x==1/2,square}],{x,y,a,b,c,d},Reals];

gs=Select[Graph[Range[Length[v]],ee,VertexCoordinates->(v/.#),VertexLabels->Automatic]&/@soln,UnitDistanceGraphEmbeddingQ]

(ud=FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",6}],MaxIterations->10000])//Timing

UnitDistanceGraphEmbeddingQ[ud]

Select[FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",6}],100],UnitDistanceGraphEmbeddingQ]//Timing

UnitDistance by refinement of default embeddings

Graph[edge list]

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

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

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

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",6}],50,"ReturnWithMessage"->True];//Quiet//Timing

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

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

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

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

FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",6}],"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

gs=BilateralGraph/@CenterGraph/@{,,,,,,,,,}

Matchstick

GraphData[{"FibonacciCube",6},"Matchstick"]

GraphData[{"FibonacciCube",6},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"FibonacciCube",6},"Edges"]]

3D construction

3D All

GraphData[{"FibonacciCube",6},"Graph",{"3D","All"}]

3D UnitDistance construction Random

GraphData[{"FibonacciCube",6},"Dimension"]

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

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

GraphData[{"FibonacciCube",6},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"FibonacciCube",6},"Polyhedral"]

GraphData[{"FibonacciCube",6},"Graph",{"3D","Polyhedron"}]

{"FibonacciCube", 7}

Names

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

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

HouseOfGraphs

hogid=GraphData[{"FibonacciCube",7},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"FibonacciCube",7},"WikidataID"]

GraphData[{"FibonacciCube",7},"WikidataID","URL"]

Primary

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

All

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

Inexact

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

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData[{"FibonacciCube",7},"Graph","Degenerate"]//Column

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",7}]]

Default embedding

g0=GraphPlot[Graph[GraphData[{"FibonacciCube",7},"VertexList"],GraphData[{"FibonacciCube",7},"Edges"]]]

g=Graph[GraphData[{"FibonacciCube",7},"VertexList"],GraphData[{"FibonacciCube",7},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

DegenerateGraphEmbeddingTypes[g]

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData[{"FibonacciCube",7},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"FibonacciCube",7},"Bipartite"]

GraphData[{"FibonacciCube",7},"Graph","Bipartite"]//StyleGraphs

Bipartite construction

GraphData[{"FibonacciCube",7},"Bipartite"]

g0=Graph[GraphData[{"FibonacciCube",7},"VertexList"],GraphData[{"FibonacciCube",7},"Edges"],GraphLayout->"BipartiteEmbedding"]

v=With[{n=Ceiling[GraphData[{"FibonacciCube",7},"V"]/2]-1},Flatten[Table[{i,j/n},{i,{-1,1}/2},{j,0,n}],1]];

g=FindCorrespondingGraph[g0,v]

RecognizeGraph@g

Bilateral

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

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

Circular

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

Circular construction All [1610 s; none symmetric]

GraphData[{"FibonacciCube",7},"Hamiltonian"]

GraphData[{"FibonacciCube",7},"LCF"]

GraphData[{"FibonacciCube",7},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",7},"HamiltonianCycles"]

Length[hc=FindHamiltonianCycle[GraphData[{"FibonacciCube",7}],All][[All,All,1]]]//Timing

Length[hcsym=SymmetricHamiltonianCycles[GraphData[{"FibonacciCube",7}],hc,Debug->True]]//Timing

GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"FibonacciCube",7}],#]&/@hcsym,GraphSymmetryGroup]

Planar

GraphData[{"FibonacciCube",7},"Planar"]

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

MinimalCrossingNumber crossings.uos.de [verified 16]

CrossingNumber[GraphData[{"FibonacciCube",7}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData[{"FibonacciCube",7},"CN"]

(gs=GraphData[{"FibonacciCube",7},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",7},"RCN"]

GraphData[{"FibonacciCube",7},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Tutte

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

(g=MinimalCrossingGraph[GraphData[{"FibonacciCube",7}],"CrossingNumber"->cn])//PolyhedralGraphQ//AbsoluteTiming

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

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

MinimalCrossing construction Random 1k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

GraphData[{"FibonacciCube",7},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",7},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction 1000

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

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

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

MinimaRectilinearlLocalCrossing construction 20000

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

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

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

Circulant

GraphData[{"FibonacciCube",7},"Circulant"]

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

Circulant construction

GraphData[{"FibonacciCube",7},"NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData[{"FibonacciCube",7},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",7}]]//Timing

RootGraph

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

RootGraph[GraphData[{"FibonacciCube",7}]]

Halin

GraphData[{"FibonacciCube",7},"Halin"]

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

Rigid

GraphData[{"FibonacciCube",7},"Rigid"]

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

Flexible

GraphData[{"FibonacciCube",7},"Flexible"]

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

LCF

GraphData[{"FibonacciCube",7},"LCF"]

GraphData[{"FibonacciCube",7},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",7},"LCFSignature"]

GraphData[{"FibonacciCube",7},"LCFNotations"]

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

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

UnitDistance

GraphData[{"FibonacciCube",7},"UnitDistance"]

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

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

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

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

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",7}],50,"ReturnWithMessage"->True];//Quiet//Timing

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

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

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

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

FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",7}],"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding old

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

l=FindSubgraphIsomorphism[GraphData[{"FibonacciCube",7}],"Results"->All]//Timing

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"FibonacciCube",7},"Matchstick"]

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

3D default

Graph3D[GraphData[{"FibonacciCube",7},"Edges"]]

3D construction

3D All

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

3D UnitDistance construction Random

GraphData[{"FibonacciCube",7},"Dimension"]

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

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

GraphData[{"FibonacciCube",7},"Polyhedral"]

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

{"FibonacciCube", 8}

Names

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

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

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"FibonacciCube",8},"WikidataID"]

GraphData[{"FibonacciCube",8},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

GraphData[{"FibonacciCube",8},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData[{"FibonacciCube",8},"Graph","Degenerate"]//Column

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",8}]]

Default embedding

g=Graph[GraphData[{"FibonacciCube",8},"VertexList"],GraphData[{"FibonacciCube",8},"Edges"]]

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData[{"FibonacciCube",8},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"FibonacciCube",8},"Bipartite"]

GraphData[{"FibonacciCube",8},"Graph","Bipartite"]//StyleGraphs

Bipartite construction

GraphData[{"FibonacciCube",8},"Bipartite"]

g=BipartiteGraph[GraphData[{"FibonacciCube",8}]]

RecognizeGraph@g

Bilateral

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

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

Circular

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

Circular construction All

GraphData[{"FibonacciCube",8},"Hamiltonian"]

GraphData[{"FibonacciCube",8},"LCF"]

GraphData[{"FibonacciCube",8},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",8},"HamiltonianCycles"]

Planar

GraphData[{"FibonacciCube",8},"Planar"]

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

MinimalCrossingNumber crossings.uos.de [failed]

CrossingNumber[GraphData[{"FibonacciCube",8}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData[{"FibonacciCube",8},"CN"]

(gs=GraphData[{"FibonacciCube",8},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",8},"RCN"]

GraphData[{"FibonacciCube",8},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

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

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

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

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

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

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

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

Take[gs,UpTo[100]]

MinimalCrossing construction Tutte

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

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

MinimalCrossing construction Random 1k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

GraphData[{"FibonacciCube",8},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",8},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction 1000

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

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

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

MinimaRectilinearlLocalCrossing construction 20000

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

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

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

Circulant

GraphData[{"FibonacciCube",8},"Circulant"]

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

Circulant construction

GraphData[{"FibonacciCube",8},"NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData[{"FibonacciCube",8},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",8}]]//Timing

RootGraph

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

RootGraph[GraphData[{"FibonacciCube",8}]]

Halin

GraphData[{"FibonacciCube",8},"Halin"]

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

Rigid

GraphData[{"FibonacciCube",8},"Rigid"]

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

Flexible

GraphData[{"FibonacciCube",8},"Flexible"]

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

LCF

GraphData[{"FibonacciCube",8},"LCF"]

GraphData[{"FibonacciCube",8},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",8},"LCFSignature"]

GraphData[{"FibonacciCube",8},"LCFNotations"]

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

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

UnitDistance

GraphData[{"FibonacciCube",8},"UnitDistance"]

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

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

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

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

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",8}],50,"ReturnWithMessage"->True];//Quiet//Timing

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

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

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

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

FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",8}],"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding original

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

gs=UniqueEmbeddings[l]

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

Matchstick

GraphData[{"FibonacciCube",8},"Matchstick"]

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

3D default

Graph3D[GraphData[{"FibonacciCube",8},"Edges"]]

3D construction

3D All

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

3D UnitDistance construction Random

GraphData[{"FibonacciCube",8},"Dimension"]

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

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

GraphData[{"FibonacciCube",8},"Polyhedral"]

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

{"FibonacciCube", 9}

Names

GraphData[{"FibonacciCube",9},"StandardName"]

GraphData[{"FibonacciCube",9},"StandardNames"]

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"FibonacciCube",9},"WikidataID"]

GraphData[{"FibonacciCube",9},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

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

Inexact

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

Degenerate

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

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

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",9}]]

Default embedding

g0=GraphPlot[Graph[GraphData[{"FibonacciCube",9},"VertexList"],GraphData[{"FibonacciCube",9},"Edges"]]]

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

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

Bipartite

GraphData[{"FibonacciCube",9},"Bipartite"]

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

Bipartite construction

GraphData[{"FibonacciCube",9},"Bipartite"]

g=BipartiteGraph[GraphData[{"FibonacciCube",9}]]

RecognizeGraph@g

Bilateral

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

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

Circular

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

Circular construction All

GraphData[{"FibonacciCube",9},"Hamiltonian"]

GraphData[{"FibonacciCube",9},"LCF"]

GraphData[{"FibonacciCube",9},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",9},"HamiltonianCycles"]

Planar

GraphData[{"FibonacciCube",9},"Planar"]

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

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"FibonacciCube",9}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData[{"FibonacciCube",9},"CN"]

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

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",9},"RCN"]

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

MinimalRectilinearCrossing construction order X [minimum RCN == ]

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

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

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

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

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

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

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

Take[gs,UpTo[100]]

MinimalCrossing construction Tutte

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

(g=MinimalCrossingGraph[GraphData[{"FibonacciCube",9}],"CrossingNumber"->cn])//PolyhedralGraphQ//AbsoluteTiming

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

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

MinimalCrossing construction Random 1k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

GraphData[{"FibonacciCube",9},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",9},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction 1000

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

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

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

MinimaRectilinearlLocalCrossing construction 20000

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

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

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

Circulant

GraphData[{"FibonacciCube",9},"Circulant"]

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

Circulant construction

GraphData[{"FibonacciCube",9},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"FibonacciCube",9}]])//Timing

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData[{"FibonacciCube",9},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",9}]]//Timing

RootGraph

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

RootGraph[GraphData[{"FibonacciCube",9}]]

Halin

GraphData[{"FibonacciCube",9},"Halin"]

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

Rigid

GraphData[{"FibonacciCube",9},"Rigid"]

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

Flexible

GraphData[{"FibonacciCube",9},"Flexible"]

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

LCF

GraphData[{"FibonacciCube",9},"LCF"]

GraphData[{"FibonacciCube",9},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",9},"LCFSignature"]

GraphData[{"FibonacciCube",9},"LCFNotations"]

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

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

UnitDistance

GraphData[{"FibonacciCube",9},"UnitDistance"]

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

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

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

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

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

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

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding original

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

gs=UniqueEmbeddings[l]

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

gs={,,,,,,,,,,,};

Select[gs,DegenerateGraphEmbeddingQ]//Timing

DegenerateGraphEmbeddingTypes@

Select[gs,FreeQ[#,_?InexactNumberQ]&]

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

Matchstick

GraphData[{"FibonacciCube",9},"Matchstick"]

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

3D default

Graph3D[GraphData[{"FibonacciCube",9},"Edges"]]

3D construction

3D All

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

3D UnitDistance construction Random

GraphData[{"FibonacciCube",9},"Dimension"]

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

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

GraphData[{"FibonacciCube",9},"Polyhedral"]

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

{"FibonacciCube", 10}

Names

GraphData[{"FibonacciCube",10},"StandardName"]

GraphData[{"FibonacciCube",10},"StandardNames"]

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"FibonacciCube",10},"WikidataID"]

GraphData[{"FibonacciCube",10},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

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

Inexact

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

Degenerate

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

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

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",10}]]

Default embedding

g0=GraphPlot[Graph[GraphData[{"FibonacciCube",10},"VertexList"],GraphData[{"FibonacciCube",10},"Edges"]]]

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

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

Bipartite

GraphData[{"FibonacciCube",10},"Bipartite"]

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

Bipartite construction

GraphData[{"FibonacciCube",10},"Bipartite"]

g=BipartiteGraph[GraphData[{"FibonacciCube",10}]]

RecognizeGraph@g

Bilateral

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

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

Circular

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

Circular construction 1*^4 [0.4 + 8 s]

Length[hc=FindHamiltonianCycle[GraphData[{"FibonacciCube",10}],1*^4][[All,All,1]]]//Timing

Length[hcsym=SymmetricHamiltonianCycles[GraphData[{"FibonacciCube",10}],hc,Debug->True]]//Timing

GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"FibonacciCube",10}],#]&/@hcsym,GraphSymmetryGroup]

Circular construction 1*^5 [1.3 + 83 s]

Length[hc=FindHamiltonianCycle[GraphData[{"FibonacciCube",10}],1*^5][[All,All,1]]]//Timing

Length[hcsym=SymmetricHamiltonianCycles[GraphData[{"FibonacciCube",10}],hc,Debug->True]]//Timing

GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"FibonacciCube",10}],#]&/@hcsym,GraphSymmetryGroup]

Circular construction 1*^6 [13 + 819 s]

Length[hc=FindHamiltonianCycle[GraphData[{"FibonacciCube",10}],1*^6][[All,All,1]]]//Timing

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

GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"FibonacciCube",10}],#]&/@hcsym,GraphSymmetryGroup]

Circular construction 1*^7 [13 + 819 s; 106 GB]

Length[hc=FindHamiltonianCycle[GraphData[{"FibonacciCube",10}],1*^7][[All,All,1]]]//Timing

MaxMemoryUsed[]/10^9.GB

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

MaxMemoryUsed[]/10^9.GB

GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"FibonacciCube",10}],#]&/@hcsym,GraphSymmetryGroup]

Circular construction All

GraphData[{"FibonacciCube",10},"Hamiltonian"]

GraphData[{"FibonacciCube",10},"LCF"]

GraphData[{"FibonacciCube",10},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",10},"HamiltonianCycles"]

Planar

GraphData[{"FibonacciCube",10},"Planar"]

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

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"FibonacciCube",10}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData[{"FibonacciCube",10},"CN"]

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

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",10},"RCN"]

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

MinimalCrossing construction Tutte

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

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

MinimalCrossing construction Random 1k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

GraphData[{"FibonacciCube",10},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",10},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction 1000

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

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

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

MinimaRectilinearlLocalCrossing construction 20000

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

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

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

Circulant

GraphData[{"FibonacciCube",10},"Circulant"]

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

Circulant construction

GraphData[{"FibonacciCube",10},"NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData[{"FibonacciCube",10},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",10}]]//Timing

RootGraph

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

RootGraph[GraphData[{"FibonacciCube",10}]]

Halin

GraphData[{"FibonacciCube",10},"Halin"]

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

Rigid

GraphData[{"FibonacciCube",10},"Rigid"]

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

Flexible

GraphData[{"FibonacciCube",10},"Flexible"]

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

LCF

GraphData[{"FibonacciCube",10},"LCF"]

GraphData[{"FibonacciCube",10},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",10},"LCFSignature"]

GraphData[{"FibonacciCube",10},"LCFNotations"]

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

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

UnitDistance

GraphData[{"FibonacciCube",10},"UnitDistance"]

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

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

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

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

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

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

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding original

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

gs=UniqueEmbeddings[l]

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

Matchstick

GraphData[{"FibonacciCube",10},"Matchstick"]

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

3D default

Graph3D[GraphData[{"FibonacciCube",10},"Edges"]]

3D construction

3D All

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

3D UnitDistance construction Random

GraphData[{"FibonacciCube",10},"Dimension"]

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

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

GraphData[{"FibonacciCube",10},"Polyhedral"]

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

{"FibonacciCube", 11}

Names

GraphData[{"FibonacciCube",11},"StandardName"]

GraphData[{"FibonacciCube",11},"StandardNames"]

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"FibonacciCube",11},"WikidataID"]

GraphData[{"FibonacciCube",11},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

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

Inexact

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

Degenerate

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

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

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",11}]]

Default embedding

g0=GraphPlot[Graph[GraphData[{"FibonacciCube",11},"VertexList"],GraphData[{"FibonacciCube",11},"Edges"]]]

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

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

Bipartite

GraphData[{"FibonacciCube",11},"Bipartite"]

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

Bipartite construction

GraphData[{"FibonacciCube",11},"Bipartite"]

g=BipartiteGraph[GraphData[{"FibonacciCube",11}]]

RecognizeGraph@g

Bilateral

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

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

Circular

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

Circular construction All

GraphData[{"FibonacciCube",11},"Hamiltonian"]

GraphData[{"FibonacciCube",11},"LCF"]

GraphData[{"FibonacciCube",11},"HamiltonianCycleCount"]

Planar

GraphData[{"FibonacciCube",11},"Planar"]

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

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"FibonacciCube",11}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData[{"FibonacciCube",11},"CN"]

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

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",11},"RCN"]

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

MinimalCrossing construction Tutte

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

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

MinimalCrossing construction Random 1k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

GraphData[{"FibonacciCube",11},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",11},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction 1000

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

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

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

MinimaRectilinearlLocalCrossing construction 20000

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

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

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

Circulant

GraphData[{"FibonacciCube",11},"Circulant"]

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

Circulant construction

GraphData[{"FibonacciCube",11},"NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData[{"FibonacciCube",11},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",11}]]//Timing

RootGraph

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

RootGraph[GraphData[{"FibonacciCube",11}]]

Halin

GraphData[{"FibonacciCube",11},"Halin"]

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

Rigid

GraphData[{"FibonacciCube",11},"Rigid"]

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

Flexible

GraphData[{"FibonacciCube",11},"Flexible"]

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

LCF

GraphData[{"FibonacciCube",11},"LCF"]

GraphData[{"FibonacciCube",11},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",11},"LCFSignature"]

GraphData[{"FibonacciCube",11},"LCFNotations"]

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

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

UnitDistance

GraphData[{"FibonacciCube",11},"UnitDistance"]

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

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

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

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

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

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

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

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

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

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

Matchstick

GraphData[{"FibonacciCube",11},"Matchstick"]

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

3D default

Graph3D[GraphData[{"FibonacciCube",11},"Edges"]]

3D construction

3D All

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

3D UnitDistance construction Random

GraphData[{"FibonacciCube",11},"Dimension"]

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

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

GraphData[{"FibonacciCube",11},"Polyhedral"]

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

{"FibonacciCube", 12}

Names

GraphData[{"FibonacciCube",12},"StandardName"]

GraphData[{"FibonacciCube",12},"StandardNames"]

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"FibonacciCube",12},"WikidataID"]

GraphData[{"FibonacciCube",12},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

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

Inexact

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

Degenerate

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

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

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",12}]]

Default embedding

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

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

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

Bipartite

GraphData[{"FibonacciCube",12},"Bipartite"]

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

Bipartite construction

GraphData[{"FibonacciCube",12},"Bipartite"]

g=BipartiteGraph[GraphData[{"FibonacciCube",12}]]

RecognizeGraph@g

Bilateral

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

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

Circular

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

Circular construction All

GraphData[{"FibonacciCube",12},"Hamiltonian"]

GraphData[{"FibonacciCube",12},"LCF"]

GraphData[{"FibonacciCube",12},"HamiltonianCycleCount"]

Planar

GraphData[{"FibonacciCube",12},"Planar"]

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

MinimalCrossingNumber crossings.uos.de

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

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData[{"FibonacciCube",12},"CN"]

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

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",12},"RCN"]

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

MinimalCrossing construction Tutte

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

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

MinimalCrossing construction Random 1k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k

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

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

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

Small numbers of crossing points on the boundary:

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

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

Symmetric embeddings:

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

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

GraphData[{"FibonacciCube",12},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",12},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction 1000

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

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

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

MinimaRectilinearlLocalCrossing construction 20000

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

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

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

Circulant

GraphData[{"FibonacciCube",12},"Circulant"]

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

Circulant construction

GraphData[{"FibonacciCube",12},"NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData[{"FibonacciCube",12},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",12}]]//Timing

RootGraph

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

RootGraph[GraphData[{"FibonacciCube",12}]]

Halin

GraphData[{"FibonacciCube",12},"Halin"]

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

Rigid

GraphData[{"FibonacciCube",12},"Rigid"]

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

Flexible

GraphData[{"FibonacciCube",12},"Flexible"]

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

LCF

GraphData[{"FibonacciCube",12},"LCF"]

GraphData[{"FibonacciCube",12},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",12},"LCFSignature"]

GraphData[{"FibonacciCube",12},"LCFNotations"]

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

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

UnitDistance

GraphData[{"FibonacciCube",12},"UnitDistance"]

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

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

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

UnitDistance by refinement of default embeddings

Graph[edge list]

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

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

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

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

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

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

Cases[gdata,{__,0.}]

Symmetric:

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

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

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

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

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

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

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

Matchstick

GraphData[{"FibonacciCube",12},"Matchstick"]

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

3D default

Graph3D[GraphData[{"FibonacciCube",12},"Edges"]]

3D construction

3D All

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

3D UnitDistance construction Random

GraphData[{"FibonacciCube",12},"Dimension"]

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

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

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

3D Polyhedron

GraphData[{"FibonacciCube",12},"Polyhedral"]

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

{"FibonacciCube", 13}

Names

GraphData[{"FibonacciCube",13},"StandardName"]

GraphData[{"FibonacciCube",13},"StandardNames"]

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"FibonacciCube",13},"WikidataID"]

GraphData[{"FibonacciCube",13},"WikidataID","URL"]

Primary

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

All

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

CurvedEdge

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

Inexact

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

Degenerate

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

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

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",13}]]

Default embedding

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

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

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

Bipartite

GraphData[{"FibonacciCube",13},"Bipartite"]

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

Bipartite construction

GraphData[{"FibonacciCube",13},"Bipartite"]

g=BipartiteGraph[GraphData[{"FibonacciCube",13}]]

RecognizeGraph@g

Bilateral

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

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

Circular

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

Circular construction 10 [135k s]

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

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

GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"FibonacciCube",13}],#]&/@hcsym,GraphSymmetryGroup]

Circular construction 100 [ s]

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

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

GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"FibonacciCube",13}],#]&/@hcsym,GraphSymmetryGroup]

Circular construction All

GraphData[{"FibonacciCube",13},"Hamiltonian"]

GraphData[{"FibonacciCube",13},"LCF"]

GraphData[{"FibonacciCube",13},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",13},"HamiltonianCycles"]

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

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

GroupBy[SymmetricHamiltonianCycleGraph[GraphData[{"FibonacciCube",13}],#]&/@hcsym,GraphSymmetryGroup]

Planar

GraphData[{"FibonacciCube",13},"Planar"]

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

MinimalCrossingNumber crossings.uos.de

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

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData[{"FibonacciCube",13},"CN"]

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

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",13},"RCN"]

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

MinimalCrossing construction Tutte

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

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

MinimalCrossing construction Random 1k

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

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

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"FibonacciCube",13},"V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"FibonacciCube",13},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalCrossing construction Random 20k

(cn=CrossingNumber[GraphData[{"FibonacciCube",13}],TimeConstraint->1])//AbsoluteTiming

(RandomGraphs=Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",13}],"CrossingNumber"->cn,RandomSeed->n],{n,20000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"FibonacciCube",13},"V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"FibonacciCube",13},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalLocalCrossing

GraphData[{"FibonacciCube",13},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"FibonacciCube",13},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",13},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"FibonacciCube",13},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction 1000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"FibonacciCube",13}],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",13}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

MinimaRectilinearlLocalCrossing construction 20000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"FibonacciCube",13}],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",13}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Circulant

GraphData[{"FibonacciCube",13},"Circulant"]

GraphData[{"FibonacciCube",13},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"FibonacciCube",13},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"FibonacciCube",13}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"FibonacciCube",13},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"FibonacciCube",13},"ComplementGraph","Name"]

Line graph

GraphData[{"FibonacciCube",13},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",13}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"FibonacciCube",13}&]

RootGraph[GraphData[{"FibonacciCube",13}]]

Halin

GraphData[{"FibonacciCube",13},"Halin"]

GraphData[{"FibonacciCube",13},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"FibonacciCube",13},"Rigid"]

GraphData[{"FibonacciCube",13},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"FibonacciCube",13},"Flexible"]

GraphData[{"FibonacciCube",13},"Graph","Flexible"]//StyleGraphs

HamiltonianCycle compute all batch

LCF

GraphData[{"FibonacciCube",13},"LCF"]

GraphData[{"FibonacciCube",13},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",13},"LCFSignature"]

GraphData[{"FibonacciCube",13},"LCFNotations"]

GraphData[{"FibonacciCube",13},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData[{"FibonacciCube",13},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"FibonacciCube",13}],Debug->True]//Timing

GraphData[{"FibonacciCube",13},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"FibonacciCube",13},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"FibonacciCube",13},"VertexList"],GraphData[{"FibonacciCube",13},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

gs=UnitDistanceEmbeddingRefine[Graph[VertexList[#],EdgeList[#],VertexCoordinates->GraphEmbedding[#]],MaxIterations->500]&/@Complement@@(GraphData[{"FibonacciCube",13},"Graph",#]&/@{"All","UnitDistance"})

TextGrid[
gdata=SortBy[
{#,DegenerateGraphEmbeddingQ[#],GraphSymmetryGroup[#],Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
],
Dividers->All
]

Cases[gdata,{__,0.}]

Symmetric:

gs=Cases[
gdata,
{g_,_,sym:Except[TransformationGroup[{}]],diff_}:>{
HighlightGraph[g1=BilateralGraph[CenterGraph[g],"ReturnNonbilateralGraph"->True],Flatten[FindCoincidentVertices[g1]]],
sym,
diff
}]

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",13}],50,"ReturnWithMessage"->True];//Quiet//Timing

gdata=SortBy[
{#,Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
]

Cases[gdata,{g_?UnitDistanceGraphEmbeddingQ,_}:>g]

SymmetricEmebddings=Select[gdata,GraphSymmetryGroup[#[[1]]]=!=TransformationGroup[{}]&]

UnitDistance by FindUnitDistanceEmbedding  (random embedding waiting until UD is found)

FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",13}],"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

{{"FibonacciCube",13},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"FibonacciCube",13}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Select[IndexGraph/@gs,!DegenerateGraphEmbeddingQ[#]&&GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]//Timing

Matchstick

GraphData[{"FibonacciCube",13},"Matchstick"]

GraphData[{"FibonacciCube",13},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"FibonacciCube",13},"Edges"]]

3D construction

3D All

GraphData[{"FibonacciCube",13},"Graph",{"3D","All"}]

3D UnitDistance construction Random

GraphData[{"FibonacciCube",13},"Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData[{"FibonacciCube",13},"VertexList"],
GraphData[{"FibonacciCube",13},"EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

GraphData[{"FibonacciCube",13},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"FibonacciCube",13},"Polyhedral"]

GraphData[{"FibonacciCube",13},"Graph",{"3D","Polyhedron"}]

{"FibonacciCube", 14}

Names

GraphData[{"FibonacciCube",14},"StandardName"]

GraphData[{"FibonacciCube",14},"StandardNames"]

HouseOfGraphs

hogid=GraphData[{"FibonacciCube",14},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"FibonacciCube",14},"WikidataID"]

GraphData[{"FibonacciCube",14},"WikidataID","URL"]

Primary

GraphData[{"FibonacciCube",14}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"FibonacciCube",14},"Graph","All"]//StyleGraphs

CurvedEdge

GraphData[{"FibonacciCube",14},"Graph","CurvedEdge"]//StyleGraphs

Inexact

Select[GraphData[{"FibonacciCube",14},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Degenerate

GraphData[{"FibonacciCube",14},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"FibonacciCube",14},"Graph","Degenerate"]//Column

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",14}]]

Default embedding

g0=GraphPlot[Graph[GraphData[{"FibonacciCube",14},"VertexList"],GraphData[{"FibonacciCube",14},"Edges"]]]

GeneralizedPetersen

GraphData[{"FibonacciCube",14},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"FibonacciCube",14},"Graph","IGraph"]//StyleGraphs

CompleteKPartite

GraphData[{"FibonacciCube",14},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"FibonacciCube",14},"Bipartite"]

GraphData[{"FibonacciCube",14},"Graph","Bipartite"]//StyleGraphs

Bipartite construction

GraphData[{"FibonacciCube",14},"Bipartite"]

g=BipartiteGraph[GraphData[{"FibonacciCube",14}]]

RecognizeGraph@g

Bilateral

GraphData[{"FibonacciCube",14},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"FibonacciCube",14},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]//Quiet

Circular

GraphData[{"FibonacciCube",14},"Graph","Circular"]//StyleGraphs

Circular construction All

GraphData[{"FibonacciCube",14},"Hamiltonian"]

GraphData[{"FibonacciCube",14},"LCF"]

GraphData[{"FibonacciCube",14},"HamiltonianCycleCount"]

Planar

GraphData[{"FibonacciCube",14},"Planar"]

GraphData[{"FibonacciCube",14},"Graph","Planar"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"FibonacciCube",14}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"FibonacciCube",14},"CN"]

(gs=GraphData[{"FibonacciCube",14},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",14},"RCN"]

GraphData[{"FibonacciCube",14},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"FibonacciCube",14}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"FibonacciCube",14}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction Tutte

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"FibonacciCube",14}],"CrossingNumber"->cn])//PolyhedralGraphQ//AbsoluteTiming

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

TutteGraphs=BilateralGraph[CenterGraph@IGLayoutTutte[g,"OuterFace"->#],"ReturnNonbilateralGraph"->True]&/@faces

TutteGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"FibonacciCube",14},"V"]])]
}&/@TutteGraphs;

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

LocalCrossingNumberWithEmbeddings=
{1+Max[Length/@DeleteCases[
Drop[AdjacencyList[#],GraphData[{"FibonacciCube",14},"V"]],
_Integer?(LessEqualThan[GraphData[{"FibonacciCube",14},"V"]]),
{2}
]],#}&/@TutteGraphs

TutteGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"FibonacciCube",14},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@TutteGraphs;

SymmetricEmbeddingsWithOrientations=DeleteCases[
TutteGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]

Select[SymmetricEmbeddingsWithOrientations[[All,1]],Count[OuterFace[#],_?(GreaterThan[GraphData[{"FibonacciCube",14},"V"]])]==0&]

MinimalCrossing construction Random 1k

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],TimeConstraint->1])//AbsoluteTiming

(RandomGraphs=Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",14}],"CrossingNumber"->cn,RandomSeed->n],{n,1000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"FibonacciCube",14},"V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"FibonacciCube",14},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalCrossing construction Random 20k

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],TimeConstraint->1])//AbsoluteTiming

(RandomGraphs=Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",14}],"CrossingNumber"->cn,RandomSeed->n],{n,20000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"FibonacciCube",14},"V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"FibonacciCube",14},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalLocalCrossing

GraphData[{"FibonacciCube",14},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"FibonacciCube",14},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",14},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"FibonacciCube",14},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction 1000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",14}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

MinimaRectilinearlLocalCrossing construction 20000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"FibonacciCube",14}],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",14}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Circulant

GraphData[{"FibonacciCube",14},"Circulant"]

GraphData[{"FibonacciCube",14},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"FibonacciCube",14},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"FibonacciCube",14}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"FibonacciCube",14},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"FibonacciCube",14},"ComplementGraph","Name"]

Line graph

GraphData[{"FibonacciCube",14},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",14}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"FibonacciCube",14}&]

RootGraph[GraphData[{"FibonacciCube",14}]]

Halin

GraphData[{"FibonacciCube",14},"Halin"]

GraphData[{"FibonacciCube",14},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"FibonacciCube",14},"Rigid"]

GraphData[{"FibonacciCube",14},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"FibonacciCube",14},"Flexible"]

GraphData[{"FibonacciCube",14},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"FibonacciCube",14},"LCF"]

GraphData[{"FibonacciCube",14},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",14},"LCFSignature"]

GraphData[{"FibonacciCube",14},"LCFNotations"]

GraphData[{"FibonacciCube",14},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData[{"FibonacciCube",14},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"FibonacciCube",14}],Debug->True]//Timing

GraphData[{"FibonacciCube",14},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"FibonacciCube",14},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"FibonacciCube",14},"VertexList"],GraphData[{"FibonacciCube",14},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

gs=UnitDistanceEmbeddingRefine[Graph[VertexList[#],EdgeList[#],VertexCoordinates->GraphEmbedding[#]],MaxIterations->500]&/@Complement@@(GraphData[{"FibonacciCube",14},"Graph",#]&/@{"All","UnitDistance"})

TextGrid[
gdata=SortBy[
{#,DegenerateGraphEmbeddingQ[#],GraphSymmetryGroup[#],Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
],
Dividers->All
]

Cases[gdata,{__,0.}]

Symmetric:

gs=Cases[
gdata,
{g_,_,sym:Except[TransformationGroup[{}]],diff_}:>{
HighlightGraph[g1=BilateralGraph[CenterGraph[g],"ReturnNonbilateralGraph"->True],Flatten[FindCoincidentVertices[g1]]],
sym,
diff
}]

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",14}],50,"ReturnWithMessage"->True];//Quiet//Timing

gdata=SortBy[
{#,Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
]

Cases[gdata,{g_?UnitDistanceGraphEmbeddingQ,_}:>g]

SymmetricEmebddings=Select[gdata,GraphSymmetryGroup[#[[1]]]=!=TransformationGroup[{}]&]

UnitDistance by FindUnitDistanceEmbedding  (random embedding waiting until UD is found)

FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",14}],"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

{{"FibonacciCube",14},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"FibonacciCube",14}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Select[IndexGraph/@gs,!DegenerateGraphEmbeddingQ[#]&&GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]//Timing

Matchstick

GraphData[{"FibonacciCube",14},"Matchstick"]

GraphData[{"FibonacciCube",14},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"FibonacciCube",14},"Edges"]]

3D construction

3D All

GraphData[{"FibonacciCube",14},"Graph",{"3D","All"}]

3D UnitDistance construction Random

GraphData[{"FibonacciCube",14},"Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData[{"FibonacciCube",14},"VertexList"],
GraphData[{"FibonacciCube",14},"EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

GraphData[{"FibonacciCube",14},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"FibonacciCube",14},"Polyhedral"]

GraphData[{"FibonacciCube",14},"Graph",{"3D","Polyhedron"}]

{"FibonacciCube", 15}

Names

GraphData[{"FibonacciCube",15},"StandardName"]

GraphData[{"FibonacciCube",15},"StandardNames"]

HouseOfGraphs

hogid=GraphData[{"FibonacciCube",15},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"FibonacciCube",15},"WikidataID"]

GraphData[{"FibonacciCube",15},"WikidataID","URL"]

Primary

GraphData[{"FibonacciCube",15}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"FibonacciCube",15},"Graph","All"]//StyleGraphs

CurvedEdge

GraphData[{"FibonacciCube",15},"Graph","CurvedEdge"]//StyleGraphs

Inexact

Select[GraphData[{"FibonacciCube",15},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Degenerate

GraphData[{"FibonacciCube",15},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"FibonacciCube",15},"Graph","Degenerate"]//Column

Embeddings

GraphDataEmbeddings[GraphData[{"FibonacciCube",15}]]

Default embedding

g0=GraphPlot[Graph[GraphData[{"FibonacciCube",15},"VertexList"],GraphData[{"FibonacciCube",15},"Edges"]]]

GeneralizedPetersen

GraphData[{"FibonacciCube",15},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"FibonacciCube",15},"Graph","IGraph"]//StyleGraphs

CompleteKPartite

GraphData[{"FibonacciCube",15},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"FibonacciCube",15},"Bipartite"]

GraphData[{"FibonacciCube",15},"Graph","Bipartite"]//StyleGraphs

Bipartite construction

GraphData[{"FibonacciCube",15},"Bipartite"]

g=BipartiteGraph[GraphData[{"FibonacciCube",15}]]

RecognizeGraph@g

Bilateral

GraphData[{"FibonacciCube",15},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"FibonacciCube",15},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]//Quiet

Circular

GraphData[{"FibonacciCube",15},"Graph","Circular"]//StyleGraphs

Circular construction All

GraphData[{"FibonacciCube",15},"Hamiltonian"]

GraphData[{"FibonacciCube",15},"LCF"]

GraphData[{"FibonacciCube",15},"HamiltonianCycleCount"]

Planar

GraphData[{"FibonacciCube",15},"Planar"]

GraphData[{"FibonacciCube",15},"Graph","Planar"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"FibonacciCube",15}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"FibonacciCube",15},"CN"]

(gs=GraphData[{"FibonacciCube",15},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"FibonacciCube",15},"RCN"]

GraphData[{"FibonacciCube",15},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Tutte

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"FibonacciCube",15}],"CrossingNumber"->cn])//PolyhedralGraphQ//AbsoluteTiming

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

TutteGraphs=BilateralGraph[CenterGraph@IGLayoutTutte[g,"OuterFace"->#],"ReturnNonbilateralGraph"->True]&/@faces

TutteGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"FibonacciCube",15},"V"]])]
}&/@TutteGraphs;

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

LocalCrossingNumberWithEmbeddings=
{1+Max[Length/@DeleteCases[
Drop[AdjacencyList[#],GraphData[{"FibonacciCube",15},"V"]],
_Integer?(LessEqualThan[GraphData[{"FibonacciCube",15},"V"]]),
{2}
]],#}&/@TutteGraphs

TutteGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"FibonacciCube",15},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@TutteGraphs;

SymmetricEmbeddingsWithOrientations=DeleteCases[
TutteGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]

Select[SymmetricEmbeddingsWithOrientations[[All,1]],Count[OuterFace[#],_?(GreaterThan[GraphData[{"FibonacciCube",15},"V"]])]==0&]

MinimalCrossing construction Random 1k

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],TimeConstraint->1])//AbsoluteTiming

(RandomGraphs=Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",15}],"CrossingNumber"->cn,RandomSeed->n],{n,1000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"FibonacciCube",15},"V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"FibonacciCube",15},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalCrossing construction Random 20k

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],TimeConstraint->1])//AbsoluteTiming

(RandomGraphs=Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",15}],"CrossingNumber"->cn,RandomSeed->n],{n,20000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"FibonacciCube",15},"V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"FibonacciCube",15},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalLocalCrossing

GraphData[{"FibonacciCube",15},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"FibonacciCube",15},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"FibonacciCube",15},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"FibonacciCube",15},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction 1000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",15}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

MinimaRectilinearlLocalCrossing construction 20000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"FibonacciCube",15}],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"FibonacciCube",15}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Circulant

GraphData[{"FibonacciCube",15},"Circulant"]

GraphData[{"FibonacciCube",15},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"FibonacciCube",15},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"FibonacciCube",15}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"FibonacciCube",15},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"FibonacciCube",15},"ComplementGraph","Name"]

Line graph

GraphData[{"FibonacciCube",15},"Line"]

LineGraphQ[GraphData[{"FibonacciCube",15}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"FibonacciCube",15}&]

RootGraph[GraphData[{"FibonacciCube",15}]]

Halin

GraphData[{"FibonacciCube",15},"Halin"]

GraphData[{"FibonacciCube",15},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"FibonacciCube",15},"Rigid"]

GraphData[{"FibonacciCube",15},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"FibonacciCube",15},"Flexible"]

GraphData[{"FibonacciCube",15},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"FibonacciCube",15},"LCF"]

GraphData[{"FibonacciCube",15},"HamiltonianCycleCount"]

GraphData[{"FibonacciCube",15},"LCFSignature"]

GraphData[{"FibonacciCube",15},"LCFNotations"]

GraphData[{"FibonacciCube",15},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData[{"FibonacciCube",15},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"FibonacciCube",15}],Debug->True]//Timing

GraphData[{"FibonacciCube",15},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"FibonacciCube",15},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"FibonacciCube",15},"VertexList"],GraphData[{"FibonacciCube",15},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

gs=UnitDistanceEmbeddingRefine[Graph[VertexList[#],EdgeList[#],VertexCoordinates->GraphEmbedding[#]],MaxIterations->500]&/@Complement@@(GraphData[{"FibonacciCube",15},"Graph",#]&/@{"All","UnitDistance"})

TextGrid[
gdata=SortBy[
{#,DegenerateGraphEmbeddingQ[#],GraphSymmetryGroup[#],Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
],
Dividers->All
]

Cases[gdata,{__,0.}]

Symmetric:

gs=Cases[
gdata,
{g_,_,sym:Except[TransformationGroup[{}]],diff_}:>{
HighlightGraph[g1=BilateralGraph[CenterGraph[g],"ReturnNonbilateralGraph"->True],Flatten[FindCoincidentVertices[g1]]],
sym,
diff
}]

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",15}],50,"ReturnWithMessage"->True];//Quiet//Timing

gdata=SortBy[
{#,Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
]

Cases[gdata,{g_?UnitDistanceGraphEmbeddingQ,_}:>g]

SymmetricEmebddings=Select[gdata,GraphSymmetryGroup[#[[1]]]=!=TransformationGroup[{}]&]

UnitDistance by FindUnitDistanceEmbedding  (random embedding waiting until UD is found)

FindUnitDistanceEmbedding[GraphData[{"FibonacciCube",15}],"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

{{"FibonacciCube",15},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"FibonacciCube",15}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Select[IndexGraph/@gs,!DegenerateGraphEmbeddingQ[#]&&GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]//Timing

Matchstick

GraphData[{"FibonacciCube",15},"Matchstick"]

GraphData[{"FibonacciCube",15},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"FibonacciCube",15},"Edges"]]

3D construction

3D All

GraphData[{"FibonacciCube",15},"Graph",{"3D","All"}]

3D UnitDistance construction Random

GraphData[{"FibonacciCube",15},"Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData[{"FibonacciCube",15},"VertexList"],
GraphData[{"FibonacciCube",15},"EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

GraphData[{"FibonacciCube",15},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"FibonacciCube",15},"Polyhedral"]

GraphData[{"FibonacciCube",15},"Graph",{"3D","Polyhedron"}]

Properties

Acyclic

seq=Table[GraphData[{"FibonacciCube",n},"Acyclic"],{n,15}]

AdjacencyMatrixCount

seq=Table[GraphData[{"FibonacciCube",n},"AdjacencyMatrixCount"],{n,10}]

Table[((Fibonacci[n+2]!)/2),{n,10}]

Arboricity

seq=Table[GraphData[{"FibonacciCube",n},"Arboricity"],{n,15}]

ArcTransitive

seq=Table[GraphData[{"FibonacciCube",n},"ArcTransitive"],{n,15}]

ArcTransitivity

seq=Table[GraphData[{"FibonacciCube",n},"ArcTransitivity"],{n,15}]

AutomorphismCount

seq=Table[GraphData[{"FibonacciCube",n},"AutomorphismCount"],{n,15}]

BalabanIndex

seq=Table[GraphData[{"FibonacciCube",n},"BalabanIndex"],{n,5}]

Bandwidth

Possibly n-1 for n > 1

seq=Table[GraphData[{"FibonacciCube",n},"Bandwidth"],{n,15}]

BridgeCount

seq=Table[GraphData[{"FibonacciCube",n},"BridgeCount"],{n,15}]

BurningNumber

seq=Table[GraphData[{"FibonacciCube",n},"BurningNumber"],{n,15}]

CharacteristicPolynomial

(poly=Factor[Table[GraphData[{"FibonacciCube",n},"CharacteristicPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Chordal

seq=Table[GraphData[{"FibonacciCube",n},"Chordal"],{n,15}]

ChordCount

seq=Table[GraphData[{"FibonacciCube",n},"ChordCount"],{n,15}]

Chordless

seq=Table[GraphData[{"FibonacciCube",n},"Chordless"],{n,15}]

ChordlessCycleCount

seq=Table[GraphData[{"FibonacciCube",n},"ChordlessCycleCount"],{n,15}]

FindSequenceFunction[DeleteMissing@seq,n]

Chords

seq=Table[GraphData[{"FibonacciCube",n},"Chords"],{n,15}]

ChromaticallyUnique

seq=Table[GraphData[{"FibonacciCube",n},"ChromaticallyUnique"],{n,15}]

GraphData[{"ChromaticallyUnique","FibonacciCube"}]

ChromaticInvariant

A295927

seq=Table[GraphData[{"FibonacciCube",n},"ChromaticInvariant"],{n,15}]

FindSequenceFunction[Drop[seq,2],n]

ChromaticNumber

seq=Table[GraphData[{"FibonacciCube",n},"ChromaticNumber"],{n,15}]

ChromaticPolynomial

(poly=Factor[DeleteMissing@Table[GraphData[{"FibonacciCube",n},"ChromaticPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Circumference

A104221

seq=Table[GraphData[{"FibonacciCube",n},"Circumference"],{n,15}]

Do[Print[{n,Circumference[GraphData[{"FibonacciCube",n}]]//Timing}],{n,15}]

FindSequenceFunction[DeleteMissing@Drop[seq,2],n-2]

Table[Piecewise[{{Missing["NotApplicable"],n==1||n==2}},Fibonacci[n+2]-Mod[Fibonacci[n+2],2]],{n,15}]

seq=Table[Fibonacci[n]-Mod[Fibonacci[n],2],{n,0,30}]

FindLinearRecurrence[seq]

LinearRecurrence[{1,1,1,-1,-1},{0,0,0,2,2},20]

gf=FindGeneratingFunction[seq,x]

CoefficientList[Series[((2 (x^3))/(1-x-(x^2)-(x^3)+(x^4)+(x^5))),{x,0,20}],x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>0&&n∈Integers]

Table[-(((((1/2) (1-(Sqrt[5]))))^n)/(Sqrt[5]))+(((((1/2) (1+(Sqrt[5]))))^n)/(Sqrt[5])),{n,10}]//FullSimplify

Table[(2/3) (Cos[((2 n π)/3)]-1)+Fibonacci[n],{n,0,20}]

2Table[Floor[Fibonacci[n]/2],{n,0,20}]

2Floor[Fibonacci[Range[0,20]]/2]

Classes

Intersection@@(GraphData[#,"Classes"]&/@GraphData["FibonacciCube"])

CliqueCount

A291916

seq=Table[GraphData[{"FibonacciCube",n},"CliqueCount"],{n,15}]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{3,-1,-3,1,1},{4,6,11,19,34},40]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers&&n>0]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((-4+6 x+3 (x^2)-4 (x^3)-2 (x^4))/((-1+x) (((-1+x+(x^2)))^2))),{x,0,20}],x]

Refine[SeriesCoefficient[gf,{x,0,n}],n>0]//FullSimplify

Table[(2^(-1-n))((25-19 (Sqrt[5])) (((1-(Sqrt[5])))^n)+(((1+(Sqrt[5])))^n) (25+19 (Sqrt[5])))/5,{n,10}]//FullSimplify

Series[(5+7*x)/(1-x-x^2),{x,0,10}]

SeriesCoefficient[(5+7*x)/(1-x-x^2),{x,0,n}]//FullSimplify

Table[((((1-(Sqrt[5])))^(1+n))+(((1+(Sqrt[5])))^(1+n))),{n,10}]//FullSimplify

Table[(2^(n+1))LucasL[n+1],{n,10}]

Table[(1/25) (2^(-1-n)) (25 (2^(1+n))+(25-19 (Sqrt[5])) (((1-(Sqrt[5])))^n)+(((1+(Sqrt[5])))^n) (25+19 (Sqrt[5])))+(1/5) (2^(-1-n)) (2^(n+1))LucasL[n+1] n,{n,10}]//FullSimplify

Table[((((25-19 (Sqrt[5])) (((1-(Sqrt[5])))^n)+(((1+(Sqrt[5])))^n) (25+19 (Sqrt[5]))))/(25 (2^(n+1))))+n LucasL[n+1]/5+1,{n,20}]//Expand

CliqueCoveringNumber

seq=Table[GraphData[{"FibonacciCube",n},"CliqueCoveringNumber"],{n,15}]

CliqueNumber

seq=Table[GraphData[{"FibonacciCube",n},"CliqueNumber"],{n,15}]

CliquePolynomial

(poly=Factor[Table[GraphData[{"FibonacciCube",n},"CliquePolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

CochromaticGraphNames

Table[GraphData[{"FibonacciCube",n},"CochromaticGraphNames"],{n,15}]//Column

Select[GraphData["FibonacciCube"],GraphData[#,"ChromaticallyUnique"]=!=False&]

ComplementOddChordlessCycleCount

seq=Table[GraphData[{"FibonacciCube",n},"ComplementOddChordlessCycleCount"],{n,15}]

ConnectedComponentCount

seq=Table[GraphData[{"FibonacciCube",n},"ConnectedComponentCount"],{n,15}]

ConnectedDominatingSetCount

seq=Table[GraphData[{"FibonacciCube",n},"ConnectedDominatingSetCount"],{n,15}]

FindSequenceFunction[seq,n]

ConnectedDominationNumber

seq=Table[GraphData[{"FibonacciCube",n},"ConnectedDominationNumber"],{n,15}]

FindSequenceFunction[seq,n]

ConnectedDominationPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"ConnectedDominationPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

ConnectedInducedSubgraphCount

A292066

seq=Table[GraphData[{"FibonacciCube",n},"ConnectedInducedSubgraphCount"],{n,15}]

FindSequenceFunction[DeleteMissing[seq],n]

FindLinearRecurrence[DeleteMissing@seq]

ConnectedInducedSubgraphPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"ConnectedInducedSubgraphPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,15}]

FullSimplify[poly2-poly]

CrossingNumber

seq=Table[GraphData[{"FibonacciCube",n},"CrossingNumber"],{n,15}]

CycleCount

A291917

seq=Table[GraphData[{"FibonacciCube",n},"CycleCount"],{n,15}]

CyclePolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"CyclePolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

CoefficientList[poly,x^2]//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Cyclic

Table[GraphData[{"FibonacciCube",n},"Cyclic"],{n,15}]

CyclomaticNumber

A006478

seq=Table[GraphData[{"FibonacciCube",n},"CyclomaticNumber"],{n,15}]

seq=Table[(2(n+1)Fibonacci[n]+n Fibonacci[n+1])/5-Fibonacci[n+2]+1,{n,15}]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{3,-1,-3,1,1},{0,0,1,3,8},20]

FullSimplify[(2(n+1)Fibonacci[n]+n Fibonacci[n+1])/5-Fibonacci[n+2]+1]

Table[1+(2 (n+1) Fibonacci[n]+n Fibonacci[n+1])/5- Fibonacci[n+2],{n,20}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers&&n>0]

DetourIndex

A291919

seq=Table[GraphData[{"FibonacciCube",n},"DetourIndex"],{n,15}]

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

DetourMatrix

MatrixForm/@Table[GraphData[{"FibonacciCube",n},"DetourMatrix"],{n,5}]

MatrixForm/@Table[SparseArray[{i_,j_}:>Abs[i-j],n],{n,15}]

DetourPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"DetourPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Diameter

seq=Table[GraphData[{"FibonacciCube",n},"Diameter"],{n,15}]

DistanceMatrix

MatrixForm/@Table[GraphData[{"FibonacciCube",n},"DistanceMatrix"],{n,5}]

MatrixForm/@Table[SparseArray[{i_,j_}:>Abs[i-j],n],{n,15}]

DistancePolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"DistancePolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

DistinguishingNumber

seq=Table[GraphData[{"FibonacciCube",n},"DistinguishingNumber"],{n,15}]

DomaticNumber

Posisbly 3 for n>= 5

seq=Table[GraphData[{"FibonacciCube",n},"DomaticNumber"],{n,15}]

DominatingSetCount

A291920

seq=Table[GraphData[{"FibonacciCube",n},"DominatingSetCount"],{n,15}]

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

DominationNumber

A291295

seq=Table[GraphData[{"FibonacciCube",n},"DominationNumber"],{n,15}]

Ilic, A. and Milosevic, M.  "The Parameters of Fibonacci and Lucas Cubes."  Ars Math. Contemp. 12, 25–29, 2017.

Jernej Azarija, S. Klavzar, Y. Rho, S. Sim, On domination-type invariants of Fibonacci cubes and hypercubes, Preprint 2016; See Table 2.
Jernej Azarija, S. Klavzar, Y. Rho, S. Sim, On domination-type invariants of Fibonacci cubes and hypercubes, Ars Mathematica Contemporanea, 14 (2018) 387-395. See Table 2.

DominationPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"DominationPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

CoefficientList[poly,x]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

EdgeChromaticNumber

seq=Table[GraphData[{"FibonacciCube",n},"EdgeChromaticNumber"],{n,15}]

EdgeConnectivity

Table[GraphData[{"FibonacciCube",n},"EdgeConnectivity"],{n,15}]

EdgeCount

seq=Table[GraphData[{"FibonacciCube",n},"EdgeCount"],{n,15}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers&&n>0]

Sum[Binomial[n-i,i]i,{i,0,n}]

-(1/25) ((((1/2) (1+(Sqrt[5]))))^n) ((Sqrt[5])-5 n)-(1+n) Binomial[-1,1+n] Hypergeometric2F1[((2+n)/2),((3+n)/2),1+n,-4]/.n->n+1

FullSimplify[%24,n∈Integers&&n>0]

Table[-(1/25) ((((2/(1+(Sqrt[5])))))^(-1-n)) (-5+(Sqrt[5])-5 n)+(((-1))^(1+n)) (2+n) Hypergeometric2F1[((3+n)/2),((4+n)/2),2+n,-4],{n,10}]//FullSimplify

Table[-(1/25) (GoldenRatio^(n+1))(-5+(Sqrt[5])-5 n)-(((-1))^n) (n+2) Hypergeometric2F1[((3+n)/2),((4+n)/2),2+n,-4],{n,10}]//FullSimplify

gf=x FindGeneratingFunction[seq,x]

Refine[SeriesCoefficient[gf,{x,0,n}],n>0]

Flatten[Table[ListConvolve[Fibonacci[Range[n]],Fibonacci[Range[n]]],{n,20}]]

Table[(2(n+1)Fibonacci[n]+n Fibonacci[n+1])/5,{n,20}]

FullSimplify[(2(n+1)Fibonacci[n]+n Fibonacci[n+1])/5,n∈Integers&&n>0]

EdgeCoverCount

seq=Table[GraphData[{"FibonacciCube",n},"EdgeCoverCount"],{n,15}]

EdgeCoverNumber

seq=Table[GraphData[{"FibonacciCube",n},"EdgeCoverNumber"],{n,15}]

Table[Min[Length/@FindAllEdgeCovers[FibonacciCubeGraph[n]]],{n,5}]//Timing

EdgeCoverPolynomial

(poly=Factor[Table[GraphData[{"FibonacciCube",n},"EdgeCoverPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

EulerianCycleCount

seq=Table[GraphData[{"FibonacciCube",n},"EulerianCycleCount"],{n,15}]

FaceCount

seq=Table[GraphData[{"FibonacciCube",n},"FaceCount"],{n,15}]

FlowPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"FlowPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

FractionalChromaticNumber

seq=Table[GraphData[{"FibonacciCube",n},"FractionalChromaticNumber"],{n,15}]

FractionalEdgeChromaticNumber

seq=Table[GraphData[{"FibonacciCube",n},"FractionalEdgeChromaticNumber"],{n,15}]

Girth

seq=Table[GraphData[{"FibonacciCube",n},"Girth"],{n,15}]

Gonality

seq=Table[GraphData[{"FibonacciCube",n},"Gonality"],{n,15}]

HamiltonConnected

seq=Table[GraphData[{"FibonacciCube",n},"HamiltonConnected"],{n,15}]

HamiltonDecompositionCount

seq=Table[GraphData[{"FibonacciCube",n},"HamiltonDecompositionCount"],{n,15}]

Hamiltonian

Table[GraphData[{"FibonacciCube",n},"Hamiltonian"],{n,15}]

HamiltonianCycleCount

seq=Table[GraphData[{"FibonacciCube",n},"HamiltonianCycleCount"],{n,15}]

HamiltonianNumber

seq=Table[GraphData[{"FibonacciCube",n},"HamiltonianNumber"],{n,15}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>0]

HamiltonianPathCount

A289998

seq=Table[GraphData[{"FibonacciCube",n},"HamiltonianPathCount"],{n,15}]

HamiltonianWalkCount

seq=Table[GraphData[{"FibonacciCube",n},"HamiltonianWalkCount"],{n,15}]

HararyIndex

seq=Table[GraphData[{"FibonacciCube",n},"HararyIndex"],{n,15}]

(seq=Monitor[Table[HararyIndex[FibonacciCubeGraph[n]],{n,16}],n])//Timing

FindSequenceFunction[DeleteMissing@seq,n]//Timing

FindGeneratingFunction[seq,x]

HexagonCount

A291915

seq=Table[GraphData[{"FibonacciCube",n},"HexagonCount"],{n,15}]

(seq=Monitor[Table[CycleCount[FibonacciCubeGraph[n],6],{n,16}],n])//Timing

(seq=Monitor[Table[CycleCount[FibonacciCubeGraph[n],6],{n,17}],n])//Timing

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{4,-2,-8,5,8,-2,-4,-1},{0,0,0,2,22,82,268,742},40]

RSolve[{a[n]==4a[n-1]-2a[n-2]-8a[n-3]+5a[n-4]+8a[n-5]-2a[n-6]-4a[n-7]-a[n-7],a[1]==0,a[2]==0,a[3]==0,a[4]==2,a[5]==22,a[6]==82,a[7]==268},a[n],n]

"a(n) = "<>StringReplace[StringJoin@@Table[If[coef[[k]]==0,"",Switch[
coef[[k]],
-1," - ",
1," + ",
_,ToString[coef[[k]]]<>"*"]<>"a(n-"<>ToString[k]<>") + "],{k,Length[coef]}]," + -"->" - " ]

Table[(x^n) FindGeneratingFunction[Drop[seq,n-1],x],{n,0,3}]//Column

...wrong...

IdiosyncraticPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"IdiosyncraticPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x,y]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

IndependenceNumber

A173173

seq=Table[GraphData[{"FibonacciCube",n},"IndependenceNumber"],{n,15}]

Table[Ceiling[Fibonacci[n+2]/2],{n,15}]

Table[Ceiling[Fibonacci[n]/2],{n,0,20}]

Ceiling[Fibonacci[Range[0,20]]/2]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{1,1,1,-1,-1},{1,2,3,4,7},20]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers&&n>0]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((1+x-2 (x^3)-(x^4))/(1-x-(x^2)-(x^3)+(x^4)+(x^5))),{x,0,20}],x]

IndependencePolynomial

(poly=Factor[DeleteMissing@Table[GraphData[{"FibonacciCube",n},"IndependencePolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

CoefficientList[Take[poly],x]//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

IndependenceRatio

seq=Table[GraphData[{"FibonacciCube",n},"IndependenceRatio"],{n,15}]

FindSequenceFunction[seq,n]

Table[((Ceiling[Fibonacci[n+2]/2])/(Fibonacci[n+2])),{n,0,20}]

IndependentEdgeSetCount

A291935

seq=Table[GraphData[{"FibonacciCube",n},"IndependentEdgeSetCount"],{n,15}]

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

IndependentVertexSetCount

A291936

seq=Table[GraphData[{"FibonacciCube",n},"IndependentVertexSetCount"],{n,15}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

IntersectionNumber

seq=Table[GraphData[{"FibonacciCube",n},"IntersectionNumber"],{n,15}]

IrredundancePolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"IrredundancePolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

IrredundantSetCount

A291963

seq=Table[GraphData[{"FibonacciCube",n},"IrredundantSetCount"],{n,15}]

IrredundancePolynomial

poly=DeleteMissing@Table[GraphData[{"FibonacciCube",n},"IrredundancePolynomial"],{n,15}]/.f_Function:>f[x]

CoefficientList[poly,x]

FindLinearRecurrence[poly]

KirchhoffIndex

seq=Table[GraphData[{"FibonacciCube",n},"KirchhoffIndex"],{n,15}]

FindSequenceFunction[seq,n]

KirchhoffSumIndex

seq=Table[GraphData[{"FibonacciCube",n},"KirchhoffSumIndex"],{n,15}]

LaplacianMatrix

MatrixForm/@Table[GraphData[{"FibonacciCube",n},"LaplacianMatrix"],{n,5}]

LaplacianPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"LaplacianPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

LeafCount

seq=Table[GraphData[{"FibonacciCube",n},"LeafCount"],{n,15}]

Likelihood

seq=Table[GraphData[{"FibonacciCube",n},"Likelihood"],{n,15}]

LongestCycleCount

seq=Table[GraphData[{"FibonacciCube",n},"LongestCycleCount"],{n,15}]

LovaszNumber

seq=Table[GraphData[{"FibonacciCube",n},"LovaszNumber"],{n,15}]

LowerIndependenceNumber

A291297

seq=Table[GraphData[{"FibonacciCube",n},"LowerIndependenceNumber"],{n,15}]

Ilic, A. and Milosevic, M.  "The Parameters of Fibonacci and Lucas Cubes."  Ars Math. Contemp. 12, 25–29, 2017.

Jernej Azarija, S. Klavzar, Y. Rho, S. Sim, On domination-type invariants of Fibonacci cubes and hypercubes, Preprint 2016; See Table 2.
Jernej Azarija, S. Klavzar, Y. Rho, S. Sim, On domination-type invariants of Fibonacci cubes and hypercubes, Ars Mathematica Contemporanea, 14 (2018)

MatchingGeneratingPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"MatchingGeneratingPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

CoefficientList[poly,x]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

MatchingNumber

A004695

seq=Table[GraphData[{"FibonacciCube",n},"MatchingNumber"],{n,15}]

Table[MatchingNumber[FibonacciCubeGraph[n]],{n,10}]//Timing

FullSimplify[FindSequenceFunction[seq,n],n∈Integers&&n>0]

Table[Fibonacci[n]/2-(1-Cos[2Pi n/3])/3,{n,0,20}]

seq=Table[Floor[Fibonacci[n+2]/2],{n,20}]

Floor[Fibonacci[Range[0,20]]/2]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{1,1,1,-1,-1},{1,1,2,4,6},20]

MatchingPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"MatchingPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

MaximalCliqueCount

Same as EdgeCount and MaximumCliqueCount

A001629

seq=Table[GraphData[{"FibonacciCube",n},"MaximalCliqueCount"],{n,15}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]

SeriesCoefficient[FindGeneratingFunction[seq,x],{x,0,n}]

MaximalIndependentEdgeSetCount

A291827

seq=Table[GraphData[{"FibonacciCube",n},"MaximalIndependentEdgeSetCount"],{n,15}]

FindLinearRecurrence[seq]

gf=x FindGeneratingFunction[seq,x]

MaximalIndependentVertexSetCount

A291742

seq=Table[GraphData[{"FibonacciCube",n},"MaximalIndependentVertexSetCount"],{n,15}]

Table[Length@MaximalSets[FindAllIndependentVertexSets[FibonacciCubeGraph[n]]],{n,6}]//Timing

Table[Length@MaximalSets[FindAllIndependentVertexSets[FibonacciCubeGraph[n]]],{n,7}]//Timing

MaximalIrredundantSetCount

A292016

seq=Table[GraphData[{"FibonacciCube",n},"MaximalIrredundantSetCount"],{n,15}]

MaximalIrredundantSetSignature

seq=Table[GraphData[{"FibonacciCube",n},"MaximalIrredundantSetSignature"],{n,15}]

MaximumCliqueCount

Same as EdgeCount and MaximalCliqueCount

A001629

seq=Table[GraphData[{"FibonacciCube",n},"MaximumCliqueCount"],{n,15}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]

SeriesCoefficient[FindGeneratingFunction[seq,x],{x,0,n}]

MaximumIndependentEdgeSetCount

A292017

seq=Table[GraphData[{"FibonacciCube",n},"MaximumIndependentEdgeSetCount"],{n,15}]

MaximumIndependentVertexSetCount

seq=Table[GraphData[{"FibonacciCube",n},"MaximumIndependentVertexSetCount"],{n,15}]

MaximumIrredundantSetCount

seq=Table[GraphData[{"FibonacciCube",n},"MaximumIrredundantSetCount"],{n,15}]

MaximumLeafNumber

seq=Table[GraphData[{"FibonacciCube",n},"MaximumLeafNumber"],{n,15}]

MaximumVertexDegree

seq=Table[GraphData[{"FibonacciCube",n},"MaximumVertexDegree"],{n,15}]

MeanDistance

seq=Table[GraphData[{"FibonacciCube",n},"MeanDistance"],{n,15}]

FindSequenceFunction[seq,n]

MinimalDominatingSetCount

A291573

seq=Table[GraphData[{"FibonacciCube",n},"MinimalDominatingSetCount"],{n,15}]

MinimalDominatingSetSignature

seq=Table[GraphData[{"FibonacciCube",n},"MinimalDominatingSetSignature"],{n,15}]

MinimalEdgeCoverCount

seq=Table[GraphData[{"FibonacciCube",n},"MinimalEdgeCoverCount"],{n,15}]

MinimalEdgeCoverSignature

seq=Table[GraphData[{"FibonacciCube",n},"MinimalEdgeCoverSignature"],{n,15}]

MinimumCliqueCoveringCount

seq=Table[GraphData[{"FibonacciCube",n},"MinimumCliqueCoveringCount"],{n,15}]

MinimumConnectedDominatingSetCount

seq=Table[GraphData[{"FibonacciCube",n},"MinimumConnectedDominatingSetCount"],{n,15}]

FindSequenceFunction[seq,n]

MinimumDistinguishingLabelingCount

seq=Table[GraphData[{"FibonacciCube",n},"MinimumDistinguishingLabelingCount"],{n,15}]

MinimumDominatingSetCount

seq=Table[GraphData[{"FibonacciCube",n},"MinimumDominatingSetCount"],{n,15}]

MinimumEdgeCoverCount

seq=Table[GraphData[{"FibonacciCube",n},"MinimumEdgeCoverCount"],{n,15}]

MinimumVertexDegree

seq=Table[GraphData[{"FibonacciCube",n},"MinimumVertexDegree"],{n,15}]

MolecularTopologicalIndex

seq=Table[GraphData[{"FibonacciCube",n},"MolecularTopologicalIndex"],{n,15}]

FindSequenceFunction[DeleteMissing@seq,n]

FindLinearRecurrence[DeleteMissing@seq,n]

Nonhamiltonian

Table[GraphData[{"FibonacciCube",n},"Nonhamiltonian"],{n,15}]

NormalizedLaplacianMatrix

MatrixForm/@Table[GraphData[{"FibonacciCube",n},"NormalizedLaplacianMatrix"],{n,5}]

OddChordlessCycleCount

seq=Table[GraphData[{"FibonacciCube",n},"OddChordlessCycleCount"],{n,15}]

PathCount

A291964

seq=Table[GraphData[{"FibonacciCube",n},"PathCount"],{n,15}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>0]

PathPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"PathPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

PentagonCount

seq=Table[GraphData[{"FibonacciCube",n},"PentagonCount"],{n,15}]

Perfect

Table[GraphData[{"FibonacciCube",n},"Perfect"],{n,15}]

Perihamiltonian

Let Gamma_n be the Fibonacci cube, bipartitioned by the parity of the Hamming weight.  Its order is F_(n+2), which is odd exactly when n is not congruent to 1 modulo 3.  For n >= 5 of odd order, Theorem 5.2.2 in Studies on the Network states that Gamma_n-v is Hamiltonian exactly when v belongs to the larger part.  Consequently the vertices with non-Hamiltonian deletion form the smaller part, an independent set, so every edge has an endpoint whose deletion is Hamiltonian.  Hence Gamma_n is perihamiltonian for n >= 5 exactly when Mod[n,3] != 1.

There is a necessary low-dimensional exception to the theorem as printed: Gamma_3 has odd order, but deletion of 010 gives a 4-cycle while deletion of either of the other two vertices in the larger part gives a tree.  Directly, the values for n=1,2,3,4 are True, False, False, False, where n=1 is True by the K_2 convention used by PerihamiltonianGraphQ.  The complete classification is therefore n=1 or n>=5 with Mod[n,3] != 1.

Source: Studies on the Network, Section 5.2, Theorem 5.2.2, https://events.cusat.ac.in/xmlui/bitstream/handle/purl/5367/T-2386.pdf?sequence=1

ProjectivePlaneCrossingNumber

seq=Table[GraphData[{"FibonacciCube",n},"ProjectivePlaneCrossingNumber"],{n,15}]

Radius

seq=Table[GraphData[{"FibonacciCube",n},"Radius"],{n,15}]

RankPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"RankPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x,y]])//Column

RectilinearCrossingNumber

seq=Table[GraphData[{"FibonacciCube",n},"RectilinearCrossingNumber"],{n,15}]

ReliabilityPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"ReliabilityPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

SigmaPolynomial

(poly=Factor[Table[GraphData[{"FibonacciCube",n},"SigmaPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Skewness

seq=Table[GraphData[{"FibonacciCube",n},"Skewness"],{n,15}]

FindSequenceFunction[Take[seq,7],n]

FindGeneratingFunction[Take[seq,7],x]

SpanningTreeCount

seq=Table[GraphData[{"FibonacciCube",n},"SpanningTreeCount"],{n,15}]

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

SquareCount

A001628(n+3)

seq=Table[GraphData[{"FibonacciCube",n},"SquareCount"],{n,15}]

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{3,0,-5,0,3,1},{1,3,9,22,51,111},20]

Table[Derivative[2][Fibonacci[n+2,#]&][1]/2,{n,20}]

Derivative[2][Fibonacci[Range[20]+2,#]&][1]/2

Derivative[2][Fibonacci[n+2,#]&][1]/2//FullSimplify

Table[-(I^(n+1))Derivative[2][ChebyshevU[n+1,-#/2]&][I]/2,{n,20}]

-(I^(n+1))Derivative[2][ChebyshevU[n+1,-#/2]&][I]/2//FullSimplify

FindSequenceFunction[seq,n]//FullSimplify

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[-(1/(((-1+x+(x^2)))^3)),{x,0,20}],x]

StabilityIndex

seq=Table[GraphData[{"FibonacciCube",n},"StabilityIndex"],{n,15}]

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

TopologicalIndex

seq=Table[GraphData[{"FibonacciCube",n},"TopologicalIndex"],{n,15}]

FindSequenceFunction[DeleteMissing@seq,n]

FindGeneratingFunction[seq,x]

ToroidalCrossingNumber

seq=Table[GraphData[{"FibonacciCube",n},"ToroidalCrossingNumber"],{n,15}]

Traceable

Should all be True

Table[GraphData[{"FibonacciCube",n},"Traceable"],{n,15}]

Triameter

seq=Table[GraphData[{"FibonacciCube",n},"Triameter"],{n,15}]

FindSequenceFunction[Rest@seq,n-1]

TriangleCount

seq=Table[GraphData[{"FibonacciCube",n},"TriangleCount"],{n,15}]

TuttePolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"TuttePolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x,y]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Untraceable

Table[GraphData[{"FibonacciCube",n},"Untraceable"],{n,15}]

VertexConnectivity

Table[GraphData[{"FibonacciCube",n},"VertexConnectivity"],{n,15}]

VertexCount

seq=Table[GraphData[{"FibonacciCube",n},"VertexCount"],{n,15}]

FindSequenceFunction[seq,n]//FullSimplify

Table[Fibonacci[n+2],{n,15}]

VertexCoverNumber

A004695

vertex cover number == vertex count - independence number

seq=Table[GraphData[{"FibonacciCube",n},"VertexCoverNumber"],{n,15}]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]

Table[Fibonacci[n+2]-Ceiling[Fibonacci[n+2]/2],{n,15}]

Table[Floor[Fibonacci[n+2]/2],{n,15}]

VertexCoverPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"FibonacciCube",n},"VertexCoverPolynomial"],{n,k0=1,kmax=15}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

VertexDegrees

seq=Table[GraphData[{"FibonacciCube",n},"VertexDegrees"],{n,5}]

VertexTransitive

Table[GraphData[{"FibonacciCube",n},"VertexTransitive"],{n,15}]

WienerIndex

A238419

seq=Table[GraphData[{"FibonacciCube",n},"WienerIndex"],{n,15}]

FindLinearRecurrence[seq]

LinearRecurrence[{4,0,-10,0,4,-1},{1,4,16,54,176,548},20]

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[(x/(((1-2 x-2 (x^2)+(x^3)))^2)),{x,0,20}],x]

Table[(n LucasL[2(n+2)]+2Fibonacci[2n+1]-(n+2)(-1)^n)/25,{n,0,20}]

WienerSumIndex

seq=Table[GraphData[{"FibonacciCube",n},"WienerSumIndex"],{n,15}]

FindSequenceFunction[seq,n]

Algorithms

Bitstrings

https://en.wikipedia.org/wiki/Fibonacci_cube#Definition

FibonacciCubeGraph1[n_]:=Module[{v=Select[Tuples[{0,1},n],FreeQ[{___,1,1,___}]],e},
e=Select[Subsets[Range@Length@v,{2}],Total[Boole[Unequal@@@Transpose[v[[#]]]]]==1&];
Graph[Range@Length@v,UndirectedEdge@@@e]
]

RecognizeGraph/@Table[FibonacciCubeGraph1[n],{n,6}]

HammingDistance

https://en.wikipedia.org/wiki/Fibonacci_cube

?HammingDistance

FibonacciCubeGraph[n_Integer?Positive,opts___?OptionQ]:=Module[{v=Range[0,Fibonacci[n+2]-1],e,zeck,len},
zeck=ZeckendorfRepresentation/@v;
len=Length[zeck[[-1]]];
zeck=PadLeft[#,len]&/@zeck;
e=Pick[Subsets[v,{2}],HammingDistance@@@Subsets[zeck,{2}],1];
IndexGraph@System`Graph[v,UndirectedEdge@@@e,opts]
]

FibonacciCubeGraph[2]

FibonacciCubeGraph[3]

Length/@ZeckendorfRepresentation/@Range[0,Fibonacci[3+2]-1]

FibonacciCubeGraph[15]//VertexCount

GraphData

GraphDataClassString

GraphDataClassString["FibonacciCube"]

GraphDataString

file=OpenAppend["~/fibonacci_cube.m"]

Table[WriteString[file,GraphDataString[FibonacciCubeGraph[n],
"Name"->ToString[n]<>"-Fibonacci cube graph",
"StandardName"->{"FibonacciCube",n},
"AlternateStandardNames"->{},
"Classes"->{"FibonacciCube"},
"NotationRules"->{"FibonacciCube"->n},
"Information"->"FibonacciCubeGraph",
"Skip"->{"Arboricity",
"ChordlessCycle","Pseudotree",
	(* bug(338672): Aborting FindCycle crashes kernel *)
"Circulant","CliqueCoveringNumber",
"ConnectedDominatingSets","Skewness",
	(* bug(338571): TimeConstrained Subgraph sporadically crashes kernel after multiple evaluations *)
"StronglyPerfect",
	(* bug(): Subsets fails to MemoryConstrain *)
"TuttePolynomial"
	(* bug(169355): TuttePolynomial is uninterruptible *)
},
TimeConstraint->2,
Debug->True
]],{n,4,15}];

Close[file]