Brinkmann Graph

Author

Eric W. Weisstein
November 10, 2022

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

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

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

Embeddings

GraphData["BrinkmannGraph","StandardName"]

Primary

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

All

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

Star embedding

RegionIntersection[Line[v[[{3,6}]]],Line[v[[{1,4}]]]]//FullSimplify

Norm[{{(1/2) Csc[(π/7)] (1+Sin[(π/14)]) Tan[(π/14)],(1/2) Csc[(π/7)] Sin[(π/14)]}}]//FullSimplify

Norm@Mean[v[[{8,10}]]]//FullSimplify

v=Join[UnitCirclePoints[7,-Pi/2],CirclePoints[(NumericalApproximation[Root, (RowDefault["0.411", FEExpressionsNumericalApproximationElider]), Root[-1+14 ((#1)^2)-49 ((#1)^4)+7 ((#1)^6)&,5], ]),7],CirclePoints[(NumericalApproximation[Root, (RowDefault["0.256", FEExpressionsNumericalApproximationElider]), Root[-1+28 ((#1)^2)-224 ((#1)^4)+448 ((#1)^6)&,4], ]),7]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,3,5,7,2,4,6,1,8,16,10,4,11,19,13,7,14,15,9,3,10,18,12,6,13,21,8,2,9,17,11,5,12,20,14,1],e[21,17,20,16,19,15,18,21]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Default embedding

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

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

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData["BrinkmannGraph","EdgeList"]]

Degenerate

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

Bilateral

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

Circular

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

Planar

GraphData["BrinkmannGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

CrossingNumber[GraphData["BrinkmannGraph"],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData["BrinkmannGraph"],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData["BrinkmannGraph"],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["BrinkmannGraph","Circulant"]

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

Halin

GraphData["BrinkmannGraph","Halin"]

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

LCF

GraphData["BrinkmannGraph","LCF"]

GraphData["BrinkmannGraph","LCFSignature"]

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

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

LCF compute

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

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

gs=LCFGraph@@@lcf//StyleGraphs

gs=Join[With[{g=BilateralLCFEmbedding[#]},If[MissingQ[g],#,g]]&/@LCFGraph@@@DeleteCases[lcf,{_,1}],DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]]

UnitDistance

GraphData["BrinkmannGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["BrinkmannGraph","Edges"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData["BrinkmannGraph","Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

FindUnitDistanceEmbedding[GraphData["BrinkmannGraph"],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["BrinkmannGraph","Matchstick"]

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

3D default

Graph3D[GraphData["BrinkmannGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["BrinkmannGraph","Polyhedral"]

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

Matrices

GraphicsRow[GraphMatrixPlot[GraphData["BrinkmannGraph"]]]

GraphData

GraphClassString

GraphClassString["BrinkmannGraph"]