Reye Graph

Author

Eric W. Weisstein
December 13, 2023

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

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

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

Definition

Levi graph of:
*16 lines and the same 12 points such that four lines pass through every point and three points lie on every line
* 12 planes and 12 points such that six points lie in every plane and six planes pass through every point

Properties

GraphData["ReyeGraph",{"V","E"}]

Configuration

GraphData["ReyeGraph","Incidence"]

lines=GraphData["ReyeGraph","Configurations"]

Subscript@@Reverse@Flatten@Tally[Length/@lines[[1]]]

RecognizeGraph[LeviGraph[#]]&/@lines

GraphData["ReyeConfigurationGraph","#"]

configg=GraphData["ReyeConfigurationGraph","Graph",{"Configuration","Labeled"}][[1]]

configg=GraphData["ReyeConfigurationGraph","Graph",{"3D","Configuration","Labeled"}][[1]]

lines2=ConfigurationLinesFromGraph[configg]

lines3={{12,9,7},{12,10,8},{12,4,2},{12,3,1},{11,10,3},{10,9,6},{11,8,1},{1,2,6},{3,4,6},{3,5,7},{4,5,8},{1,5,9},{6,7,8},{11,7,2},{11,9,4},{2,5,10}};

LeviGraph[lines3]//RecognizeGraph

points=GraphEmbedding[configg]

ResourceFunction["FindExtraordinaryLines"][points]==lines2

ConfigurationGraph[points,lines2,VertexLabels->Automatic]

RecognizeGraph@%

ConfigurationDiagram[points,lines2,10,Boxed->False]

Original construction

Length[v={{460.156350453974`,86.54809969596795`},{648.0309050864188`,174.67494286437181`},{357.05868689675754`,215.83314737466458`},{543.9051527833656`,260.51457736226257`},{485.743053510471`,344.50596242943584`},{1072.2041494361094`,384.7862484601376`},{561.6021410824867`,415.9985607213812`},{436.6720311249185`,424.88170954776774`},{496.02394096883756`,446.4253669745699`},{376.1534138278588`,454.11870522993195`},{400.6542703438091`,873.8792540637843`},{7.924369434201765`,676.8443131903455`}}/1000]

Length[lines={{12,9,7},{12,10,8},{12,4,2},{12,3,1},{11,10,3},{10,9,6},{11,8,1},{1,2,6},{3,4,6},{3,5,7},{4,5,8},{1,5,9},{6,7,8},{11,7,2},{11,9,4},{2,5,10}}]

edges=Flatten[Partition[#,2,1]&/@lines,1];
g=Graph[Range[Length[v]],UndirectedEdge@@@Sort[Sort/@edges],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@LeviGraph[lines]

"ReyeGraph"

ConfigurationDiagram[v,lines,.1]

g=ConfigurationGraph[v,lines]

RecognizeGraph@g

Embeddings

<<MathWorld`Graphs`

Names

GraphData["ReyeGraph","StandardName"]

GraphData["ReyeGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["ReyeGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Perspective

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

Bilateral

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

Circular

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

Planar

GraphData["ReyeGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

(cn=CrossingNumber[GraphData["ReyeGraph"],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["ReyeGraph"],TimeConstraint->3600])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["ReyeGraph","Circulant"]

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

Complement graph

GraphData["ReyeGraph","ComplementGraph","Name"]

Line graph

GraphData["ReyeGraph","Line"]

LineGraphQ[GraphData["ReyeGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["ReyeGraph"]]

Halin

GraphData["ReyeGraph","Halin"]

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

Rigid

GraphData["ReyeGraph","Rigid"]

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

Flexible

GraphData["ReyeGraph","Flexible"]

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

LCF

GraphData["ReyeGraph","LCF"]

GraphData["ReyeGraph","LCFSignature"]

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

UnitDistance

GraphData["ReyeGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData["ReyeGraph","Matchstick"]

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

MinimalCrossing

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

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

Default embedding

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

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData["ReyeGraph"],TimeConstraint->10]//AbsoluteTiming

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

GraphPlot[MinimalCrossingGraph[GraphData["ReyeGraph"],"CrossingNumber"->20]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData["ReyeGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["ReyeGraph","Polyhedral"]

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