Balaban 10-Cage

Author

Eric W. Weisstein
November 10, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Balaban10-Cage.nb.

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

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

Graph

All

GraphicsGrid[Partition[StyleGraphs@Take[GraphData["Balaban10Cage","Graph","All"],All],UpTo[5]],ImageSize->800,Dividers->All]

Embeddings

<<MathWorld`Graphs`

Names

GraphData["Balaban10Cage","StandardName"]

GraphData["Balaban10Cage","StandardNames"]

Primary

GraphData["Balaban10Cage"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["Balaban10Cage","Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["Balaban10Cage","EdgeList"]]

Default embedding

GraphPlot@GraphData["Balaban10Cage","Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData["Balaban10Cage","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["Balaban10Cage","Graph","Degenerate"]

Perspective

GraphData["Balaban10Cage","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["Balaban10Cage","Polyhedron"]

Bilateral

GraphData["Balaban10Cage","Graph","Bilateral"]//StyleGraphs

Circular

GraphData["Balaban10Cage","Graph","Circular"]//StyleGraphs

Planar

GraphData["Balaban10Cage","Planar"]

GraphData["Balaban10Cage","Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData["Balaban10Cage",{"RCN","CN"}]

GraphData["Balaban10Cage","Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData["Balaban10Cage"],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["Balaban10Cage"],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["Balaban10Cage"],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData["Balaban10Cage"],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["Balaban10Cage","Circulant"]

GraphData["Balaban10Cage","Graph","Circulant"]//StyleGraphs

Complement graph

GraphData["Balaban10Cage","ComplementGraph","Name"]

Line graph

GraphData["Balaban10Cage","Line"]

LineGraphQ[GraphData["Balaban10Cage"]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== "Balaban10Cage"&]

RootGraph[GraphData["Balaban10Cage"]]

Halin

GraphData["Balaban10Cage","Halin"]

GraphData["Balaban10Cage","Graph","Halin"]//StyleGraphs

Rigid

GraphData["Balaban10Cage","Rigid"]

GraphData["Balaban10Cage","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["Balaban10Cage","Flexible"]

GraphData["Balaban10Cage","Graph","Flexible"]//StyleGraphs

LCF

GraphData["Balaban10Cage","LCF"]

GraphData["Balaban10Cage","HamiltonianCycleCount"]

GraphData["Balaban10Cage","LCFSignature"]

GraphData["Balaban10Cage","LCFNotations"]

GraphData["Balaban10Cage","Graph","LCF"]//StyleGraphs

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

LCF compute all

Divisors[GraphData["Balaban10Cage","V"]]

Length[FindHamiltonianCycle[GraphData["Balaban10Cage"],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData["Balaban10Cage"],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["Balaban10Cage",".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@%

UnitDistance

GraphData["Balaban10Cage","UnitDistance"]

UnitDistanceGraphQ[GraphData["Balaban10Cage"],Debug->True]//Timing

GraphData["Balaban10Cage","Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["Balaban10Cage","VertexList"],GraphData["Balaban10Cage","EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["Balaban10Cage"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData["Balaban10Cage"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

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

Matchstick

GraphData["Balaban10Cage","Matchstick"]

GraphData["Balaban10Cage","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["Balaban10Cage","Edges"]]

3D All

GraphData["Balaban10Cage","Graph",{"3D","All"}]

3D UnitDistance

GraphData["Balaban10Cage","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["Balaban10Cage","Polyhedral"]

GraphData["Balaban10Cage","Graph",{"3D","Polyhedron"}]

Matrices

GraphDataMatrices["Balaban10Cage"]

Properties

GraphData["Balaban10Cage",{"VertexCount","EdgeCount"}]

GraphData["Balaban10Cage","Classes"]

(#->GraphData["Balaban10Cage",#])&/@GraphData["Properties"]//ColumnForm

Construction

g2=Module[{p,i},p=GraphUnion[CirculantGraph[20,{6}],Cycle[50]];
MakeUndirected[AddEdges[p,Join[Table[{7+5i,32+5i},{i,3,7}],Table[{20+10i,10i+29},{i,4}],Table[{15+10i,10i+24},{i,4}],{{21,20},{1,23},{70,29},{24,65}},Flatten[Table[{2i+j,21+5i+2j},{j,0,1},{i,9}],1]]]/.Graph[l_List,v_List]:>Graph[l,List/@Join[Table[{Cos[#],Sin[#]}&[2.Pi (i+1/2)/20],{i,20}],2 Table[{Cos[#],Sin[#]}&[2.Pi (i+1/2)/50],{i,50}]]]]]

ShowGraph[g2]

GraphData

GraphClassString

GraphClassString["Balaban10Cage"]

Construction

Graph["Balaban10Cage"]

Import["/Volumes/Users/eww/Desktop/bridges-between-geometry-and.pdf",{"Pages",19}]

Pisanski 2

l2=;

Length[l=First/@Cases[l2,_Line,{1,∞}]]

v=First/@Partition[Cases[l2,_Polygon,{4}]/.Polygon[x_]:>Mean[x],2]

Graphics[{Line[newl={#[[1]]-.08(#[[2]]-#[[1]]),#[[2]]}&/@l],{Red,Circle[#,1]}&/@v}]

edges=Union[Sort/@Flatten/@Map[Nearest[Thread[v->Range[Length[v]]],#,1]&,newl,{2}]]

ShowLabeledGraph[g2=Graph[List/@edges,List/@v],VertexStyle->Disk[.02]]

Degrees[g2]

RecognizeGraph[g2]

Pisanski 3

l3=;

Length[l=First/@Cases[l3,_Line,{1,∞}]]

Length[v=First/@Partition[Cases[l3,_Polygon,{4}]/.Polygon[x_]:>Mean[x],2]]

Graphics[{Line[newl={#[[1]]-.06(#[[2]]-#[[1]]),#[[2]]}&/@l],{Red,Circle[#,1]}&/@v}]

edges=Union[Sort/@Flatten/@Map[Nearest[Thread[v->Range[Length[v]]],#,1]&,newl,{2}]]

ShowLabeledGraph[g3=Graph[List/@edges,List/@v],VertexStyle->Disk[.02]]

Degrees[g3]

RecognizeGraph[g3]

e=GraphData["Balaban10Cage","Embeddings"];

Length[e]

Take[Range[5],{2,-1}]

Join[Take[e,2],ToCommonEdges[#,Graph["Balaban10Cage"]]&/@{g2,g3}/500,Take[e,{3,-3}]]//PadVertices