Paley Graph

Author

Eric W. Weisstein
January 16, 2024

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

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

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

Code

QuadraticResidues[n_]:={n,#}&/@Table[Select[Union@Mod[k Range[n]^2,n],(GCD[#,n]==1&&#<n/2&)],{k,n/2}]//Union

Graphic

GraphData["Paley"]

l={"Paley"/.GraphData[#,"NotationRules"],#}&/@GraphData["Paley"]

GraphicsGrid[Partition[Show[GraphData[#2]//StyleGraphs,PlotLabel->TextCell[ToString[#1]<>"\[Hyphen]Paley graph\n"<>If[StringTake[n=GraphData[#2,"Name"],-11]==="Paley graph","",n],PageWidth->120,TextAlignment->Center],BaseStyle->{Black,Italic,FontFamily->"Times"}]&@@@Take[l,8],4],ImageSize->600,Alignment->Center,Dividers->All]

Table

indices=Select[Range[100],Mod[#,4]==1&&PrimePowerQ[#]&]

RecognizeGraph[PaleyGraph[#,Method->"FiniteFields"]]&/@indices

RecognizeGraph[PaleyGraph[#,Method->"JacobsthalMatrix"]]&/@Select[indices,PrimeQ]

TextGrid[{#,r=RecognizeGraph[PaleyGraph[#]],GraphData[r,"AlternateStandardNames"]}&/@indices,Dividers->All]

Special cases

Noncirculant

Complement@@(GraphData/@{"Paley","Circulant"})

Circulant

GraphData[{"Paley","Circulant"}]

Print[{#,CirculantIndices[PaleyGraph[#]]//Timing}]&/@i

Function[n,{n,Select[Union@Mod[Range[n]^2,n],(GCD[#,n]==1&),Floor[n/4]]}]/@Select[Range[169],Mod[#,4]==1&&PrimeQ[#]&]//Column

Embeddings

<<MathWorld`Graphs`

Paley graphs having no LCFNotation of order > 1:

Select[
GraphData[{"LCF","Paley"}],
AllTrue[
GraphData[#,"Graph","LCF"],
Function[lcf,Last[LCFNotation@lcf]==1]
]&
]

Non-circulant Paley graphs having no LCFNotation of order > 1:

Complement[GraphData[{"LCF","Paley"}],GraphData["Circulant"]]

Select[
Complement[GraphData[{"LCF","Paley"}],GraphData["Circulant"]],
AllTrue[
GraphData[#,"Graph","LCF"],
Function[lcf,Last[LCFNotation@lcf]==1]
]&
]

Paley

GraphData["Paley"]

{"Paley", 5} == {"Cycle", 5}

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

{"Paley", 9} == {"GeneralizedQuadrangle", {2, 1}}

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

Toroidal

GraphData[{"Paley",9},"Graph","Torus"]

Jones:

{"Paley", 13}

Names

GraphData[{"Paley",13},"StandardName"]

GraphData[{"Paley",13},"StandardNames"]

Primary

GraphData[{"Paley",13}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",13},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",13},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",13},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",13},"Graph","Degenerate"]//StyleGraphs

Torus

GraphData[{"Paley",13},"Graph","Torus"]//StyleGraphs

Jones:

Bilateral

GraphData[{"Paley",13},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",13},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",13},"Planar"]

GraphData[{"Paley",13},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",13},{"RCN","CN"}]

GraphData[{"Paley",13},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",13}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",13}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",13}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",13},"Circulant"]

GraphData[{"Paley",13},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[13]

GraphData[{"Paley",13},"NotationRules","Circulant"]

Cases[GraphData[{"Paley",13},"StandardNames"],{"Circulant",i_}:>i]

CirculantIndices[GraphData[{"Paley",13}]]//Timing

CirculantGraph1@@@CirculantIndices[GraphData[{"Paley",13}]]

Halin

GraphData[{"Paley",13},"Halin"]

GraphData[{"Paley",13},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",13},"Rigid"]

GraphData[{"Paley",13},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",13},"Flexible"]

GraphData[{"Paley",13},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",13},"LCF"]

GraphData[{"Paley",13},"HamiltonianCycleCount"]

GraphData[{"Paley",13},"LCFSignature"]

GraphData[{"Paley",13},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",13}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",13}],All])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",13},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",13}],Debug->True]//Timing

GraphData[{"Paley",13},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",13},"VertexList"],GraphData[{"Paley",13},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",13},"Matchstick"]

GraphData[{"Paley",13},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",13},"Edges"]]

3D All

GraphData[{"Paley",13},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",13},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",13},"Polyhedral"]

GraphData[{"Paley",13},"Graph",{"3D","Polyhedron"}]

{"Paley", 17}

Properties

The Paley graph of order 17 is the unique largest graph G such that neither G nor its complement contains a complete 4-vertex subgraph (Evans et al. 1981). It follows that the Ramsey number R(4) = 18.

Names

GraphData[{"Paley",17},"StandardName"]

GraphData[{"Paley",17},"StandardNames"]

Primary

GraphData[{"Paley",17}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",17},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",17},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",17},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",17},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",17},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",17},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",17},"Planar"]

GraphData[{"Paley",17},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",17},{"RCN","CN"}]

GraphData[{"Paley",17},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",17}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",17}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",17}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",17},"Circulant"]

GraphData[{"Paley",17},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[17]

Cases[GraphData[{"Paley",17},"StandardNames"],{"Circulant",i_}:>i]

CirculantIndices[GraphData[{"Paley",17}]]//Timing

gs=CirculantGraph1@@@CirculantIndices[GraphData[{"Paley",17}]]

BilateralGraphEmbeddingQ/@%

Halin

GraphData[{"Paley",17},"Halin"]

GraphData[{"Paley",17},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",17},"Rigid"]

GraphData[{"Paley",17},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",17},"Flexible"]

GraphData[{"Paley",17},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",17},"LCF"]

GraphData[{"Paley",17},"HamiltonianCycleCount"]

GraphData[{"Paley",17},"LCFSignature"]

GraphData[{"Paley",17},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",17}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",17}],All])[[All,2]]]//Timing

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Paley",17},".m.gz"]])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",17},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",17}],Debug->True]//Timing

GraphData[{"Paley",17},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",17},"VertexList"],GraphData[{"Paley",17},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",17},"Matchstick"]

GraphData[{"Paley",17},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",17},"Edges"]]

3D All

GraphData[{"Paley",17},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",17},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",17},"Polyhedral"]

GraphData[{"Paley",17},"Graph",{"3D","Polyhedron"}]

{"Paley", 25}

Names

GraphData[{"Paley",25},"StandardName"]

GraphData[{"Paley",25},"StandardNames"]

Primary

GraphData[{"Paley",25}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",25},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",25},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",25},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",25},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",25},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",25},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",25},"Planar"]

GraphData[{"Paley",25},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",25},{"RCN","CN"}]

GraphData[{"Paley",25},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",25}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",25}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",25}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",25}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",25},"Circulant"]

GraphData[{"Paley",25},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[25]

CirculantGraph@@@%

RecognizeGraph/@%

Cases[GraphData[{"Paley",25},"StandardNames"],{"Circulant",i_}:>i]

CirculantIndices[GraphData[{"Paley",25}]]//Timing

CirculantGraph1@@@CirculantIndices[GraphData[{"Paley",25}]]

Halin

GraphData[{"Paley",25},"Halin"]

GraphData[{"Paley",25},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",25},"Rigid"]

GraphData[{"Paley",25},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",25},"Flexible"]

GraphData[{"Paley",25},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",25},"LCF"]

GraphData[{"Paley",25},"HamiltonianCycleCount"]

GraphData[{"Paley",25},"LCFSignature"]

GraphData[{"Paley",25},"Graph","LCF"]//StyleGraphs

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

Order-5 LCF construction

Ed Pegg Jr., Sep. 23, 2010

paley25=Select[Subsets[Tuples[Range[0,4],{2}],{2}],MemberQ[#[[1]]-#[[2]],0]||Length[Union[Mod[#[[1]]-#[[2]],5]]]==1&];

g=Graph[UndirectedEdge@@@(Map[5 #[[1]]+#[[2]]&,paley25,{2}]+1)]

RecognizeGraph[g]

g0=Graph[UndirectedEdge@@@paley25,VertexCoordinates->Thread[Tuples[Range[0,4],{2}]->Table[{Sin[2 Pi x/25],Cos[2 Pi x/25]},{x,25}]],VertexLabels->Automatic]

RecognizeGraph@g0

LCFNotation@IndexGraph[g0]

g=BilateralLCFEmbedding[IndexGraph[g0]]

BilateralGraphEmbeddingQ@g

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",25}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",25}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

UnitDistance

GraphData[{"Paley",25},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",25}],Debug->True]//Timing

GraphData[{"Paley",25},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",25},"VertexList"],GraphData[{"Paley",25},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",25},"Matchstick"]

GraphData[{"Paley",25},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",25},"Edges"]]

3D All

GraphData[{"Paley",25},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",25},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",25},"Polyhedral"]

GraphData[{"Paley",25},"Graph",{"3D","Polyhedron"}]

{"Paley", 29}

Names

GraphData[{"Paley",29},"StandardName"]

GraphData[{"Paley",29},"StandardNames"]

Primary

GraphData[{"Paley",29}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",29},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",29},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",29},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",29},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",29},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",29},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",29},"Planar"]

GraphData[{"Paley",29},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",29},{"RCN","CN"}]

GraphData[{"Paley",29},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",29}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",29}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",29}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",29}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",29},"Circulant"]

GraphData[{"Paley",29},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[29]

Cases[GraphData[{"Paley",29},"StandardNames"],{"Circulant",i_}:>i]

CirculantIndices[GraphData[{"Paley",29}]]//Timing

gs=CirculantGraph1@@@CirculantIndices[GraphData[{"Paley",29}]]

BilateralGraphEmbeddingQ/@%

Halin

GraphData[{"Paley",29},"Halin"]

GraphData[{"Paley",29},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",29},"Rigid"]

GraphData[{"Paley",29},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",29},"Flexible"]

GraphData[{"Paley",29},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",29},"LCF"]

GraphData[{"Paley",29},"HamiltonianCycleCount"]

GraphData[{"Paley",29},"LCFSignature"]

GraphData[{"Paley",29},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",29}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",29}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",29},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",29}],Debug->True]//Timing

GraphData[{"Paley",29},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",29},"VertexList"],GraphData[{"Paley",29},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",29},"Matchstick"]

GraphData[{"Paley",29},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",29},"Edges"]]

3D All

GraphData[{"Paley",29},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",29},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",29},"Polyhedral"]

GraphData[{"Paley",29},"Graph",{"3D","Polyhedron"}]

{"Paley", 37}

Names

GraphData[{"Paley",37},"StandardName"]

GraphData[{"Paley",37},"StandardNames"]

Primary

GraphData[{"Paley",37}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",37},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",37},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",37},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",37},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",37},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",37},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",37},"Planar"]

GraphData[{"Paley",37},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",37},{"RCN","CN"}]

GraphData[{"Paley",37},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",37}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",37}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",37}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",37}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",37},"Circulant"]

GraphData[{"Paley",37},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[37]

Cases[GraphData[{"Paley",37},"StandardNames"],{"Circulant",i_}:>i]

(ci=CirculantIndices[GraphData[{"Paley",37}]])//Timing

CirculantGraph1@@@ci

BilateralGraphEmbeddingQ/@%

Halin

GraphData[{"Paley",37},"Halin"]

GraphData[{"Paley",37},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",37},"Rigid"]

GraphData[{"Paley",37},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",37},"Flexible"]

GraphData[{"Paley",37},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",37},"LCF"]

GraphData[{"Paley",37},"HamiltonianCycleCount"]

GraphData[{"Paley",37},"LCFSignature"]

GraphData[{"Paley",37},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",37}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",37}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",37},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",37}],Debug->True]//Timing

GraphData[{"Paley",37},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",37},"VertexList"],GraphData[{"Paley",37},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",37},"Matchstick"]

GraphData[{"Paley",37},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",37},"Edges"]]

3D All

GraphData[{"Paley",37},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",37},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",37},"Polyhedral"]

GraphData[{"Paley",37},"Graph",{"3D","Polyhedron"}]

{"Paley", 41}

Names

GraphData[{"Paley",41},"StandardName"]

GraphData[{"Paley",41},"StandardNames"]

Primary

GraphData[{"Paley",41}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",41},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",41},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",41},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",41},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",41},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",41},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",41},"Planar"]

GraphData[{"Paley",41},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",41},{"RCN","CN"}]

GraphData[{"Paley",41},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",41}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",41}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",41}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",41}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",41},"Circulant"]

GraphData[{"Paley",41},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[41]

Cases[GraphData[{"Paley",41},"StandardNames"],{"Circulant",i_}:>i]

(ci=CirculantIndices[GraphData[{"Paley",41}]])//Timing

gs=CirculantGraph1@@@ci

BilateralGraphEmbeddingQ/@gs

Halin

GraphData[{"Paley",41},"Halin"]

GraphData[{"Paley",41},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",41},"Rigid"]

GraphData[{"Paley",41},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",41},"Flexible"]

GraphData[{"Paley",41},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",41},"LCF"]

GraphData[{"Paley",41},"HamiltonianCycleCount"]

GraphData[{"Paley",41},"LCFSignature"]

GraphData[{"Paley",41},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",41}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",41}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",41},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",41}],Debug->True]//Timing

GraphData[{"Paley",41},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",41},"VertexList"],GraphData[{"Paley",41},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",41},"Matchstick"]

GraphData[{"Paley",41},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",41},"Edges"]]

3D All

GraphData[{"Paley",41},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",41},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",41},"Polyhedral"]

GraphData[{"Paley",41},"Graph",{"3D","Polyhedron"}]

{"Paley", 49}

Names

GraphData[{"Paley",49},"StandardName"]

GraphData[{"Paley",49},"StandardNames"]

Primary

GraphData[{"Paley",49}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",49},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",49},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",49},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",49},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",49},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",49},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",49},"Planar"]

GraphData[{"Paley",49},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",49},{"RCN","CN"}]

GraphData[{"Paley",49},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",49}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",49}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",49}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",49}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",49},"Circulant"]

GraphData[{"Paley",49},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[49]

CirculantGraph@@@%

RecognizeGraph/@%

Cases[GraphData[{"Paley",49},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraphQ[GraphData[{"Paley",49}]]//Timing

Halin

GraphData[{"Paley",49},"Halin"]

GraphData[{"Paley",49},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",49},"Rigid"]

GraphData[{"Paley",49},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",49},"Flexible"]

GraphData[{"Paley",49},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",49},"LCF"]

GraphData[{"Paley",49},"HamiltonianCycleCount"]

GraphData[{"Paley",49},"LCFSignature"]

GraphData[{"Paley",49},"Graph","LCF"]//StyleGraphs

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

LCF order-7 construction

g=BilateralLCFEmbedding@

LCFNotation@g

BilateralGraphEmbeddingQ@g

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",49}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",49}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",49},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",49}],Debug->True]//Timing

GraphData[{"Paley",49},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",49},"VertexList"],GraphData[{"Paley",49},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",49},"Matchstick"]

GraphData[{"Paley",49},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",49},"Edges"]]

3D All

GraphData[{"Paley",49},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",49},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",49},"Polyhedral"]

GraphData[{"Paley",49},"Graph",{"3D","Polyhedron"}]

{"Paley", 53}

Names

GraphData[{"Paley",53},"StandardName"]

GraphData[{"Paley",53},"StandardName"]

Primary

GraphData[{"Paley",53}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",53},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",53},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",53},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",53},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",53},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",53},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",53},"Planar"]

GraphData[{"Paley",53},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",53},{"RCN","CN"}]

GraphData[{"Paley",53},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",53}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",53}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",53}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",53}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",53},"Circulant"]

GraphData[{"Paley",53},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[53]

Cases[GraphData[{"Paley",53},"StandardNames"],{"Circulant",i_}:>i]

(ci=CirculantIndices[GraphData[{"Paley",53}]])//Timing

gs=CirculantGraph1@@@ci

gs=CirculantGraph1@@@Cases[GraphData[{"Paley",53},"StandardNames"],{"Circulant",i_}:>i]

BilateralGraphEmbeddingQ/@gs

Halin

GraphData[{"Paley",53},"Halin"]

GraphData[{"Paley",53},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",53},"Rigid"]

GraphData[{"Paley",53},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",53},"Flexible"]

GraphData[{"Paley",53},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",53},"LCF"]

GraphData[{"Paley",53},"HamiltonianCycleCount"]

GraphData[{"Paley",53},"LCFSignature"]

GraphData[{"Paley",53},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",53}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",53}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",53},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",53}],Debug->True]//Timing

GraphData[{"Paley",53},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",53},"VertexList"],GraphData[{"Paley",53},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",53},"Matchstick"]

GraphData[{"Paley",53},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",53},"Edges"]]

3D All

GraphData[{"Paley",53},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",53},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",53},"Polyhedral"]

GraphData[{"Paley",53},"Graph",{"3D","Polyhedron"}]

{"Paley", 61}

Names

GraphData[{"Paley",61},"StandardName"]

GraphData[{"Paley",61},"StandardNames"]

Primary

GraphData[{"Paley",61}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",61},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",61},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",61},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",61},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",61},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",61},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",61},"Planar"]

GraphData[{"Paley",61},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",61},{"RCN","CN"}]

GraphData[{"Paley",61},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",61}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",61}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",61}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",61}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",61},"Circulant"]

GraphData[{"Paley",61},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[61]

Cases[GraphData[{"Paley",61},"StandardNames"],{"Circulant",i_}:>i]

(ci=CirculantIndices[GraphData[{"Paley",61}],Debug->True])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Paley",61},"StandardNames"],{"Circulant",i_}:>i]

gs=CirculantGraph1@@@%

BilateralGraphEmbeddingQ/@%

Halin

GraphData[{"Paley",61},"Halin"]

GraphData[{"Paley",61},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",61},"Rigid"]

GraphData[{"Paley",61},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",61},"Flexible"]

GraphData[{"Paley",61},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",61},"LCF"]

GraphData[{"Paley",61},"HamiltonianCycleCount"]

GraphData[{"Paley",61},"LCFSignature"]

GraphData[{"Paley",61},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",61}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",61}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",61},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",61}],Debug->True]//Timing

GraphData[{"Paley",61},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",61},"VertexList"],GraphData[{"Paley",61},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",61},"Matchstick"]

GraphData[{"Paley",61},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",61},"Edges"]]

3D All

GraphData[{"Paley",61},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",61},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",61},"Polyhedral"]

GraphData[{"Paley",61},"Graph",{"3D","Polyhedron"}]

{"Paley", 73}

Names

GraphData[{"Paley",73},"StandardName"]

GraphData[{"Paley",73},"StandardNames"]

Primary

GraphData[{"Paley",73}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",73},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",73},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",73},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",73},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",73},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",73},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",73},"Planar"]

GraphData[{"Paley",73},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",73},{"RCN","CN"}]

GraphData[{"Paley",73},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",73}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",73}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",73}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",73}],TimeConstraint-> 5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",73},"Circulant"]

GraphData[{"Paley",73},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[73]

Cases[GraphData[{"Paley",73},"StandardNames"],{"Circulant",i_}:>i]

(ci=CirculantIndices[GraphData[{"Paley",73}],Debug->True])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Paley",73},"StandardNames"],{"Circulant",i_}:>i]

gs=CirculantGraph1@@@%

BilateralGraphEmbeddingQ/@%

Halin

GraphData[{"Paley",73},"Halin"]

GraphData[{"Paley",73},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",73},"Rigid"]

GraphData[{"Paley",73},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",73},"Flexible"]

GraphData[{"Paley",73},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",73},"LCF"]

GraphData[{"Paley",73},"HamiltonianCycleCount"]

GraphData[{"Paley",73},"LCFSignature"]

GraphData[{"Paley",73},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",73}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",73}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",73},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",73}],Debug->True]//Timing

GraphData[{"Paley",73},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",73},"VertexList"],GraphData[{"Paley",73},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",73},"Matchstick"]

GraphData[{"Paley",73},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",73},"Edges"]]

3D All

GraphData[{"Paley",73},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",73},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",73},"Polyhedral"]

GraphData[{"Paley",73},"Graph",{"3D","Polyhedron"}]

{"Paley", 81}

Names

GraphData[{"Paley",81},"StandardName"]

GraphData[{"Paley",81},"StandardNames"]

Primary

GraphData[{"Paley",81}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",81},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",81},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",81},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",81},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",81},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",81},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",81},"Planar"]

GraphData[{"Paley",81},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",81},{"RCN","CN"}]

GraphData[{"Paley",81},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",81}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",81}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",81}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",81}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",81},"Circulant"]

GraphData[{"Paley",81},"Graph","Circulant"]//StyleGraphs

Circulant construction

Cases[GraphData[{"Paley",81},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraphQ[GraphData[{"Paley",81}]]

Halin

GraphData[{"Paley",81},"Halin"]

GraphData[{"Paley",81},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",81},"Rigid"]

GraphData[{"Paley",81},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",81},"Flexible"]

GraphData[{"Paley",81},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",81},"LCF"]

GraphData[{"Paley",81},"HamiltonianCycleCount"]

GraphData[{"Paley",81},"LCFSignature"]

GraphData[{"Paley",81},"Graph","LCF"]//StyleGraphs

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

LCF order-3 construction

Ed Pegg Jr., Sep. 23, 2010

fieldPlus[pol1_,pol2_,mod_]:=Algebra`PolynomialPlusModList[pol1,pol2,mod]

fieldTimes[pol1_,pol2_,mod_,irred_]:=Algebra`PolynomialTimesModList[pol1,pol2,irred,mod]

prime=3;
size=81;
irredpoly={1,1,1,1,1};
elements=Tuples[Range[0,2],{4}];
sqrs=Union[Table[fieldTimes[elements[[n]],elements[[n]],3,irredpoly],{n,1,81}]];

paley81=Select[Subsets[elements,{2}],MemberQ[sqrs,fieldPlus[#[[1]],-#[[2]],3]]&];

Graph[UndirectedEdge@@@paley81]//RecognizeGraph

g0=Graph[UndirectedEdge@@@paley81,VertexCoordinates->Thread[Tuples[Range[0,2],{4}]->Table[{Sin[2 Pi x/81],Cos[2 Pi x/81]},{x,81}]]]

RecognizeGraph[g0]

g=BilateralLCFEmbedding[IndexGraph[g0]]

BilateralGraphEmbeddingQ@g

RecognizeGraph[g]

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",81}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",81}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",81},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",81}],Debug->True]//Timing

GraphData[{"Paley",81},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",81},"VertexList"],GraphData[{"Paley",81},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",81},"Matchstick"]

GraphData[{"Paley",81},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",81},"Edges"]]

3D All

GraphData[{"Paley",81},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",81},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",81},"Polyhedral"]

GraphData[{"Paley",81},"Graph",{"3D","Polyhedron"}]

{"Paley", 89}

Names

GraphData[{"Paley",89},"StandardName"]

GraphData[{"Paley",89},"StandardNames"]

Primary

GraphData[{"Paley",89}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",89},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",89},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",89},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",89},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",89},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",89},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",89},"Planar"]

GraphData[{"Paley",89},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",89},{"RCN","CN"}]

GraphData[{"Paley",89},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",89}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",89}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",89}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",89}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",89},"Circulant"]

GraphData[{"Paley",89},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[89]

(ci=CirculantIndices[GraphData[{"Paley",89}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Paley",89},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Paley",89},"Halin"]

GraphData[{"Paley",89},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",89},"Rigid"]

GraphData[{"Paley",89},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",89},"Flexible"]

GraphData[{"Paley",89},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",89},"LCF"]

GraphData[{"Paley",89},"HamiltonianCycleCount"]

GraphData[{"Paley",89},"LCFSignature"]

GraphData[{"Paley",89},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Paley",89}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",89}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",89},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",89}],Debug->True]//Timing

GraphData[{"Paley",89},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",89},"VertexList"],GraphData[{"Paley",89},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",89},"Matchstick"]

GraphData[{"Paley",89},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",89},"Edges"]]

3D All

GraphData[{"Paley",89},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",89},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",89},"Polyhedral"]

GraphData[{"Paley",89},"Graph",{"3D","Polyhedron"}]

{"Paley", 97}

Names

GraphData[{"Paley",97},"StandardName"]

GraphData[{"Paley",97},"StandardNames"]

Primary

GraphData[{"Paley",97}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",97},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",97},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",97},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",97},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",97},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",97},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",97},"Planar"]

GraphData[{"Paley",97},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",97},{"RCN","CN"}]

GraphData[{"Paley",97},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",97}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",97}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",97}],TimeConstraint->3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",97},"Circulant"]

GraphData[{"Paley",97},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[97]

GraphData[{"Paley",97},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Paley",89}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Paley",97},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Paley",97},"Halin"]

GraphData[{"Paley",97},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",97},"Rigid"]

GraphData[{"Paley",97},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",97},"Flexible"]

GraphData[{"Paley",97},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",97},"LCF"]

GraphData[{"Paley",97},"HamiltonianCycleCount"]

GraphData[{"Paley",97},"LCFSignature"]

GraphData[{"Paley",97},"Graph","LCF"]//StyleGraphs

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

LCF compute 10^6

Length[FindHamiltonianCycle[GraphData[{"Paley",97}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",97}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",97},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",97}],Debug->True]//Timing

GraphData[{"Paley",97},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",97},"VertexList"],GraphData[{"Paley",97},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Paley",97},"Matchstick"]

GraphData[{"Paley",97},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",97},"Edges"]]

3D All

GraphData[{"Paley",97},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",97},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",97},"Polyhedral"]

GraphData[{"Paley",97},"Graph",{"3D","Polyhedron"}]

{"Paley", 101}

Names

GraphData[{"Paley",101},"StandardName"]

GraphData[{"Paley",101},"StandardNames"]

Primary

GraphData[{"Paley",101}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",101},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",101},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",101},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",101},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",101},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",101},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",101},"Planar"]

GraphData[{"Paley",101},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",101},{"RCN","CN"}]

GraphData[{"Paley",101},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",101}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",101}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",101}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",101}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",101},"Circulant"]

GraphData[{"Paley",101},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[101]

GraphData[{"Paley",101},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Paley",101}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Paley",101},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Paley",101},"Halin"]

GraphData[{"Paley",101},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",101},"Rigid"]

GraphData[{"Paley",101},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",101},"Flexible"]

GraphData[{"Paley",101},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",101},"LCF"]

GraphData[{"Paley",101},"HamiltonianCycleCount"]

GraphData[{"Paley",101},"LCFSignature"]

GraphData[{"Paley",101},"Graph","LCF"]//StyleGraphs

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

LCF compute 10^6

Length[FindHamiltonianCycle[GraphData[{"Paley",101}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",101}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",101},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",101}],Debug->True]//Timing

GraphData[{"Paley",101},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",101},"VertexList"],GraphData[{"Paley",101},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",101},"Matchstick"]

GraphData[{"Paley",101},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",101},"Edges"]]

3D All

GraphData[{"Paley",101},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",101},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",101},"Polyhedral"]

GraphData[{"Paley",101},"Graph",{"3D","Polyhedron"}]

{"Paley", 109}

Names

GraphData[{"Paley",109},"StandardName"]

GraphData[{"Paley",109},"StandardNames"]

Primary

GraphData[{"Paley",109}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",109},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",109},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",109},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",109},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",109},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",109},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",109},"Planar"]

GraphData[{"Paley",109},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",109},{"RCN","CN"}]

GraphData[{"Paley",109},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",109}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",109}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",109}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",109}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",109},"Circulant"]

GraphData[{"Paley",109},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[109]

GraphData[{"Paley",109},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Paley",109}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Paley",109},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Paley",109},"Halin"]

GraphData[{"Paley",109},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",109},"Rigid"]

GraphData[{"Paley",109},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",109},"Flexible"]

GraphData[{"Paley",109},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",109},"LCF"]

GraphData[{"Paley",109},"HamiltonianCycleCount"]

GraphData[{"Paley",109},"LCFSignature"]

GraphData[{"Paley",109},"Graph","LCF"]//StyleGraphs

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

LCF compute 10^6

Length[FindHamiltonianCycle[GraphData[{"Paley",109}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",109}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",109},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",109}],Debug->True]//Timing

GraphData[{"Paley",109},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",109},"VertexList"],GraphData[{"Paley",109},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",109},"Matchstick"]

GraphData[{"Paley",109},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",109},"Edges"]]

3D All

GraphData[{"Paley",109},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",109},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",109},"Polyhedral"]

GraphData[{"Paley",109},"Graph",{"3D","Polyhedron"}]

{"Paley", 113}

Names

GraphData[{"Paley",113},"StandardName"]

GraphData[{"Paley",113},"StandardNames"]

Primary

GraphData[{"Paley",113}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",113},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",113},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",113},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",113},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",113},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",113},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",113},"Planar"]

GraphData[{"Paley",113},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",113},{"RCN","CN"}]

GraphData[{"Paley",113},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",113}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",113}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",113}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",113}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",113},"Circulant"]

GraphData[{"Paley",113},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[113]

GraphData[{"Paley",113},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Paley",113}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Paley",113},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Paley",113},"Halin"]

GraphData[{"Paley",113},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",113},"Rigid"]

GraphData[{"Paley",113},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",113},"Flexible"]

GraphData[{"Paley",113},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",113},"LCF"]

GraphData[{"Paley",113},"HamiltonianCycleCount"]

GraphData[{"Paley",113},"LCFSignature"]

GraphData[{"Paley",113},"Graph","LCF"]//StyleGraphs

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

LCF compute 10^6

Length[FindHamiltonianCycle[GraphData[{"Paley",113}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",113}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",113},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",113}],Debug->True]//Timing

GraphData[{"Paley",113},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",113},"VertexList"],GraphData[{"Paley",113},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",113},"Matchstick"]

GraphData[{"Paley",113},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",113},"Edges"]]

3D All

GraphData[{"Paley",113},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",113},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",113},"Polyhedral"]

GraphData[{"Paley",113},"Graph",{"3D","Polyhedron"}]

{"Paley", 121}

Names

GraphData[{"Paley",121},"StandardName"]

GraphData[{"Paley",121},"StandardNames"]

Primary

GraphData[{"Paley",121}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",121},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",121},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",121},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",121},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",121},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",121},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",121},"Planar"]

GraphData[{"Paley",121},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",121},{"RCN","CN"}]

GraphData[{"Paley",121},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",121}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",121}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",121}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",121}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",121},"Circulant"]

GraphData[{"Paley",121},"Graph","Circulant"]//StyleGraphs

Circulant construction

Cases[GraphData[{"Paley",121},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraphQ[GraphData[{"Paley",121}]]//Timing

Halin

GraphData[{"Paley",121},"Halin"]

GraphData[{"Paley",121},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",121},"Rigid"]

GraphData[{"Paley",121},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",121},"Flexible"]

GraphData[{"Paley",121},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",121},"LCF"]

GraphData[{"Paley",121},"HamiltonianCycleCount"]

GraphData[{"Paley",121},"LCFSignature"]

GraphData[{"Paley",121},"Graph","LCF"]//StyleGraphs

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

BilateralGraphEmbeddingQ/@%%

LCF compute 10^6

Length[FindHamiltonianCycle[GraphData[{"Paley",121}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",121}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",121},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",121}],Debug->True]//Timing

GraphData[{"Paley",121},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",121},"VertexList"],GraphData[{"Paley",121},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",121},"Matchstick"]

GraphData[{"Paley",121},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",121},"Edges"]]

3D All

GraphData[{"Paley",121},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",121},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",121},"Polyhedral"]

GraphData[{"Paley",121},"Graph",{"3D","Polyhedron"}]

{"Paley", 125}

Names

GraphData[{"Paley",125},"StandardName"]

GraphData[{"Paley",125},"StandardNames"]

Primary

GraphData[{"Paley",125}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",125},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",125},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",125},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",125},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",125},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",125},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",125},"Planar"]

GraphData[{"Paley",125},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",125},{"RCN","CN"}]

GraphData[{"Paley",125},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",125}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",125}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",125}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",125}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",125},"Circulant"]

GraphData[{"Paley",125},"Graph","Circulant"]//StyleGraphs

Circulant construction

Cases[GraphData[{"Paley",125},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraphQ[GraphData[{"Paley",125}]]//Timing

Halin

GraphData[{"Paley",125},"Halin"]

GraphData[{"Paley",125},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",125},"Rigid"]

GraphData[{"Paley",125},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",125},"Flexible"]

GraphData[{"Paley",125},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",125},"LCF"]

GraphData[{"Paley",125},"HamiltonianCycleCount"]

GraphData[{"Paley",125},"LCFSignature"]

GraphData[{"Paley",125},"Graph","LCF"]//StyleGraphs

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

LCF compute 10^6

Length[FindHamiltonianCycle[GraphData[{"Paley",125}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",125}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",125},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",125}],Debug->True]//Timing

GraphData[{"Paley",125},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",125},"VertexList"],GraphData[{"Paley",125},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",125},"Matchstick"]

GraphData[{"Paley",125},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",125},"Edges"]]

3D All

GraphData[{"Paley",125},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",125},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",125},"Polyhedral"]

GraphData[{"Paley",125},"Graph",{"3D","Polyhedron"}]

{"Paley", 137}

Names

GraphData[{"Paley",137},"StandardName"]

GraphData[{"Paley",137},"StandardNames"]

Primary

GraphData[{"Paley",137}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",137},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",137},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",137},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",137},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",137},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",137},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",137},"Planar"]

GraphData[{"Paley",137},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",137},{"RCN","CN"}]

GraphData[{"Paley",137},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",137}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",137}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",137}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",137}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",137},"Circulant"]

GraphData[{"Paley",137},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[137]

GraphData[{"Paley",137},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Paley",137}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Paley",137},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Paley",137},"Halin"]

GraphData[{"Paley",137},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",137},"Rigid"]

GraphData[{"Paley",137},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",137},"Flexible"]

GraphData[{"Paley",137},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",137},"LCF"]

GraphData[{"Paley",137},"HamiltonianCycleCount"]

GraphData[{"Paley",137},"LCFSignature"]

GraphData[{"Paley",137},"Graph","LCF"]//StyleGraphs

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

LCF compute 10^6

Length[FindHamiltonianCycle[GraphData[{"Paley",137}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",137}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",137},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",137}],Debug->True]//Timing

GraphData[{"Paley",137},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",137},"VertexList"],GraphData[{"Paley",137},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",137},"Matchstick"]

GraphData[{"Paley",137},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",137},"Edges"]]

3D All

GraphData[{"Paley",137},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",137},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",137},"Polyhedral"]

GraphData[{"Paley",137},"Graph",{"3D","Polyhedron"}]

{"Paley", 149}

Names

GraphData[{"Paley",149},"StandardName"]

GraphData[{"Paley",149},"StandardNames"]

Primary

GraphData[{"Paley",149}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",149},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",149},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",149},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",149},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",149},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",149},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",149},"Planar"]

GraphData[{"Paley",149},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",149},{"RCN","CN"}]

GraphData[{"Paley",149},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",149}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",149}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",149}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",149}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",149},"Circulant"]

GraphData[{"Paley",149},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[149]

GraphData[{"Paley",149},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Paley",149}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Paley",149},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Paley",149},"Halin"]

GraphData[{"Paley",149},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",149},"Rigid"]

GraphData[{"Paley",149},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",149},"Flexible"]

GraphData[{"Paley",149},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",149},"LCF"]

GraphData[{"Paley",149},"HamiltonianCycleCount"]

GraphData[{"Paley",149},"LCFSignature"]

GraphData[{"Paley",149},"Graph","LCF"]//StyleGraphs

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

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Paley",149}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",149},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",149}],Debug->True]//Timing

GraphData[{"Paley",149},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",149},"VertexList"],GraphData[{"Paley",149},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",149},"Matchstick"]

GraphData[{"Paley",149},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",149},"Edges"]]

3D All

GraphData[{"Paley",149},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",149},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",149},"Polyhedral"]

GraphData[{"Paley",149},"Graph",{"3D","Polyhedron"}]

{"Paley", 157}

Names

GraphData[{"Paley",157},"StandardName"]

GraphData[{"Paley",157},"StandardNames"]

Primary

GraphData[{"Paley",157}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",157},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",157},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",157},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",157},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",157},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",157},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",157},"Planar"]

GraphData[{"Paley",157},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",157},{"RCN","CN"}]

GraphData[{"Paley",157},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",157}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",157}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",157}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",157}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",157},"Circulant"]

GraphData[{"Paley",157},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[157]

GraphData[{"Paley",157},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Paley",157}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"Paley",157},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Halin

GraphData[{"Paley",157},"Halin"]

GraphData[{"Paley",157},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",157},"Rigid"]

GraphData[{"Paley",157},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",157},"Flexible"]

GraphData[{"Paley",157},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",157},"LCF"]

GraphData[{"Paley",157},"HamiltonianCycleCount"]

GraphData[{"Paley",157},"LCFSignature"]

GraphData[{"Paley",157},"Graph","LCF"]//StyleGraphs

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

LCF compute 10^6

Length[FindHamiltonianCycle[GraphData[{"Paley",157}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",157}],10^6])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

LCF compute 10^7

Length[FindHamiltonianCycle[GraphData[{"Paley",157}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"Paley",157}],10^7])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XXX}]]}]

Length[gs]

UnitDistance

GraphData[{"Paley",157},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",157}],Debug->True]//Timing

GraphData[{"Paley",157},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",157},"VertexList"],GraphData[{"Paley",157},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",157},"Matchstick"]

GraphData[{"Paley",157},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",157},"Edges"]]

3D All

GraphData[{"Paley",157},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",157},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",157},"Polyhedral"]

GraphData[{"Paley",157},"Graph",{"3D","Polyhedron"}]

{"Paley", 169}

Names

GraphData[{"Paley",169},"StandardName"]

GraphData[{"Paley",169},"StandardNames"]

Primary

GraphData[{"Paley",169}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Paley",169},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Paley",169},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Paley",169},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Paley",169},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Paley",169},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Paley",169},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Paley",169},"Planar"]

GraphData[{"Paley",169},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Paley",169},{"RCN","CN"}]

GraphData[{"Paley",169},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

(cn=CrossingNumber[GraphData[{"Paley",169}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",169}],TimeConstraint->300])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",169}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Paley",169}],TimeConstraint->5 3600])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Paley",169},"Circulant"]

GraphData[{"Paley",169},"Graph","Circulant"]//StyleGraphs

Circulant construction

QuadraticResidues[169]

CirculantGraph@@@%

RecognizeGraph/@%

Cases[GraphData[{"Paley",169},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraphQ[GraphData[{"Paley",169}]]//Timing

Halin

GraphData[{"Paley",169},"Halin"]

GraphData[{"Paley",169},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Paley",169},"Rigid"]

GraphData[{"Paley",169},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Paley",169},"Flexible"]

GraphData[{"Paley",169},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Paley",169},"LCF"]

GraphData[{"Paley",169},"HamiltonianCycleCount"]

GraphData[{"Paley",169},"LCFSignature"]

GraphData[{"Paley",169},"Graph","LCF"]//StyleGraphs

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

BilateralGraphEmbeddingQ/@%%

LCF compute 10^3

Tally[(lcf=LCF[GraphData[{"Paley",169}],10^3])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^4

Tally[(lcf=LCF[GraphData[{"Paley",169}],10^4])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Paley",169}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Paley",169},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Paley",169}],Debug->True]//Timing

GraphData[{"Paley",169},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Paley",169},"VertexList"],GraphData[{"Paley",169},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Paley",169},"Matchstick"]

GraphData[{"Paley",169},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Paley",169},"Edges"]]

3D All

GraphData[{"Paley",169},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Paley",169},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Paley",169},"Polyhedral"]

GraphData[{"Paley",169},"Graph",{"3D","Polyhedron"}]

Construction

Using Jacobsthal matrix

Jones, p. 158

primepowers=Select[Range[169],Mod[#,4]==1&&PrimePowerQ[#]&]

primes=Select[Range[169],Mod[#,4]==1&&PrimeQ[#]&]

JacobsthalMatrix[q_]:=Table[JacobiSymbol[i-j,q],{i,0,q-1},{j,0,q-1}]

adj[q_]:=AdjacencyGraph[(1/2)(JacobsthalMatrix[q]-IdentityMatrix[q]+ConstantArray[1,{q,q}])]

JacobsthalMatrix[13]

RecognizeGraph@adj[13]

RecognizeGraph@adj[13]

DeleteCases[{#,GraphData[{"Paley",#},"#"],RecognizeGraph[PaleyGraph[#]]}&/@primes,{_,x_,x_}]

Using FiniteFields

i=Select[Range[169],Mod[#,4]==1&&PrimePowerQ[#]&]

<<MathWorld`Graphs`

p=PaleyGraph[#,Method->Automatic]&/@i;//Timing

p=PaleyGraph[#,Method->"FiniteFields"]&/@i;//Timing

p=PaleyGraph[#,Method->"FiniteFields","EdgeMethod"->"Subsets"]&/@i;//Timing

RecognizeGraph/@p

GraphPlot[#,Method->None]&/@Take[p,8]

Print[{V[#],RecognizeGraph[#],RegularParameters[#],Spectrum[#]//SpectrumForm}//Timing//TraditionalForm]&/@p

Compare Subsets and Outer

Using FiniteFields

i=Select[Range[1000],Mod[#,4]==1&&PrimePowerQ[#]&]

p=PaleyGraph[#,Method->"FiniteFields"]&/@i;//Timing

p=PaleyGraph[#,Method->"FiniteFields","EdgeMethod"->"Subsets"]&/@i;//Timing

GraphData

GraphClassString

GraphClassString[GraphData["Paley"]]

GraphDataString 9

Print[GraphDataString[HammingGraph[2,3],
"Name"->"9-Paley graph",
"StandardName"->{"Paley",9},
"Classes"->{"DistanceRegular","Paley","Hamiltonian","Hamming"},
"NotationRules"->{"Hamming"->{2,3},"Paley"->9},
TimeConstraint->60,
Debug->True
]]

GraphDataString Prime

Print[GraphDataString[PaleyGraph[#],
"Name"->ToString[#]<>"-Paley graph",
"StandardName"->{"Paley",#},
"Classes"->{"Circulant","Paley","Hamiltonian"},
"NotationRules"->{"\"Paley\""->#},
TimeConstraint->60
]]&/@i

GraphDataString

file=OpenWrite["paley.m"]

WriteString[file,GraphDataString[PaleyGraph[#],
"Name"->ToString[#]<>"-Paley graph",
"Classes"->{"Paley"},
"StandardName"->{"Paley",#},
"Vertices"->None,
"NotationRules"->{"Paley"->#},
"Information"->"PaleyGraph",
Debug->True,
TimeConstraint->60
]
]&/@{49,73,81,89,97,101,109,113,121,125,137,149,157,169};