Royle Graphs

Author

Eric W. Weisstein
January 28, 2023

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

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

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

Figure

royle=GraphData["Royle*"]

GraphicsRow[GraphData/@royle//StyleGraphs]

(polys=GetGraphData[#,"SigmaPolynomial"][x]&/@royle)//ColumnForm//TraditionalForm

List@@@Map[Last,NRoots[#,x]&/@polys,{2}]//Column

Embeddings

"RoyleGraph1"

GraphData["RoyleGraph1","StandardName"]

Primary

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

Construction from Read and Wilson

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["RoyleGraph1","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData["RoyleGraph1"],All][[All,All,1]]]

Length[bilat=Union@DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["RoyleGraph1"],#]&/@hc]]//Timing

bilat

gs=bilat

Length[quad=Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&]]

Planar

GraphData["RoyleGraph1","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

GraphPlot@RotateGraph[,Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["RoyleGraph1","Circulant"]

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

Halin

GraphData["RoyleGraph1","Halin"]

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

Rigid

GraphData["RoyleGraph1","Rigid"]

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

Flexible

GraphData["RoyleGraph1","Flexible"]

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

LCF

GraphData["RoyleGraph1","LCF"]

GraphData["RoyleGraph1","HamiltonianCycleCount"]

GraphData["RoyleGraph1","LCFSignature"]

GraphData["RoyleGraph1","LCFNotations"]

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

UnitDistance

GraphData["RoyleGraph1","UnitDistance"]

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

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

UnitDistance by refinement

UnitDistanceGraphEmbeddingQ[%]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData["RoyleGraph1","Matchstick"]

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

3D default

Graph3D[GraphData["RoyleGraph1","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["RoyleGraph1","Polyhedral"]

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

"RoyleGraph2"

GraphData["RoyleGraph2","StandardName"]

Primary

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

Construction from Read and Wilson

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["RoyleGraph2","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData["RoyleGraph2"],All][[All,All,1]]]

Length[bilat=Union@DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["RoyleGraph2"],#]&/@hc]]//Timing

Planar

GraphData["RoyleGraph2","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["RoyleGraph2","Circulant"]

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

Halin

GraphData["RoyleGraph2","Halin"]

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

Rigid

GraphData["RoyleGraph2","Rigid"]

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

Flexible

GraphData["RoyleGraph2","Flexible"]

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

LCF

GraphData["RoyleGraph2","LCF"]

GraphData["RoyleGraph2","HamiltonianCycleCount"]

GraphData["RoyleGraph2","LCFSignature"]

GraphData["RoyleGraph2","LCFNotations"]

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

UnitDistance

GraphData["RoyleGraph2","UnitDistance"]

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

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

UnitDistance by refinement

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

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

GraphPlot@

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData["RoyleGraph2","Matchstick"]

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

3D default

Graph3D[GraphData["RoyleGraph2","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["RoyleGraph2","Polyhedral"]

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

Search

Monitor[Do[Print[{n,Select[GetGraphData[n],Length[Reduce[GetGraphData[g=#,"SigmaPolynomial"][x]==0&&Im[x]≠0,x]]>0&]//Timing}],{n,7}],g]

Length[c9=ReadList["/Volumes/Users/eww/Mathematica/Paclets/GraphData/_Graphs9/ChromaticPolynomial.m"]]

chromaticNumber[poly_,x_]:=Module[{i=0},While[(poly/.x->i)≤0,i++];i]

i=0;
(l=Flatten[Monitor[Position[c9[[All,2]],_?(Length[Reduce[SigmaPolynomial[#,9,chromaticNumber[#,x],x][x]==0&&Im[x]≠0,x]]>0&),{1},Heads->False],i++]])//Timing

Length[l]

g=Graphs[9];

Print[{#,Reduce[SigmaPolynomial[g[[#]]][x]==0&&Im[x]≠0,x]//Timing}]&/@l;

GraphicsGrid[Partition[GraphPlot/@g[[l]],7]]

GraphData

GraphClassString

GraphClassString[GraphData["Royle*"]]