Haar Graph

Author

Eric W. Weisstein
March 1, 2024

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

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

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

Definition

<<MathWorld`Graphs`

HaarGraph[69]//RecognizeGraph

b=IntegerDigits[69,2]

Length[b]

Position[b,1]-1//Flatten

HaarAutomorphismQ[g_Graph,Cycles[cyc_]]:=Module[{len=Length/@cyc,n=VertexCount[g]},And[Length[cyc]==2,Equal@@len,Total[len]==n,AllTrue[cyc,IndependentVertexSetQ[g,#]&]]]

HaarGraphGenerators[g_Graph]:=Module[{n=VertexCount[g],m=EdgeCount[g]},If[m==1&&n==2,Return[True]];(*special case?*)If[Mod[n,2]!=0||m==0||m==Binomial[n,2]||Unequal@@VertexDegree[g]||BipartiteGraphQ[g]=!=True (*||VertexTransitiveGraphQ[g]=!=True*),Return[False]];
Select[GroupElements[GraphAutomorphismGroup[g]],HaarAutomorphismQ[g,#]&]]

HaarGraphGenerators[HaarGraph[69]]

stylize[sym_]:=Module[{base,sub},
{base,sub}=Characters[ToString[sym]];
Style[Subscript[Style[base,Italic],ToExpression@sub],Directive[16,FontFamily->"Times"]]
]

edges=Map[
stylize,
{{u0,v0},{u4,v0},{u6,v0},{u1,v1},{u5,v1},{u0,v1},{u2,v2},{u6,v2},{u1,v2},{u3,v3},{u0,v3},{u2,v3},{u4,v4},{u1,v4},{u3,v4},{u5,v5},{u2,v5},{u4,v5},{u6,v6},{u3,v6},{u5,v6}},
{2}]

g1=Graph[UndirectedEdge@@@edges]

iso=FindGraphIsomorphism[GraphData["HeawoodGraph"],g1,All]

isos=FindGraphIsomorphism[GraphData["HeawoodGraph"],g1,All];

iso=Normal@isos[[101]]

colors=iso/.HoldPattern[Rule[n_,v_]]:>Rule[n,If[FreeQ[v,"u"],White,Black]]

Annotate[GraphData["HeawoodGraph"],{VertexLabels->iso,VertexStyle->colors,VertexSize->Medium,EdgeStyle->Black}]

Counts

Number of Haar graphs on n nodes

GraphData

Length/@Table[GraphData["Haar",n],{n,12}]

Length/@Table[GraphData["Haar",n],{n,2,30,2}]

OEIS

A357000

seq=Cases[Import["https://oeis.org/A357000/b357000.txt","Table"],{_Integer,n_Integer}:>n]

ListLogPlot[{seq[[1;;All;;2]],seq[[2;;All;;2]]},PlotLegends->{"odd","even"}]

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n-k]//Head//Timing}],{k,0,5}]

FindGeneratingFunction[seq,x]//Head//Timing

FindLinearRecurrence[seq]//Head//Timing

Conecklace

A333764

A co-necklace is a finite sequence that is lexicographically greater than or equal to any cyclic rotation

Only the terms in this sequence can lead to unique Haar graphs

StandardIntegerComposition[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
coneckQ[q_]:=Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];

co1=Select[Range[10^6],coneckQ[StandardIntegerComposition[#]]&];//Timing

Check only co-necklace values

StandardIntegerPartition[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
coneck[q_]:=Block[{res},res=NestWhile[RotateRight,q,OrderedQ[{#,q}]&,1,Length[q]-1];OrderedQ[{res,q}]]
ConecklaceQ[n_]:=StandardIntegerPartition[StandardIntegerPartition[n]]

Do[
Clear[haar];
cnt=0;
Print[Flatten[{
k,
MaxMemoryUsed[Do[
If[ConecklaceQ[n]&&haar[g=CanonicalGraph@HaarGraph[n]]=!=True,haar[g]=True;cnt++],
{n,2^(k-1),2^k-1}]]//Timing,
cnt}]],
{k,30}]

coneckQ2[q_]:=AllTrue[NestList[RotateRight,q,Length[q]-1],OrderedQ[{#,q}]&]

co2=Select[Range[10^6],coneckQ2[stc[#]]&];//Timing

co1===co2

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;coneckQ3[q_]:=Block[{res},res=NestWhile[RotateRight,q,OrderedQ[{#,q}]&,1,Length[q]-1];OrderedQ[{res,q}]]

co3=Select[Range[10^6],coneckQ3[stc[#]]&];//Timing

co1===co3

CountDistinctBy

Table[CountDistinctBy[Table[HaarGraph[n],{n,(2^(k-1)),(2^k)-1}],CanonicalGraph],{k,18}]//Timing

Table[CountDistinctBy[Range[(2^(k-1)),(2^k)-1],CanonicalGraph[HaarGraph[#]]&],{k,18}]//Timing

Do[
Print[Flatten[{k,MaxMemoryUsed[cnt=CountDistinctBy[Table[HaarGraph[n],{n,2^(k-1),2^k-1}],CanonicalGraph]]//Timing,cnt}]],
{k,31}]//Timing

Incremental Union + Hash

Do[
haar={};
Print[Flatten[{k,MaxMemoryUsed[
Do[haar=Union[{Hash[CanonicalForm[HaarGraph[n]]]},haar],
{n,2^(k-1),2^k-1}];]//Timing,Length[haar]}]],
{k,30}]

Incremental Downvalues

Do[
Clear[haar];
cnt=0;
Print[Flatten[{k,MaxMemoryUsed[
Do[If[haar[g=CanonicalGraph@HaarGraph[n]]=!=True,haar[g]=True;cnt++],
{n,2^(k-1),2^k-1}]]//Timing,cnt}]],
{k,15}]

Graphic

GraphicsGrid[Partition[Table[Show[StyleGraphs@HaarGraph[n],PlotLabel->Style[H[n],Directive[Black,FontFamily->"Times"]]],{n,30}],6],ImageSize->800,Dividers->All,Alignment->Top]

Embeddings

GraphData["Haar*"]

{"Haar", 143}

Names

GraphData[{"Haar",143},"StandardName"]

GraphData[{"Haar",143},"StandardNames"]

Primary

GraphData[{"Haar",143}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",143},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",143},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",143},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",143},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",143},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",143},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",143},"Polyhedron"]

Bilateral

GraphData[{"Haar",143},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",143},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",143},"Planar"]

GraphData[{"Haar",143},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",143},{"RCN","CN"}]

GraphData[{"Haar",143},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",143}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",143}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Haar",143}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",143},"Circulant"]

GraphData[{"Haar",143},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",143},"Line"]

LineGraphQ[GraphData[{"Haar",143}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",143}&]

RootGraph[GraphData[{"Haar",143}]]

Halin

GraphData[{"Haar",143},"Halin"]

GraphData[{"Haar",143},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",143},"Rigid"]

GraphData[{"Haar",143},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",143},"Flexible"]

GraphData[{"Haar",143},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",143},"LCF"]

GraphData[{"Haar",143},"HamiltonianCycleCount"]

GraphData[{"Haar",143},"LCFSignature"]

GraphData[{"Haar",143},"LCFNotations"]

GraphData[{"Haar",143},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",143}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",143},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",143}],Debug->True]//Timing

GraphData[{"Haar",143},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",143},"VertexList"],GraphData[{"Haar",143},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",143}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",143},"Matchstick"]

GraphData[{"Haar",143},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",143},"Edges"]]

3D All

GraphData[{"Haar",143},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",143},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",143},"Polyhedral"]

GraphData[{"Haar",143},"Graph",{"3D","Polyhedron"}]

{"Haar", 151}

Names

GraphData[{"Haar",151},"StandardName"]

GraphData[{"Haar",151},"StandardNames"]

Primary

GraphData[{"Haar",151}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",151},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",151},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",151},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",151},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",151},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",151},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",151},"Polyhedron"]

Bilateral

GraphData[{"Haar",151},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",151},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",151},"Planar"]

GraphData[{"Haar",151},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",151},{"RCN","CN"}]

GraphData[{"Haar",151},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",151}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",151}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",151},"Circulant"]

GraphData[{"Haar",151},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",151},"Line"]

LineGraphQ[GraphData[{"Haar",151}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",151}&]

RootGraph[GraphData[{"Haar",151}]]

Halin

GraphData[{"Haar",151},"Halin"]

GraphData[{"Haar",151},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",151},"Rigid"]

GraphData[{"Haar",151},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",151},"Flexible"]

GraphData[{"Haar",151},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",151},"LCF"]

GraphData[{"Haar",151},"HamiltonianCycleCount"]

GraphData[{"Haar",151},"LCFSignature"]

GraphData[{"Haar",151},"LCFNotations"]

GraphData[{"Haar",151},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",151}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

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

gs

BilateralGraphEmbeddingQ/@%

UnitDistance

GraphData[{"Haar",151},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",151}],Debug->True]//Timing

GraphData[{"Haar",151},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",151},"VertexList"],GraphData[{"Haar",151},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",151}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",151},"Matchstick"]

GraphData[{"Haar",151},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",151},"Edges"]]

3D All

GraphData[{"Haar",151},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",151},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",151},"Polyhedral"]

GraphData[{"Haar",151},"Graph",{"3D","Polyhedron"}]

{"Haar", 155}

Names

GraphData[{"Haar",155},"StandardName"]

GraphData[{"Haar",155},"StandardNames"]

Primary

GraphData[{"Haar",155}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",155},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",155},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",155},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",155},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",155},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",155},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",155},"Polyhedron"]

Bilateral

GraphData[{"Haar",155},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",155},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",155},"Planar"]

GraphData[{"Haar",155},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",155},{"RCN","CN"}]

GraphData[{"Haar",155},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",155}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",155}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",155},"Circulant"]

GraphData[{"Haar",155},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",155},"Line"]

LineGraphQ[GraphData[{"Haar",155}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",155}&]

RootGraph[GraphData[{"Haar",155}]]

Halin

GraphData[{"Haar",155},"Halin"]

GraphData[{"Haar",155},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",155},"Rigid"]

GraphData[{"Haar",155},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",155},"Flexible"]

GraphData[{"Haar",155},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",155},"LCF"]

GraphData[{"Haar",155},"HamiltonianCycleCount"]

GraphData[{"Haar",155},"LCFSignature"]

GraphData[{"Haar",155},"LCFNotations"]

GraphData[{"Haar",155},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",155}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@%

UnitDistance

GraphData[{"Haar",155},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",155}],Debug->True]//Timing

GraphData[{"Haar",155},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",155},"VertexList"],GraphData[{"Haar",155},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",155}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",155},"Matchstick"]

GraphData[{"Haar",155},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",155},"Edges"]]

3D All

GraphData[{"Haar",155},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",155},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",155},"Polyhedral"]

GraphData[{"Haar",155},"Graph",{"3D","Polyhedron"}]

{"Haar", 175}

Names

GraphData[{"Haar",175},"StandardName"]

GraphData[{"Haar",175},"StandardNames"]

Primary

GraphData[{"Haar",175}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",175},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",175},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",175},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",175},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",175},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",175},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",175},"Polyhedron"]

Bilateral

GraphData[{"Haar",175},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",175},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",175},"Planar"]

GraphData[{"Haar",175},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",175},{"RCN","CN"}]

GraphData[{"Haar",175},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",175}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",175}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",175},"Circulant"]

GraphData[{"Haar",175},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",175},"Line"]

LineGraphQ[GraphData[{"Haar",175}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",175}&]

RootGraph[GraphData[{"Haar",175}]]

Halin

GraphData[{"Haar",175},"Halin"]

GraphData[{"Haar",175},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",175},"Rigid"]

GraphData[{"Haar",175},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",175},"Flexible"]

GraphData[{"Haar",175},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",175},"LCF"]

GraphData[{"Haar",175},"HamiltonianCycleCount"]

GraphData[{"Haar",175},"LCFSignature"]

GraphData[{"Haar",175},"LCFNotations"]

GraphData[{"Haar",175},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",175}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",175},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",175}],Debug->True]//Timing

GraphData[{"Haar",175},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",175},"VertexList"],GraphData[{"Haar",175},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",175}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",175},"Matchstick"]

GraphData[{"Haar",175},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",175},"Edges"]]

3D All

GraphData[{"Haar",175},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",175},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",175},"Polyhedral"]

GraphData[{"Haar",175},"Graph",{"3D","Polyhedron"}]

{"Haar", 187}

Names

GraphData[{"Haar",187},"StandardName"]

GraphData[{"Haar",187},"StandardNames"]

Primary

GraphData[{"Haar",187}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",187},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",187},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",187},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",187},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",187},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",187},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",187},"Polyhedron"]

Bilateral

GraphData[{"Haar",187},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",187},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",187},"Planar"]

GraphData[{"Haar",187},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",187},{"RCN","CN"}]

GraphData[{"Haar",187},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",187}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",187}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",187},"Circulant"]

GraphData[{"Haar",187},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",187},"Line"]

LineGraphQ[GraphData[{"Haar",187}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",187}&]

RootGraph[GraphData[{"Haar",187}]]

Halin

GraphData[{"Haar",187},"Halin"]

GraphData[{"Haar",187},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",187},"Rigid"]

GraphData[{"Haar",187},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",187},"Flexible"]

GraphData[{"Haar",187},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",187},"LCF"]

GraphData[{"Haar",187},"HamiltonianCycleCount"]

GraphData[{"Haar",187},"LCFSignature"]

GraphData[{"Haar",187},"LCFNotations"]

GraphData[{"Haar",187},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",187}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

lcf

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

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

Length[gs]

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

gs

Length[gs]

UnitDistance

GraphData[{"Haar",187},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",187}],Debug->True]//Timing

GraphData[{"Haar",187},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",187},"VertexList"],GraphData[{"Haar",187},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",187}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",187},"Matchstick"]

GraphData[{"Haar",187},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",187},"Edges"]]

3D All

GraphData[{"Haar",187},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",187},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",187},"Polyhedral"]

GraphData[{"Haar",187},"Graph",{"3D","Polyhedron"}]

{"Haar", 279}

Names

GraphData[{"Haar",279},"StandardName"]

GraphData[{"Haar",279},"StandardNames"]

Primary

GraphData[{"Haar",279}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",279},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",279},"EdgeList"]]

Default embedding

GraphPlot[Graph[GraphData[{"Haar",279},"Edges"],GraphLayout->"HighDimensionalEmbedding"]]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",279},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",279},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",279},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",279},"Polyhedron"]

Bilateral

GraphData[{"Haar",279},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",279},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",279},"Planar"]

GraphData[{"Haar",279},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",279},{"RCN","CN"}]

GraphData[{"Haar",279},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",279}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",279}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",279},"Circulant"]

GraphData[{"Haar",279},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",279},"Line"]

LineGraphQ[GraphData[{"Haar",279}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",279}&]

RootGraph[GraphData[{"Haar",279}]]

Halin

GraphData[{"Haar",279},"Halin"]

GraphData[{"Haar",279},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",279},"Rigid"]

GraphData[{"Haar",279},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",279},"Flexible"]

GraphData[{"Haar",279},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",279},"LCF"]

GraphData[{"Haar",279},"HamiltonianCycleCount"]

GraphData[{"Haar",279},"LCFSignature"]

GraphData[{"Haar",279},"LCFNotations"]

GraphData[{"Haar",279},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",279}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",279},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",279}],Debug->True]//Timing

GraphData[{"Haar",279},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",279},"VertexList"],GraphData[{"Haar",279},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",279}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",279},"Matchstick"]

GraphData[{"Haar",279},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",279},"Edges"]]

3D All

GraphData[{"Haar",279},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",279},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",279},"Polyhedral"]

GraphData[{"Haar",279},"Graph",{"3D","Polyhedron"}]

{"Haar", 301}

Names

GraphData[{"Haar",301},"StandardName"]

GraphData[{"Haar",301},"StandardNames"]

Primary

GraphData[{"Haar",301}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",301},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",301},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",301},"Edges"]

v=Join[CirclePoints[12],CirclePoints[1/2,6]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,3,5,7,9,11,1,14,15,16,17,18,13,14,6,8,10,12,2,4,6,16,10,18,2,14],e[11,13,3,15,7,17,11,10],e[1,12,17],e[18,9,12],e[9,8,5,4,13],{8,15},{16,5},{1,4},{2,3},{6,7}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",301},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",301},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",301},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",301},"Polyhedron"]

Bilateral

GraphData[{"Haar",301},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",301},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",301},"Planar"]

GraphData[{"Haar",301},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",301},{"RCN","CN"}]

GraphData[{"Haar",301},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",301}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",301}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",301},"Circulant"]

GraphData[{"Haar",301},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",301},"Line"]

LineGraphQ[GraphData[{"Haar",301}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",301}&]

RootGraph[GraphData[{"Haar",301}]]

Halin

GraphData[{"Haar",301},"Halin"]

GraphData[{"Haar",301},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",301},"Rigid"]

GraphData[{"Haar",301},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",301},"Flexible"]

GraphData[{"Haar",301},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",301},"LCF"]

GraphData[{"Haar",301},"HamiltonianCycleCount"]

GraphData[{"Haar",301},"LCFSignature"]

GraphData[{"Haar",301},"LCFNotations"]

GraphData[{"Haar",301},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",301}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",301},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",301}],Debug->True]//Timing

GraphData[{"Haar",301},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",301},"VertexList"],GraphData[{"Haar",301},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",301}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",301},"Matchstick"]

GraphData[{"Haar",301},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",301},"Edges"]]

3D All

GraphData[{"Haar",301},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",301},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",301},"Polyhedral"]

GraphData[{"Haar",301},"Graph",{"3D","Polyhedron"}]

{"Haar", 303}

Names

GraphData[{"Haar",303},"StandardName"]

GraphData[{"Haar",303},"StandardNames"]

Primary

GraphData[{"Haar",303}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",303},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",303},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",303},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",303},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",303},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",303},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",303},"Polyhedron"]

Bilateral

GraphData[{"Haar",303},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",303},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",303},"Planar"]

GraphData[{"Haar",303},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",303},{"RCN","CN"}]

GraphData[{"Haar",303},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",303}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",303}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",303},"Circulant"]

GraphData[{"Haar",303},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",303},"Line"]

LineGraphQ[GraphData[{"Haar",303}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",303}&]

RootGraph[GraphData[{"Haar",303}]]

Halin

GraphData[{"Haar",303},"Halin"]

GraphData[{"Haar",303},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",303},"Rigid"]

GraphData[{"Haar",303},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",303},"Flexible"]

GraphData[{"Haar",303},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",303},"LCF"]

GraphData[{"Haar",303},"HamiltonianCycleCount"]

GraphData[{"Haar",303},"LCFSignature"]

GraphData[{"Haar",303},"LCFNotations"]

GraphData[{"Haar",303},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",303}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",303},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",303}],Debug->True]//Timing

GraphData[{"Haar",303},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",303},"VertexList"],GraphData[{"Haar",303},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",303}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",303},"Matchstick"]

GraphData[{"Haar",303},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",303},"Edges"]]

3D All

GraphData[{"Haar",303},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",303},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",303},"Polyhedral"]

GraphData[{"Haar",303},"Graph",{"3D","Polyhedron"}]

{"Haar", 523}

Names

GraphData[{"Haar",523},"StandardName"]

GraphData[{"Haar",523},"StandardNames"]

Primary

GraphData[{"Haar",523}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",523},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",523},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",523},"Edges"]

v=Join[CirclePoints[12],CirclePoints[5/8,8]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,12,2,3,4,5,7,6,8,9,10,11,1,20,13,12,10,18,17,6,4,14,2,16,17,11,19,14,13,5,15,18,8,20,19,9,7,16,15,3,1]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",523},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",523},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",523},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",523},"Polyhedron"]

Bilateral

GraphData[{"Haar",523},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",523},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",523},"Planar"]

GraphData[{"Haar",523},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",523},{"RCN","CN"}]

GraphData[{"Haar",523},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",523}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",523}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

GraphPlot@RotateGraph[,-2Pi/5]

v={{0,0},{7,0},{7,7},{0,7},{1,1},{6,1},{2,2},{5,2},{2,3},{5,3},{3,3},{4,3},{3,4},{4,4},{3,5},{4,5},{1,6},{3,6},{4,6},{6,6}}/7;
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[9,15,16,10,8],e[9,1,2,3,18,19,4,1,5,7,8,6,2,10,12,14,16,19,20,6,5,17,18,15,13,11,9,7,12],e[8,11,4],e[4,17,13,14,20,3,12]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",523},"Circulant"]

GraphData[{"Haar",523},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",523},"Line"]

LineGraphQ[GraphData[{"Haar",523}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",523}&]

RootGraph[GraphData[{"Haar",523}]]

Halin

GraphData[{"Haar",523},"Halin"]

GraphData[{"Haar",523},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",523},"Rigid"]

GraphData[{"Haar",523},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",523},"Flexible"]

GraphData[{"Haar",523},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",523},"LCF"]

GraphData[{"Haar",523},"HamiltonianCycleCount"]

GraphData[{"Haar",523},"LCFSignature"]

GraphData[{"Haar",523},"LCFNotations"]

GraphData[{"Haar",523},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",523}],All][[All,All,1]]]//Timing

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",523},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",523}],Debug->True]//Timing

GraphData[{"Haar",523},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",523},"VertexList"],GraphData[{"Haar",523},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",523}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",523},"Matchstick"]

GraphData[{"Haar",523},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",523},"Edges"]]

3D All

GraphData[{"Haar",523},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",523},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",523},"Polyhedral"]

GraphData[{"Haar",523},"Graph",{"3D","Polyhedron"}]

{"Haar", 525}

Names

GraphData[{"Haar",525},"StandardName"]

GraphData[{"Haar",525},"StandardNames"]

Primary

GraphData[{"Haar",525}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",525},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",525},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",525},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",525},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",525},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",525},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",525},"Polyhedron"]

Bilateral

GraphData[{"Haar",525},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",525},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",525},"Planar"]

GraphData[{"Haar",525},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",525},{"RCN","CN"}]

GraphData[{"Haar",525},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",525}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",525}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

GraphPlot@RotateGraph[,-Pi/4]

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

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

GraphPlot@

v=(#+1)/11&/@{{-1,-1},{10,-1},{6,0},{5,2},{0,3},{5,3},{2,4},{3,4},{4,4},{5,4},{4,5},{5,5},{6,5},{7,5},{4,6},{9,6},{4,7},{3,9},{-1,10},{10,10}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,20,19,1,5,6,16,20,17,15,11,9,4,3,2,14,13,12,11,7,5,15,16,14],e[18,19,7,8,9,10,14],e[1,4,6,10,12,17,18,8,3,13,18]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",525},"Circulant"]

GraphData[{"Haar",525},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",525},"Line"]

LineGraphQ[GraphData[{"Haar",525}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",525}&]

RootGraph[GraphData[{"Haar",525}]]

Halin

GraphData[{"Haar",525},"Halin"]

GraphData[{"Haar",525},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",525},"Rigid"]

GraphData[{"Haar",525},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",525},"Flexible"]

GraphData[{"Haar",525},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",525},"LCF"]

GraphData[{"Haar",525},"HamiltonianCycleCount"]

GraphData[{"Haar",525},"LCFSignature"]

GraphData[{"Haar",525},"LCFNotations"]

GraphData[{"Haar",525},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",525}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",525},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",525}],Debug->True]//Timing

GraphData[{"Haar",525},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",525},"VertexList"],GraphData[{"Haar",525},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",525}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",525},"Matchstick"]

GraphData[{"Haar",525},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",525},"Edges"]]

3D All

GraphData[{"Haar",525},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",525},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",525},"Polyhedral"]

GraphData[{"Haar",525},"Graph",{"3D","Polyhedron"}]

{"Haar", 527}

Names

GraphData[{"Haar",527},"StandardName"]

GraphData[{"Haar",527},"StandardNames"]

Primary

GraphData[{"Haar",527}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",527},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",527},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",527},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",527},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",527},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",527},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",527},"Polyhedron"]

Bilateral

GraphData[{"Haar",527},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",527},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",527},"Planar"]

GraphData[{"Haar",527},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",527},{"RCN","CN"}]

GraphData[{"Haar",527},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",527}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",527}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",527},"Circulant"]

GraphData[{"Haar",527},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",527},"Line"]

LineGraphQ[GraphData[{"Haar",527}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",527}&]

RootGraph[GraphData[{"Haar",527}]]

Halin

GraphData[{"Haar",527},"Halin"]

GraphData[{"Haar",527},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",527},"Rigid"]

GraphData[{"Haar",527},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",527},"Flexible"]

GraphData[{"Haar",527},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",527},"LCF"]

GraphData[{"Haar",527},"HamiltonianCycleCount"]

GraphData[{"Haar",527},"LCFSignature"]

GraphData[{"Haar",527},"LCFNotations"]

GraphData[{"Haar",527},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",527}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",527},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",527}],Debug->True]//Timing

GraphData[{"Haar",527},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",527},"VertexList"],GraphData[{"Haar",527},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",527}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",527},"Matchstick"]

GraphData[{"Haar",527},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",527},"Edges"]]

3D All

GraphData[{"Haar",527},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",527},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",527},"Polyhedral"]

GraphData[{"Haar",527},"Graph",{"3D","Polyhedron"}]

{"Haar", 531}

Names

GraphData[{"Haar",531},"StandardName"]

GraphData[{"Haar",531},"StandardNames"]

Primary

GraphData[{"Haar",531}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",531},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",531},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",531},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",531},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",531},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",531},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",531},"Polyhedron"]

Bilateral

GraphData[{"Haar",531},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",531},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",531},"Planar"]

GraphData[{"Haar",531},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",531},{"RCN","CN"}]

GraphData[{"Haar",531},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",531}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",531}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",531},"Circulant"]

GraphData[{"Haar",531},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",531},"Line"]

LineGraphQ[GraphData[{"Haar",531}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",531}&]

RootGraph[GraphData[{"Haar",531}]]

Halin

GraphData[{"Haar",531},"Halin"]

GraphData[{"Haar",531},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",531},"Rigid"]

GraphData[{"Haar",531},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",531},"Flexible"]

GraphData[{"Haar",531},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",531},"LCF"]

GraphData[{"Haar",531},"HamiltonianCycleCount"]

GraphData[{"Haar",531},"LCFSignature"]

GraphData[{"Haar",531},"LCFNotations"]

GraphData[{"Haar",531},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",531}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",531},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",531}],Debug->True]//Timing

GraphData[{"Haar",531},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",531},"VertexList"],GraphData[{"Haar",531},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",531}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",531},"Matchstick"]

GraphData[{"Haar",531},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",531},"Edges"]]

3D All

GraphData[{"Haar",531},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",531},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",531},"Polyhedral"]

GraphData[{"Haar",531},"Graph",{"3D","Polyhedron"}]

{"Haar", 533}

Names

GraphData[{"Haar",533},"StandardName"]

GraphData[{"Haar",533},"StandardNames"]

Primary

GraphData[{"Haar",533}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",533},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",533},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",533},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",533},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",533},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",533},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",533},"Polyhedron"]

Bilateral

GraphData[{"Haar",533},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",533},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",533},"Planar"]

GraphData[{"Haar",533},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",533},{"RCN","CN"}]

GraphData[{"Haar",533},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",533}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",533}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Haar",533}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",533},"Circulant"]

GraphData[{"Haar",533},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",533},"Line"]

LineGraphQ[GraphData[{"Haar",533}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",533}&]

RootGraph[GraphData[{"Haar",533}]]

Halin

GraphData[{"Haar",533},"Halin"]

GraphData[{"Haar",533},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",533},"Rigid"]

GraphData[{"Haar",533},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",533},"Flexible"]

GraphData[{"Haar",533},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",533},"LCF"]

GraphData[{"Haar",533},"HamiltonianCycleCount"]

GraphData[{"Haar",533},"LCFSignature"]

GraphData[{"Haar",533},"LCFNotations"]

GraphData[{"Haar",533},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",533}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",533},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",533}],Debug->True]//Timing

GraphData[{"Haar",533},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",533},"VertexList"],GraphData[{"Haar",533},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",533}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",533},"Matchstick"]

GraphData[{"Haar",533},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",533},"Edges"]]

3D All

GraphData[{"Haar",533},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",533},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",533},"Polyhedral"]

GraphData[{"Haar",533},"Graph",{"3D","Polyhedron"}]

{"Haar", 535}

Names

GraphData[{"Haar",535},"StandardName"]

GraphData[{"Haar",535},"StandardNames"]

Primary

GraphData[{"Haar",535}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",535},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",535},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",535},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",535},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",535},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",535},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",535},"Polyhedron"]

Bilateral

GraphData[{"Haar",535},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",535},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",535},"Planar"]

GraphData[{"Haar",535},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",535},{"RCN","CN"}]

GraphData[{"Haar",535},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",535}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",535}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",535},"Circulant"]

GraphData[{"Haar",535},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",535},"Line"]

LineGraphQ[GraphData[{"Haar",535}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",535}&]

RootGraph[GraphData[{"Haar",535}]]

Halin

GraphData[{"Haar",535},"Halin"]

GraphData[{"Haar",535},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",535},"Rigid"]

GraphData[{"Haar",535},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",535},"Flexible"]

GraphData[{"Haar",535},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",535},"LCF"]

GraphData[{"Haar",535},"HamiltonianCycleCount"]

GraphData[{"Haar",535},"LCFSignature"]

GraphData[{"Haar",535},"LCFNotations"]

GraphData[{"Haar",535},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",535}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",535},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",535}],Debug->True]//Timing

GraphData[{"Haar",535},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",535},"VertexList"],GraphData[{"Haar",535},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",535}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",535},"Matchstick"]

GraphData[{"Haar",535},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",535},"Edges"]]

3D All

GraphData[{"Haar",535},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",535},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",535},"Polyhedral"]

GraphData[{"Haar",535},"Graph",{"3D","Polyhedron"}]

{"Haar", 539}

Names

GraphData[{"Haar",539},"StandardName"]

GraphData[{"Haar",539},"StandardNames"]

Primary

GraphData[{"Haar",539}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",539},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",539},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",539},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",539},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",539},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",539},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",539},"Polyhedron"]

Bilateral

GraphData[{"Haar",539},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",539},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",539},"Planar"]

GraphData[{"Haar",539},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",539},{"RCN","CN"}]

GraphData[{"Haar",539},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",539}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",539}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",539},"Circulant"]

GraphData[{"Haar",539},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",539},"Line"]

LineGraphQ[GraphData[{"Haar",539}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",539}&]

RootGraph[GraphData[{"Haar",539}]]

Halin

GraphData[{"Haar",539},"Halin"]

GraphData[{"Haar",539},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",539},"Rigid"]

GraphData[{"Haar",539},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",539},"Flexible"]

GraphData[{"Haar",539},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",539},"LCF"]

GraphData[{"Haar",539},"HamiltonianCycleCount"]

GraphData[{"Haar",539},"LCFSignature"]

GraphData[{"Haar",539},"LCFNotations"]

GraphData[{"Haar",539},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",539}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",539},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",539}],Debug->True]//Timing

GraphData[{"Haar",539},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",539},"VertexList"],GraphData[{"Haar",539},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",539}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",539},"Matchstick"]

GraphData[{"Haar",539},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",539},"Edges"]]

3D All

GraphData[{"Haar",539},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",539},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",539},"Polyhedral"]

GraphData[{"Haar",539},"Graph",{"3D","Polyhedron"}]

{"Haar", 547}

Names

GraphData[{"Haar",547},"StandardName"]

GraphData[{"Haar",547},"StandardNames"]

Primary

GraphData[{"Haar",547}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",547},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",547},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",547},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",547},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",547},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",547},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",547},"Polyhedron"]

Bilateral

GraphData[{"Haar",547},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",547},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",547},"Planar"]

GraphData[{"Haar",547},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",547},{"RCN","CN"}]

GraphData[{"Haar",547},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",547}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",547}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",547},"Circulant"]

GraphData[{"Haar",547},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",547},"Line"]

LineGraphQ[GraphData[{"Haar",547}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",547}&]

RootGraph[GraphData[{"Haar",547}]]

Halin

GraphData[{"Haar",547},"Halin"]

GraphData[{"Haar",547},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",547},"Rigid"]

GraphData[{"Haar",547},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",547},"Flexible"]

GraphData[{"Haar",547},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",547},"LCF"]

GraphData[{"Haar",547},"HamiltonianCycleCount"]

GraphData[{"Haar",547},"LCFSignature"]

GraphData[{"Haar",547},"LCFNotations"]

GraphData[{"Haar",547},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",547}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

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

gs

UnitDistance

GraphData[{"Haar",547},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",547}],Debug->True]//Timing

GraphData[{"Haar",547},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",547},"VertexList"],GraphData[{"Haar",547},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",547}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",547},"Matchstick"]

GraphData[{"Haar",547},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",547},"Edges"]]

3D All

GraphData[{"Haar",547},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",547},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",547},"Polyhedral"]

GraphData[{"Haar",547},"Graph",{"3D","Polyhedron"}]

{"Haar", 551}

Names

GraphData[{"Haar",551},"StandardName"]

GraphData[{"Haar",551},"StandardNames"]

Primary

GraphData[{"Haar",551}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",551},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",551},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",551},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",551},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",551},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",551},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",551},"Polyhedron"]

Bilateral

GraphData[{"Haar",551},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",551},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",551},"Planar"]

GraphData[{"Haar",551},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",551},{"RCN","CN"}]

GraphData[{"Haar",551},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",551}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",551}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",551},"Circulant"]

GraphData[{"Haar",551},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",551},"Line"]

LineGraphQ[GraphData[{"Haar",551}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",551}&]

RootGraph[GraphData[{"Haar",551}]]

Halin

GraphData[{"Haar",551},"Halin"]

GraphData[{"Haar",551},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",551},"Rigid"]

GraphData[{"Haar",551},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",551},"Flexible"]

GraphData[{"Haar",551},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",551},"LCF"]

GraphData[{"Haar",551},"HamiltonianCycleCount"]

GraphData[{"Haar",551},"LCFSignature"]

GraphData[{"Haar",551},"LCFNotations"]

GraphData[{"Haar",551},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",551}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",551},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",551}],Debug->True]//Timing

GraphData[{"Haar",551},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",551},"VertexList"],GraphData[{"Haar",551},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",551}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",551},"Matchstick"]

GraphData[{"Haar",551},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",551},"Edges"]]

3D All

GraphData[{"Haar",551},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",551},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",551},"Polyhedral"]

GraphData[{"Haar",551},"Graph",{"3D","Polyhedron"}]

{"Haar", 555}

Names

GraphData[{"Haar",555},"StandardName"]

GraphData[{"Haar",555},"StandardNames"]

Primary

GraphData[{"Haar",555}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",555},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",555},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",555},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",555},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",555},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",555},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",555},"Polyhedron"]

Bilateral

GraphData[{"Haar",555},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",555},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",555},"Planar"]

GraphData[{"Haar",555},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",555},{"RCN","CN"}]

GraphData[{"Haar",555},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",555}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",555}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",555},"Circulant"]

GraphData[{"Haar",555},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",555},"Line"]

LineGraphQ[GraphData[{"Haar",555}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",555}&]

RootGraph[GraphData[{"Haar",555}]]

Halin

GraphData[{"Haar",555},"Halin"]

GraphData[{"Haar",555},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",555},"Rigid"]

GraphData[{"Haar",555},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",555},"Flexible"]

GraphData[{"Haar",555},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",555},"LCF"]

GraphData[{"Haar",555},"HamiltonianCycleCount"]

GraphData[{"Haar",555},"LCFSignature"]

GraphData[{"Haar",555},"LCFNotations"]

GraphData[{"Haar",555},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",555}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",555},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",555}],Debug->True]//Timing

GraphData[{"Haar",555},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",555},"VertexList"],GraphData[{"Haar",555},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",555}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",555},"Matchstick"]

GraphData[{"Haar",555},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",555},"Edges"]]

3D All

GraphData[{"Haar",555},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",555},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",555},"Polyhedral"]

GraphData[{"Haar",555},"Graph",{"3D","Polyhedron"}]

{"Haar", 558}

Names

GraphData[{"Haar",558},"StandardName"]

GraphData[{"Haar",558},"StandardNames"]

Primary

GraphData[{"Haar",558}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",558},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",558},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",558},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",558},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",558},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",558},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",558},"Polyhedron"]

Bilateral

GraphData[{"Haar",558},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",558},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",558},"Planar"]

GraphData[{"Haar",558},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",558},{"RCN","CN"}]

GraphData[{"Haar",558},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",558}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",558}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",558},"Circulant"]

GraphData[{"Haar",558},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",558},"Line"]

LineGraphQ[GraphData[{"Haar",558}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",558}&]

RootGraph[GraphData[{"Haar",558}]]

Halin

GraphData[{"Haar",558},"Halin"]

GraphData[{"Haar",558},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",558},"Rigid"]

GraphData[{"Haar",558},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",558},"Flexible"]

GraphData[{"Haar",558},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",558},"LCF"]

GraphData[{"Haar",558},"HamiltonianCycleCount"]

GraphData[{"Haar",558},"LCFSignature"]

GraphData[{"Haar",558},"LCFNotations"]

GraphData[{"Haar",558},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",558}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",558},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",558}],Debug->True]//Timing

GraphData[{"Haar",558},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",558},"VertexList"],GraphData[{"Haar",558},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",558}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",558},"Matchstick"]

GraphData[{"Haar",558},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",558},"Edges"]]

3D All

GraphData[{"Haar",558},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",558},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",558},"Polyhedral"]

GraphData[{"Haar",558},"Graph",{"3D","Polyhedron"}]

{"Haar", 559}

Names

GraphData[{"Haar",559},"StandardName"]

GraphData[{"Haar",559},"StandardNames"]

Primary

GraphData[{"Haar",559}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",559},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",559},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",559},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",559},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",559},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",559},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",559},"Polyhedron"]

Bilateral

GraphData[{"Haar",559},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",559},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",559},"Planar"]

GraphData[{"Haar",559},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",559},{"RCN","CN"}]

GraphData[{"Haar",559},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",559}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",559}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",559},"Circulant"]

GraphData[{"Haar",559},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",559},"Line"]

LineGraphQ[GraphData[{"Haar",559}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",559}&]

RootGraph[GraphData[{"Haar",559}]]

Halin

GraphData[{"Haar",559},"Halin"]

GraphData[{"Haar",559},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",559},"Rigid"]

GraphData[{"Haar",559},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",559},"Flexible"]

GraphData[{"Haar",559},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",559},"LCF"]

GraphData[{"Haar",559},"HamiltonianCycleCount"]

GraphData[{"Haar",559},"LCFSignature"]

GraphData[{"Haar",559},"LCFNotations"]

GraphData[{"Haar",559},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",559}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

ByteCount[lcf]

DeleteCases[lcf,{_,1|2}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",559},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",559}],Debug->True]//Timing

GraphData[{"Haar",559},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",559},"VertexList"],GraphData[{"Haar",559},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",559}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",559},"Matchstick"]

GraphData[{"Haar",559},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",559},"Edges"]]

3D All

GraphData[{"Haar",559},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",559},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",559},"Polyhedral"]

GraphData[{"Haar",559},"Graph",{"3D","Polyhedron"}]

{"Haar", 563}

Names

GraphData[{"Haar",563},"StandardName"]

GraphData[{"Haar",563},"StandardNames"]

Primary

GraphData[{"Haar",563}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",563},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",563},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",563},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",563},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",563},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",563},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",563},"Polyhedron"]

Bilateral

GraphData[{"Haar",563},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",563},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",563},"Planar"]

GraphData[{"Haar",563},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",563},{"RCN","CN"}]

GraphData[{"Haar",563},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",563}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",563}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",563},"Circulant"]

GraphData[{"Haar",563},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",563},"Line"]

LineGraphQ[GraphData[{"Haar",563}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",563}&]

RootGraph[GraphData[{"Haar",563}]]

Halin

GraphData[{"Haar",563},"Halin"]

GraphData[{"Haar",563},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",563},"Rigid"]

GraphData[{"Haar",563},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",563},"Flexible"]

GraphData[{"Haar",563},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",563},"LCF"]

GraphData[{"Haar",563},"HamiltonianCycleCount"]

GraphData[{"Haar",563},"LCFSignature"]

GraphData[{"Haar",563},"LCFNotations"]

GraphData[{"Haar",563},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",563}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",563},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",563}],Debug->True]//Timing

GraphData[{"Haar",563},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",563},"VertexList"],GraphData[{"Haar",563},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",563}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",563},"Matchstick"]

GraphData[{"Haar",563},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",563},"Edges"]]

3D All

GraphData[{"Haar",563},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",563},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",563},"Polyhedral"]

GraphData[{"Haar",563},"Graph",{"3D","Polyhedron"}]

{"Haar", 565}

Names

GraphData[{"Haar",565},"StandardName"]

GraphData[{"Haar",565},"StandardNames"]

Primary

GraphData[{"Haar",565}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",565},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",565},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",565},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",565},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",565},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",565},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",565},"Polyhedron"]

Bilateral

GraphData[{"Haar",565},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",565},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",565},"Planar"]

GraphData[{"Haar",565},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",565},{"RCN","CN"}]

GraphData[{"Haar",565},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",565}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",565}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",565},"Circulant"]

GraphData[{"Haar",565},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",565},"Line"]

LineGraphQ[GraphData[{"Haar",565}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",565}&]

RootGraph[GraphData[{"Haar",565}]]

Halin

GraphData[{"Haar",565},"Halin"]

GraphData[{"Haar",565},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",565},"Rigid"]

GraphData[{"Haar",565},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",565},"Flexible"]

GraphData[{"Haar",565},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",565},"LCF"]

GraphData[{"Haar",565},"HamiltonianCycleCount"]

GraphData[{"Haar",565},"LCFSignature"]

GraphData[{"Haar",565},"LCFNotations"]

GraphData[{"Haar",565},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",565}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",565},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",565}],Debug->True]//Timing

GraphData[{"Haar",565},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",565},"VertexList"],GraphData[{"Haar",565},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",565}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",565},"Matchstick"]

GraphData[{"Haar",565},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",565},"Edges"]]

3D All

GraphData[{"Haar",565},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",565},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",565},"Polyhedral"]

GraphData[{"Haar",565},"Graph",{"3D","Polyhedron"}]

{"Haar", 567}

Names

GraphData[{"Haar",567},"StandardName"]

GraphData[{"Haar",567},"StandardNames"]

Primary

GraphData[{"Haar",567}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",567},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",567},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",567},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",567},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",567},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",567},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",567},"Polyhedron"]

Bilateral

GraphData[{"Haar",567},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",567},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",567},"Planar"]

GraphData[{"Haar",567},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",567},{"RCN","CN"}]

GraphData[{"Haar",567},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",567}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",567}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",567},"Circulant"]

GraphData[{"Haar",567},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",567},"Line"]

LineGraphQ[GraphData[{"Haar",567}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",567}&]

RootGraph[GraphData[{"Haar",567}]]

Halin

GraphData[{"Haar",567},"Halin"]

GraphData[{"Haar",567},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",567},"Rigid"]

GraphData[{"Haar",567},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",567},"Flexible"]

GraphData[{"Haar",567},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",567},"LCF"]

GraphData[{"Haar",567},"HamiltonianCycleCount"]

GraphData[{"Haar",567},"LCFSignature"]

GraphData[{"Haar",567},"LCFNotations"]

GraphData[{"Haar",567},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",567}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

ByteCount[lcf]

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",567},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",567}],Debug->True]//Timing

GraphData[{"Haar",567},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",567},"VertexList"],GraphData[{"Haar",567},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",567}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",567},"Matchstick"]

GraphData[{"Haar",567},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",567},"Edges"]]

3D All

GraphData[{"Haar",567},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",567},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",567},"Polyhedral"]

GraphData[{"Haar",567},"Graph",{"3D","Polyhedron"}]

{"Haar", 571}

Names

GraphData[{"Haar",571},"StandardName"]

GraphData[{"Haar",571},"StandardNames"]

Primary

GraphData[{"Haar",571}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",571},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",571},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",571},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",571},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",571},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",571},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",571},"Polyhedron"]

Bilateral

GraphData[{"Haar",571},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",571},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",571},"Planar"]

GraphData[{"Haar",571},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",571},{"RCN","CN"}]

GraphData[{"Haar",571},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",571}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",571}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",571},"Circulant"]

GraphData[{"Haar",571},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",571},"Line"]

LineGraphQ[GraphData[{"Haar",571}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",571}&]

RootGraph[GraphData[{"Haar",571}]]

Halin

GraphData[{"Haar",571},"Halin"]

GraphData[{"Haar",571},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",571},"Rigid"]

GraphData[{"Haar",571},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",571},"Flexible"]

GraphData[{"Haar",571},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",571},"LCF"]

GraphData[{"Haar",571},"HamiltonianCycleCount"]

GraphData[{"Haar",571},"LCFSignature"]

GraphData[{"Haar",571},"LCFNotations"]

GraphData[{"Haar",571},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",571}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1|2}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",571},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",571}],Debug->True]//Timing

GraphData[{"Haar",571},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",571},"VertexList"],GraphData[{"Haar",571},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",571}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",571},"Matchstick"]

GraphData[{"Haar",571},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",571},"Edges"]]

3D All

GraphData[{"Haar",571},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",571},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",571},"Polyhedral"]

GraphData[{"Haar",571},"Graph",{"3D","Polyhedron"}]

{"Haar", 575}

Names

GraphData[{"Haar",575},"StandardName"]

GraphData[{"Haar",575},"StandardNames"]

Primary

GraphData[{"Haar",575}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",575},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",575},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",575},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",575},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",575},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",575},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",575},"Polyhedron"]

Bilateral

GraphData[{"Haar",575},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",575},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",575},"Planar"]

GraphData[{"Haar",575},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",575},{"RCN","CN"}]

GraphData[{"Haar",575},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",575}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",575}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",575},"Circulant"]

GraphData[{"Haar",575},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",575},"Line"]

LineGraphQ[GraphData[{"Haar",575}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",575}&]

RootGraph[GraphData[{"Haar",575}]]

Halin

GraphData[{"Haar",575},"Halin"]

GraphData[{"Haar",575},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",575},"Rigid"]

GraphData[{"Haar",575},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",575},"Flexible"]

GraphData[{"Haar",575},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",575},"LCF"]

GraphData[{"Haar",575},"HamiltonianCycleCount"]

GraphData[{"Haar",575},"LCFSignature"]

GraphData[{"Haar",575},"LCFNotations"]

GraphData[{"Haar",575},"Graph","LCF"]//StyleGraphs

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

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Haar",575}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Haar",575}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute 5*^7

Tally[(lcf=LCF[GraphData[{"Haar",575}],5*^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

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

Length[gs]

gs

LCFNotation/@gs

nicelcf={{{{-9,-7,-5,-3,3},{-3,3,5,7,9}},10},{{{-9,-7,-5,-3,5},{-7,-5,-3,3,7},{-7,-3,3,5,7},{-5,3,5,7,9}},5},{{{-9,-7,-3,3,9},{-9,-3,3,7,9},{-9,-7,3,5,9},{-9,-5,-3,7,9}},5},{{{-9,-7,3,5,7},{-7,-5,-3,5,7},{-7,-5,3,5,7},{-7,-5,-3,7,9}},5},{{{-9,-7,-5,-3,5},{-5,-3,3,5,7},{-7,-5,-3,3,9},{-9,3,5,7,9}},5},{{{-9,-7,-5,-3,9},{-9,-7,-3,3,7},{-3,3,5,7,9},{-9,-5,3,5,9}},5},{{{-9,-7,-5,3,5},{-7,-5,-3,7,9},{-9,-3,3,7,9},{-9,-3,3,5,9}},5},{{{-9,-7,-5,7,9},{-9,-3,5,7,9},{-9,-5,-3,3,9},{-9,-7,3,5,9}},5},{{{-9,-5,-3,3,5},{-7,-5,-3,3,5},{-7,-5,-3,3,7},{-3,3,5,7,9}},5}};

l={{{"Haar",575},{0,nicelcf}}}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",575}],All][[All,All,1]]]//Timing

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

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

DeleteCases[lcf,{_,1}]

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

lcf={{{{-9,-7,-5,-3,3},{-3,3,5,7,9}},10},{{{-9,-7,-5,-3,9},{-9,3,5,7,9}},10},{{{-9,-7,-5,5,7},{-7,-5,5,7,9}},10},{{{-9,-7,-3,5,7},{-7,-5,3,7,9}},10},{{{-7,-5,-3,3,5},{-5,-3,3,5,7}},10},{{{-9,-7,-5,-3,3},{-7,-3,3,5,7},{-5,-3,3,5,7},{-5,-3,3,5,9}},5},{{{-9,-7,-5,-3,3},{-7,-3,3,7,9},{-9,3,5,7,9},{-9,-5,-3,5,9}},5},{{{-9,-7,-5,-3,5},{-7,-5,-3,3,7},{-7,-3,3,5,7},{-5,3,5,7,9}},5},{{{-9,-7,-5,-3,5},{-5,-3,3,5,7},{-7,-5,-3,3,9},{-9,3,5,7,9}},5},{{{-9,-7,-5,-3,7},{-7,-3,3,5,7},{-7,-5,-3,3,7},{-7,3,5,7,9}},5},{{{-9,-7,-5,-3,7},{-7,-3,3,7,9},{-9,-3,3,5,7},{-7,-5,3,5,9}},5},{{{-9,-7,-5,-3,9},{-9,-7,-3,3,7},{-3,3,5,7,9},{-9,-5,3,5,9}},5},{{{-9,-7,-5,-3,9},{-9,-3,3,5,7},{-7,-5,-3,3,5},{-5,3,5,7,9}},5},{{{-9,-7,-5,3,5},{-7,-5,-3,7,9},{-9,-3,3,7,9},{-9,-3,3,5,9}},5},{{{-9,-7,-5,3,5},{-5,-3,5,7,9},{-9,-7,-5,3,9},{-9,-3,5,7,9}},5},{{{-9,-7,-5,3,9},{-9,-7,-3,7,9},{-9,-7,3,7,9},{-9,-3,5,7,9}},5},{{{-9,-7,-5,3,9},{-9,-7,5,7,9},{-9,-5,-3,7,9},{-9,-3,3,5,9}},5},{{{-9,-7,-5,5,7},{-7,-5,-3,5,7},{-7,-5,3,7,9},{-9,-7,5,7,9}},5},{{{-9,-7,-5,5,9},{-9,-5,-3,5,7},{-7,-5,3,5,9},{-9,-5,5,7,9}},5},{{{-9,-7,-5,5,9},{-9,-5,5,7,9},{-9,-5,-3,5,9},{-9,-5,3,5,9}},5},{{{-9,-7,-5,7,9},{-9,-7,-3,5,7},{-7,-5,3,5,7},{-7,-5,5,7,9}},5},{{{-9,-7,-5,7,9},{-9,-3,5,7,9},{-9,-5,-3,3,9},{-9,-7,3,5,9}},5},{{{-9,-7,-3,3,5},{-7,-5,3,5,7},{-7,-5,-3,5,7},{-5,-3,3,7,9}},5},{{{-9,-7,-3,3,5},{-5,-3,3,7,9},{-9,-3,3,5,9},{-9,-5,-3,3,9}},5},{{{-9,-7,-3,3,7},{-7,3,5,7,9},{-9,-5,-3,5,7},{-7,-5,-3,3,9}},5},{{{-9,-7,-3,3,9},{-9,-7,3,5,7},{-5,-3,5,7,9},{-9,-5,-3,3,9}},5},{{{-9,-7,-3,3,9},{-9,-7,3,7,9},{-9,-7,-3,7,9},{-9,-3,3,7,9}},5},{{{-9,-7,-3,3,9},{-9,-3,3,7,9},{-9,-7,3,5,9},{-9,-5,-3,7,9}},5},{{{-9,-7,3,5,7},{-7,-5,-3,5,7},{-7,-5,3,5,7},{-7,-5,-3,7,9}},5},{{{-9,-5,-3,3,5},{-7,-5,-3,3,5},{-7,-5,-3,3,7},{-3,3,5,7,9}},5},{{{-9,-5,-3,3,5},{-7,-5,-3,3,9},{-9,-3,3,5,7},{-5,-3,3,5,9}},5}};

l={{{"Haar",575},{0,Missing["TooLarge",lcf]}}};

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Haar",575},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",575}],Debug->True]//Timing

GraphData[{"Haar",575},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",575},"VertexList"],GraphData[{"Haar",575},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",575}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",575},"Matchstick"]

GraphData[{"Haar",575},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",575},"Edges"]]

3D All

GraphData[{"Haar",575},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",575},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",575},"Polyhedral"]

GraphData[{"Haar",575},"Graph",{"3D","Polyhedron"}]

{"Haar", 591}

Names

GraphData[{"Haar",591},"StandardName"]

GraphData[{"Haar",591},"StandardNames"]

Primary

GraphData[{"Haar",591}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",591},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",591},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",591},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",591},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",591},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",591},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",591},"Polyhedron"]

Bilateral

GraphData[{"Haar",591},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",591},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",591},"Planar"]

GraphData[{"Haar",591},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",591},{"RCN","CN"}]

GraphData[{"Haar",591},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",591}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",591}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",591},"Circulant"]

GraphData[{"Haar",591},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",591},"Line"]

LineGraphQ[GraphData[{"Haar",591}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",591}&]

RootGraph[GraphData[{"Haar",591}]]

Halin

GraphData[{"Haar",591},"Halin"]

GraphData[{"Haar",591},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",591},"Rigid"]

GraphData[{"Haar",591},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",591},"Flexible"]

GraphData[{"Haar",591},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",591},"LCF"]

GraphData[{"Haar",591},"HamiltonianCycleCount"]

GraphData[{"Haar",591},"LCFSignature"]

GraphData[{"Haar",591},"LCFNotations"]

GraphData[{"Haar",591},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",591}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

ByteCount[lcf]

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",591},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",591}],Debug->True]//Timing

GraphData[{"Haar",591},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",591},"VertexList"],GraphData[{"Haar",591},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",591}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",591},"Matchstick"]

GraphData[{"Haar",591},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",591},"Edges"]]

3D All

GraphData[{"Haar",591},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",591},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",591},"Polyhedral"]

GraphData[{"Haar",591},"Graph",{"3D","Polyhedron"}]

{"Haar", 599}

Names

GraphData[{"Haar",599},"StandardName"]

GraphData[{"Haar",599},"StandardNames"]

Primary

GraphData[{"Haar",599}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",599},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",599},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",599},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",599},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",599},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",599},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",599},"Polyhedron"]

Bilateral

GraphData[{"Haar",599},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",599},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",599},"Planar"]

GraphData[{"Haar",599},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",599},{"RCN","CN"}]

GraphData[{"Haar",599},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",599}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",599}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",599},"Circulant"]

GraphData[{"Haar",599},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",599},"Line"]

LineGraphQ[GraphData[{"Haar",599}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",599}&]

RootGraph[GraphData[{"Haar",599}]]

Halin

GraphData[{"Haar",599},"Halin"]

GraphData[{"Haar",599},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",599},"Rigid"]

GraphData[{"Haar",599},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",599},"Flexible"]

GraphData[{"Haar",599},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",599},"LCF"]

GraphData[{"Haar",599},"HamiltonianCycleCount"]

GraphData[{"Haar",599},"LCFSignature"]

GraphData[{"Haar",599},"LCFNotations"]

GraphData[{"Haar",599},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",599}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

ByteCount[lcf]

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",599},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",599}],Debug->True]//Timing

GraphData[{"Haar",599},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",599},"VertexList"],GraphData[{"Haar",599},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",599}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",599},"Matchstick"]

GraphData[{"Haar",599},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",599},"Edges"]]

3D All

GraphData[{"Haar",599},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",599},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",599},"Polyhedral"]

GraphData[{"Haar",599},"Graph",{"3D","Polyhedron"}]

{"Haar", 607}

Names

GraphData[{"Haar",607},"StandardName"]

GraphData[{"Haar",607},"StandardNames"]

Primary

GraphData[{"Haar",607}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",607},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",607},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",607},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",607},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",607},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",607},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",607},"Polyhedron"]

Bilateral

GraphData[{"Haar",607},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",607},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",607},"Planar"]

GraphData[{"Haar",607},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",607},{"RCN","CN"}]

GraphData[{"Haar",607},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",607}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",607}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",607},"Circulant"]

GraphData[{"Haar",607},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",607},"Line"]

LineGraphQ[GraphData[{"Haar",607}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",607}&]

RootGraph[GraphData[{"Haar",607}]]

Halin

GraphData[{"Haar",607},"Halin"]

GraphData[{"Haar",607},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",607},"Rigid"]

GraphData[{"Haar",607},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",607},"Flexible"]

GraphData[{"Haar",607},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",607},"LCF"]

GraphData[{"Haar",607},"HamiltonianCycleCount"]

GraphData[{"Haar",607},"LCFSignature"]

GraphData[{"Haar",607},"LCFNotations"]

GraphData[{"Haar",607},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Haar",607}],TimeConstraint->120]

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Haar",607}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

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

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

Length[gs]

gs

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",607}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

gzcat Haar-607.m.gz | head -1000 > ~/haar-607.m

nicelcf={{{{-9,-7,-5,-3,5},{-5,3,5,7,9}},10},{{{-9,-7,-5,-3,7},{-7,3,5,7,9}},10},{{{-9,-7,-5,7,9},{-9,-7,5,7,9}},10},{{{-9,-7,-3,3,5},{-5,-3,3,7,9}},10},{{{-9,-7,3,5,7},{-7,-5,-3,7,9}},10},{{{-9,-5,-3,3,5},{-5,-3,3,5,9}},10},{{{-9,-5,-3,3,9},{-9,-3,3,5,9}},10},{{{-9,-3,3,5,7},{-7,-5,-3,3,9}},10},{{{-7,-5,-3,3,7},{-7,-3,3,5,7}},10},{{{-7,-5,-3,5,7},{-7,-5,3,5,7}},10},{{{-9,-7,-5,-3,3},{-7,-3,3,7,9},{-9,-7,-3,3,7},{-3,3,5,7,9}},5},{{{-9,-7,-5,-3,3},{-7,3,5,7,9},{-9,-5,-3,5,7},{-5,-3,3,5,9}},5},{{{-9,-7,-5,-3,3},{-7,3,5,7,9},{-9,-5,5,7,9},{-9,-5,-3,5,9}},5},{{{-9,-7,-5,-3,3},{-3,3,5,7,9},{-9,-5,3,5,9},{-9,-5,-3,5,9}},5},{{{-9,-7,-5,-3,5},{-7,-5,-3,3,7},{-7,3,5,7,9},{-9,-5,5,7,9}},5},{{{-9,-7,-5,-3,5},{-5,-3,3,5,7},{-7,-5,3,5,9},{-9,-5,5,7,9}},5},{{{-9,-7,-5,-3,5},{-5,-3,3,5,7},{-5,-3,3,5,9},{-9,-5,3,5,9}},5},{{{-9,-7,-5,-3,5},{-5,3,5,7,9},{-9,-5,-3,5,9},{-9,-5,3,5,9}},5},{{{-9,-7,-5,-3,7},{-7,-3,3,5,7},{-5,3,5,7,9},{-9,-7,-5,5,9}},5},{{{-9,-7,-5,-3,7},{-7,3,5,7,9},{-9,-5,-3,5,7},{-7,-5,3,5,9}},5},{{{-9,-7,-5,-3,7},{-3,3,5,7,9},{-9,-5,-3,3,5},{-7,-5,3,5,9}},5},{{{-9,-7,-5,-3,7},{-3,3,5,7,9},{-9,-5,3,5,9},{-9,-7,-5,5,9}},5},{{{-9,-7,-5,-3,9},{-9,-7,-3,3,7},{-7,-3,3,7,9},{-9,3,5,7,9}},5},{{{-9,-7,-5,-3,9},{-9,-3,3,5,7},{-7,-5,3,5,9},{-9,-5,5,7,9}},5},{{{-9,-7,-5,-3,9},{-9,3,5,7,9},{-9,-7,-5,5,9},{-9,-5,5,7,9}},5},{{{-9,-7,-5,-3,9},{-9,3,5,7,9},{-9,-5,-3,5,9},{-9,-5,3,5,9}},5},{{{-9,-7,-5,3,5},{-7,-5,-3,5,7},{-7,-5,3,7,9},{-9,-3,5,7,9}},5},{{{-9,-7,-5,3,5},{-7,-5,-3,5,7},{-5,-3,3,7,9},{-9,-3,3,5,9}},5},{{{-9,-7,-5,3,5},{-7,-5,-3,7,9},{-9,-7,3,5,7},{-5,-3,5,7,9}},5},{{{-9,-7,-5,3,5},{-7,-5,5,7,9},{-9,-7,-5,5,7},{-5,-3,5,7,9}},5},{{{-9,-7,-5,3,5},{-7,-5,5,7,9},{-9,-7,-5,7,9},{-9,-3,5,7,9}},5},{{{-9,-7,-5,3,9},{-9,-7,-3,5,7},{-7,-5,3,5,7},{-5,-3,5,7,9}},5},{{{-9,-7,-5,3,9},{-9,-7,-3,5,7},{-7,-5,3,7,9},{-9,-3,5,7,9}},5},{{{-9,-7,-5,3,9},{-9,-7,5,7,9},{-9,-7,-5,5,7},{-5,-3,5,7,9}},5},{{{-9,-7,-5,3,9},{-9,-3,5,7,9},{-9,-5,-3,3,9},{-9,-3,3,5,9}},5},{{{-9,-7,-5,5,7},{-7,-5,-3,7,9},{-9,-7,3,7,9},{-9,-7,5,7,9}},5},{{{-9,-7,-5,5,7},{-7,-5,-3,7,9},{-9,-3,3,7,9},{-9,-7,3,5,9}},5},{{{-9,-7,-5,5,7},{-7,-5,5,7,9},{-9,-5,-3,7,9},{-9,-7,3,5,9}},5},{{{-9,-7,-5,5,9},{-9,-5,-3,5,7},{-7,-5,-3,3,5},{-5,3,5,7,9}},5},{{{-9,-7,-5,5,9},{-9,-5,-3,5,7},{-7,-5,-3,3,9},{-9,3,5,7,9}},5},{{{-9,-7,-5,7,9},{-9,-7,-3,5,7},{-5,-3,3,7,9},{-9,-7,3,5,9}},5},{{{-9,-7,-5,7,9},{-9,-7,-3,7,9},{-9,-7,3,5,7},{-7,-5,5,7,9}},5},{{{-9,-7,-5,7,9},{-9,-7,-3,7,9},{-9,-7,3,7,9},{-9,-7,5,7,9}},5},{{{-9,-7,-5,7,9},{-9,-7,5,7,9},{-9,-5,-3,7,9},{-9,-7,3,5,9}},5},{{{-9,-7,-3,3,5},{-7,-5,3,5,7},{-7,-5,-3,7,9},{-9,-3,3,7,9}},5},{{{-9,-7,-3,3,5},{-7,-5,3,5,7},{-5,-3,5,7,9},{-9,-5,-3,3,9}},5},{{{-9,-7,-3,3,5},{-7,-5,3,7,9},{-9,-7,-3,7,9},{-9,-3,3,7,9}},5},{{{-9,-7,-3,3,5},{-7,-5,3,7,9},{-9,-7,5,7,9},{-9,-5,-3,7,9}},5},{{{-9,-7,-3,3,5},{-5,-3,3,7,9},{-9,-7,3,5,9},{-9,-5,-3,7,9}},5},{{{-9,-7,-3,3,7},{-7,-3,3,5,7},{-7,-5,-3,3,7},{-7,-3,3,7,9}},5},{{{-9,-7,-3,3,7},{-7,-3,3,5,7},{-5,-3,3,5,7},{-7,-5,-3,3,9}},5},{{{-9,-7,-3,3,7},{-7,-3,3,7,9},{-9,-3,3,5,7},{-7,-5,-3,3,9}},5},{{{-9,-7,-3,3,9},{-9,-7,3,5,7},{-7,-5,-3,5,7},{-5,-3,3,7,9}},5},{{{-9,-7,-3,3,9},{-9,-7,3,5,7},{-7,-5,5,7,9},{-9,-5,-3,7,9}},5},{{{-9,-7,-3,3,9},{-9,-7,3,7,9},{-9,-7,-3,5,7},{-5,-3,3,7,9}},5},{{{-9,-7,-3,3,9},{-9,-3,3,7,9},{-9,-3,3,5,9},{-9,-5,-3,3,9}},5},{{{-9,-7,-3,5,7},{-7,-5,3,7,9},{-9,-7,-3,7,9},{-9,-7,3,7,9}},5},{{{-9,-7,-3,7,9},{-9,-7,3,5,7},{-7,-5,-3,7,9},{-9,-7,3,7,9}},5},{{{-9,-5,-3,3,5},{-7,-5,-3,3,5},{-5,3,5,7,9},{-9,-5,-3,5,9}},5},{{{-9,-5,-3,3,5},{-7,-5,3,5,9},{-9,-5,-3,5,7},{-5,-3,3,5,9}},5},{{{-9,-5,-3,3,5},{-5,-3,3,5,9},{-9,-5,3,5,9},{-9,-5,-3,5,9}},5},{{{-9,-5,-3,5,7},{-7,-5,-3,3,5},{-5,-3,3,5,7},{-7,-5,3,5,9}},5},{{{-9,-3,3,5,7},{-7,-5,-3,3,5},{-7,-5,-3,3,7},{-7,-3,3,7,9}},5}};

DeleteCases[lcf,{_,1|2}]

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

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[nicelcf,6,5])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Haar",607},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",607}],Debug->True]//Timing

GraphData[{"Haar",607},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",607},"VertexList"],GraphData[{"Haar",607},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",607}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",607},"Matchstick"]

GraphData[{"Haar",607},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",607},"Edges"]]

3D All

GraphData[{"Haar",607},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",607},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",607},"Polyhedral"]

GraphData[{"Haar",607},"Graph",{"3D","Polyhedron"}]

{"Haar", 631}

Names

GraphData[{"Haar",631},"StandardName"]

GraphData[{"Haar",631},"StandardNames"]

Primary

GraphData[{"Haar",631}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",631},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",631},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",631},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",631},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",631},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",631},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",631},"Polyhedron"]

Bilateral

GraphData[{"Haar",631},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",631},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",631},"Planar"]

GraphData[{"Haar",631},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",631},{"RCN","CN"}]

GraphData[{"Haar",631},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",631}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",631}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",631},"Circulant"]

GraphData[{"Haar",631},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",631},"Line"]

LineGraphQ[GraphData[{"Haar",631}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",631}&]

RootGraph[GraphData[{"Haar",631}]]

Halin

GraphData[{"Haar",631},"Halin"]

GraphData[{"Haar",631},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",631},"Rigid"]

GraphData[{"Haar",631},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",631},"Flexible"]

GraphData[{"Haar",631},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",631},"LCF"]

GraphData[{"Haar",631},"HamiltonianCycleCount"]

GraphData[{"Haar",631},"LCFSignature"]

GraphData[{"Haar",631},"LCFNotations"]

GraphData[{"Haar",631},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Haar",631}],TimeConstraint->120]

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Haar",631}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute 5*^7

Tally[(lcf=LCF[GraphData[{"Haar",631}],5*^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

gs=Select[{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,},LCFNotation[#][[-1]]>2&]

Length[gs]

LCFNotation/@gs

nice={{{{-9,-7,-5,3,5},{-5,-3,5,7,9}},10},{{{-9,-7,-5,3,9},{-9,-3,5,7,9}},10},{{{-9,-7,-3,3,9},{-9,-3,3,7,9}},10},{{{-9,-7,-3,7,9},{-9,-7,3,7,9}},10},{{{-9,-7,3,5,9},{-9,-5,-3,7,9}},10},{{{-9,-5,-3,5,7},{-7,-5,3,5,9}},10},{{{-9,-5,-3,5,9},{-9,-5,3,5,9}},10}};

gs=LCFGraph@@@nice

LCFGraph@@@nice

RecognizeGraph/@%

l={{{"Haar",631},{0,Missing["NotAvailable",nice]}}}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",631}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

With[{debug=True},
ComputeLCF[
If[debug,Print[#]];
#,
"Prune"->False,
Method->"FindPath",
"ChunkSize"->10*^6,
Debug->debug
]
]&/@{{"Haar",631}};

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

DeleteCases[lcf,{_,1|2}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@%

UnitDistance

GraphData[{"Haar",631},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",631}],Debug->True]//Timing

GraphData[{"Haar",631},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",631},"VertexList"],GraphData[{"Haar",631},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",631}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",631},"Matchstick"]

GraphData[{"Haar",631},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",631},"Edges"]]

3D All

GraphData[{"Haar",631},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",631},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",631},"Polyhedral"]

GraphData[{"Haar",631},"Graph",{"3D","Polyhedron"}]

{"Haar", 683}

Names

GraphData[{"Haar",683},"StandardName"]

GraphData[{"Haar",683},"StandardNames"]

Primary

GraphData[{"Haar",683}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",683},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",683},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",683},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",683},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",683},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",683},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",683},"Polyhedron"]

Bilateral

GraphData[{"Haar",683},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",683},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",683},"Planar"]

GraphData[{"Haar",683},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",683},{"RCN","CN"}]

GraphData[{"Haar",683},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",683}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",683}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",683},"Circulant"]

GraphData[{"Haar",683},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",683},"Line"]

LineGraphQ[GraphData[{"Haar",683}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",683}&]

RootGraph[GraphData[{"Haar",683}]]

Halin

GraphData[{"Haar",683},"Halin"]

GraphData[{"Haar",683},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",683},"Rigid"]

GraphData[{"Haar",683},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",683},"Flexible"]

GraphData[{"Haar",683},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",683},"LCF"]

GraphData[{"Haar",683},"HamiltonianCycleCount"]

GraphData[{"Haar",683},"LCFSignature"]

GraphData[{"Haar",683},"LCFNotations"]

GraphData[{"Haar",683},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",683}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

lcf={{{{-9,-5,3,7},{-7,-3,5,9}},10},{{{-9,-7,-5,-3},{-7,-5,-3,9},{-9,-7,-5,-3},{3,5,7,9},{-9,3,5,7},{3,5,7,9},{-9,-3,3,5},{-3,3,5,9},{-9,-5,-3,3},{-5,-3,3,9}},2},{{{-9,-7,-5,-3},{-7,-5,-3,9},{-9,-7,-5,-3},{3,5,7,9},{-9,3,5,7},{3,5,7,9},{-7,-3,3,5},{-9,-3,3,5},{-5,-3,3,9},{-5,-3,3,7}},2},{{{-9,-7,-5,-3},{-7,-5,-3,9},{-9,-7,-5,-3},{3,5,7,9},{-7,3,5,7},{-9,3,5,7},{-3,3,5,9},{-3,3,5,7},{-9,-5,-3,3},{-5,-3,3,9}},2},{{{-9,-7,-5,-3},{-7,-5,-3,9},{-9,-7,-5,-3},{3,5,7,9},{-7,3,5,7},{-7,3,5,7},{-7,-3,3,5},{-3,3,5,7},{-5,-3,3,7},{-5,-3,3,7}},2},{{{-9,-7,-5,-3},{-7,-5,-3,9},{-9,-7,-5,-3},{3,5,7,9},{-5,3,5,7},{-9,3,5,7},{-3,3,5,9},{-9,-3,3,5},{-5,-3,3,9},{-5,-3,3,5}},2},{{{-9,-7,-5,-3},{-7,-5,-3,9},{-9,-7,-5,-3},{3,5,7,9},{-5,3,5,7},{-7,3,5,7},{-9,-3,3,5},{-3,3,5,9},{-5,-3,3,7},{-5,-3,3,5}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-9,3,5,7},{3,5,7,9},{-9,-3,3,5},{-3,3,5,9},{-7,-5,-3,3},{-9,-5,-3,3},{-7,-5,-3,9},{-7,-5,-3,7}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-9,3,5,7},{3,5,7,9},{-7,-3,3,5},{-7,-3,3,5},{-7,-5,-3,3},{-5,-3,3,7},{-7,-5,-3,7},{-7,-5,-3,7}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-9,3,5,7},{3,5,7,9},{-5,-3,3,5},{-9,-3,3,5},{-5,-3,3,9},{-9,-5,-3,3},{-7,-5,-3,9},{-7,-5,-3,5}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-9,3,5,7},{3,5,7,9},{-5,-3,3,5},{-7,-3,3,5},{-9,-5,-3,3},{-5,-3,3,9},{-7,-5,-3,7},{-7,-5,-3,5}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-7,3,5,7},{-9,3,5,7},{-3,3,5,9},{-3,3,5,7},{-7,-5,-3,3},{-9,-5,-3,3},{-7,-5,-3,9},{-7,-5,-3,7}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-7,3,5,7},{-7,3,5,7},{-5,-3,3,5},{-3,3,5,7},{-5,-3,3,7},{-9,-5,-3,3},{-7,-5,-3,9},{-7,-5,-3,5}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-7,3,5,7},{-5,3,5,7},{-7,-3,3,5},{-3,3,5,7},{-7,-5,-3,3},{-5,-3,3,7},{-7,-5,-3,5},{-7,-5,-3,7}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-7,3,5,7},{-5,3,5,7},{-5,-3,3,5},{-3,3,5,7},{-9,-5,-3,3},{-5,-3,3,9},{-7,-5,-3,5},{-7,-5,-3,5}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-5,3,5,7},{-9,3,5,7},{-3,3,5,9},{-7,-3,3,5},{-7,-5,-3,3},{-5,-3,3,5},{-7,-5,-3,7},{-7,-5,-3,7}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-5,3,5,7},{-7,3,5,7},{-5,-3,3,5},{-7,-3,3,5},{-5,-3,3,7},{-5,-3,3,5},{-7,-5,-3,7},{-7,-5,-3,5}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-5,3,5,7},{-5,3,5,7},{-9,-3,3,5},{-3,3,5,9},{-7,-5,-3,3},{-5,-3,3,5},{-7,-5,-3,5},{-7,-5,-3,7}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-5,3,5,7},{-5,3,5,7},{-5,-3,3,5},{-9,-3,3,5},{-5,-3,3,9},{-5,-3,3,5},{-7,-5,-3,5},{-7,-5,-3,5}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-3,3,5,7},{-9,3,5,7},{-3,3,5,9},{-9,-3,3,5},{-5,-3,3,9},{-9,-5,-3,3},{-7,-5,-3,9},{-7,-5,-3,3}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-3,3,5,7},{-9,3,5,7},{-3,3,5,9},{-7,-3,3,5},{-9,-5,-3,3},{-5,-3,3,9},{-7,-5,-3,7},{-7,-5,-3,3}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-3,3,5,7},{-7,3,5,7},{-9,-3,3,5},{-3,3,5,9},{-5,-3,3,7},{-9,-5,-3,3},{-7,-5,-3,9},{-7,-5,-3,3}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-3,3,5,7},{-7,3,5,7},{-7,-3,3,5},{-7,-3,3,5},{-5,-3,3,7},{-5,-3,3,7},{-7,-5,-3,7},{-7,-5,-3,3}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-3,3,5,7},{-5,3,5,7},{-9,-3,3,5},{-3,3,5,9},{-9,-5,-3,3},{-5,-3,3,9},{-7,-5,-3,5},{-7,-5,-3,3}},2},{{{-9,-7,-5,-3},{3,5,7,9},{-3,3,5,7},{-5,3,5,7},{-7,-3,3,5},{-9,-3,3,5},{-5,-3,3,9},{-5,-3,3,7},{-7,-5,-3,5},{-7,-5,-3,3}},2},{{{-9,-7,-5,7},{-7,-5,7,9},{-9,-7,-3,5},{-5,3,7,9},{-9,-7,5,7},{-7,5,7,9},{-9,-3,3,5},{-7,-5,7,9},{-9,-7,5,7},{-5,-3,3,9}},2},{{{-9,-7,-5,7},{-7,-3,5,9},{-9,-7,-3,5},{-7,5,7,9},{-7,-5,5,7},{-9,3,5,7},{-7,-5,7,9},{-9,-7,-5,7},{-5,-3,3,9},{-5,3,5,7}},2},{{{-9,-7,-5,7},{-7,5,7,9},{-9,-7,-3,5},{-7,-5,7,9},{-7,3,5,7},{-9,-7,5,7},{-7,-5,7,9},{-7,-5,-3,7},{-9,-7,5,7},{-5,3,7,9}},2},{{{-9,-7,-5,7},{-5,-3,3,9},{-9,-5,3,7},{-7,-5,7,9},{-7,-3,3,5},{-9,-7,-3,5},{-7,5,7,9},{-7,-3,5,7},{-9,3,5,7},{-7,-5,7,9}},2},{{{-9,-7,-5,7},{-5,3,7,9},{-9,-5,3,7},{-7,5,7,9},{-7,-5,-3,5},{-9,-3,3,5},{-7,5,7,9},{-9,-7,5,7},{-7,-5,-3,9},{-7,-5,5,7}},2},{{{-9,-7,-5,7},{-5,3,7,9},{-5,-3,3,7},{-9,-7,5,7},{-7,-3,5,9},{-9,-3,3,5},{-7,5,7,9},{-9,-7,5,7},{-7,-5,-3,9},{-7,-5,3,7}},2},{{{-9,-7,-5,7},{-3,3,5,9},{-9,-5,3,7},{-5,3,7,9},{-9,-7,-3,5},{-7,-3,5,9},{-9,-5,-3,3},{-7,5,7,9},{-9,3,5,7},{-7,-5,-3,9}},2},{{{-9,-7,-5,7},{-3,3,5,9},{-7,-5,3,7},{-9,-5,3,7},{-7,-3,5,9},{-7,-3,5,7},{-9,-5,-3,3},{-7,5,7,9},{-9,3,5,7},{-7,-5,-3,9}},2},{{{-9,-7,-3,5},{-7,-5,7,9},{-7,-3,5,7},{-9,-7,5,7},{-7,-5,7,9},{-7,-5,3,7},{-9,-7,5,7},{-5,3,7,9},{-7,-5,-3,7},{-7,3,5,7}},2},{{{-9,-7,-3,5},{-5,3,7,9},{-7,-3,5,7},{-7,-5,5,7},{-9,-3,3,5},{-7,-5,7,9},{-9,-7,5,7},{-5,-3,3,9},{-7,-5,5,7},{-7,-5,3,7}},2}};

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",683},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",683}],Debug->True]//Timing

GraphData[{"Haar",683},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",683},"VertexList"],GraphData[{"Haar",683},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",683}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",683},"Matchstick"]

GraphData[{"Haar",683},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",683},"Edges"]]

3D All

GraphData[{"Haar",683},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",683},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",683},"Polyhedral"]

GraphData[{"Haar",683},"Graph",{"3D","Polyhedron"}]

{"Haar", 687}

Names

GraphData[{"Haar",687},"StandardName"]

GraphData[{"Haar",687},"StandardNames"]

Primary

GraphData[{"Haar",687}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",687},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",687},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",687},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",687},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",687},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",687},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",687},"Polyhedron"]

Bilateral

GraphData[{"Haar",687},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",687},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",687},"Planar"]

GraphData[{"Haar",687},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",687},{"RCN","CN"}]

GraphData[{"Haar",687},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",687}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",687}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",687},"Circulant"]

GraphData[{"Haar",687},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",687},"Line"]

LineGraphQ[GraphData[{"Haar",687}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",687}&]

RootGraph[GraphData[{"Haar",687}]]

Halin

GraphData[{"Haar",687},"Halin"]

GraphData[{"Haar",687},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",687},"Rigid"]

GraphData[{"Haar",687},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",687},"Flexible"]

GraphData[{"Haar",687},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",687},"LCF"]

GraphData[{"Haar",687},"HamiltonianCycleCount"]

GraphData[{"Haar",687},"LCFSignature"]

GraphData[{"Haar",687},"LCFNotations"]

GraphData[{"Haar",687},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Haar",687}],TimeConstraint->120]

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Haar",687}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

nicelcf=DeleteCases[lcf,{_,1|2}]

l={{{"Haar",687},{0,Missing["NotAvailable",nicelcf]}}}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

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

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

Length[gs]

gs

LCF compute 5*^7

Tally[(lcf=LCF[GraphData[{"Haar",687}],5*^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

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

Length[gs]

gs

nicelcf=LCFNotation/@gs

l={{{"Haar",687},{0,Missing["NotAvailable",nicelcf]}}}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",687}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1|2}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Haar",687},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",687}],Debug->True]//Timing

GraphData[{"Haar",687},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",687},"VertexList"],GraphData[{"Haar",687},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",687}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",687},"Matchstick"]

GraphData[{"Haar",687},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",687},"Edges"]]

3D All

GraphData[{"Haar",687},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",687},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",687},"Polyhedral"]

GraphData[{"Haar",687},"Graph",{"3D","Polyhedron"}]

{"Haar", 703}

Names

GraphData[{"Haar",703},"StandardName"]

GraphData[{"Haar",703},"StandardNames"]

Primary

GraphData[{"Haar",703}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",703},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",703},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",703},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",703},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",703},"Graph","Degenerate"]

Perspective

GraphData[{"Haar",703},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",703},"Polyhedron"]

Bilateral

GraphData[{"Haar",703},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",703},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",703},"Planar"]

GraphData[{"Haar",703},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",703},{"RCN","CN"}]

GraphData[{"Haar",703},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",703}],TimeConstraint->1])//AbsoluteTiming

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

(g=MinimalCrossingGraph[GraphData[{"Haar",703}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",703},"Circulant"]

GraphData[{"Haar",703},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",703},"Line"]

LineGraphQ[GraphData[{"Haar",703}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",703}&]

RootGraph[GraphData[{"Haar",703}]]

Halin

GraphData[{"Haar",703},"Halin"]

GraphData[{"Haar",703},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",703},"Rigid"]

GraphData[{"Haar",703},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",703},"Flexible"]

GraphData[{"Haar",703},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",703},"LCF"]

GraphData[{"Haar",703},"HamiltonianCycleCount"]

GraphData[{"Haar",703},"LCFSignature"]

GraphData[{"Haar",703},"LCFNotations"]

GraphData[{"Haar",703},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Haar",703}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Haar",703}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute 10^6

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Haar",703}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

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

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

Length[gs]

gs

LCF compute 5*^7

Tally[(lcf=LCF[GraphData[{"Haar",703}],5*^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1|2}]

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

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

Length[gs]

gs

LCFNotation/@gs

l={{{"Haar",703},{0,Missing["NotAvailable",nicelcf]}}}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Length[FindHamiltonianCycle[GraphData[{"Haar",703}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData[{"Haar",703},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",703}],Debug->True]//Timing

GraphData[{"Haar",703},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",703},"VertexList"],GraphData[{"Haar",703},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",703}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"Haar",703},"Matchstick"]

GraphData[{"Haar",703},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",703},"Edges"]]

3D All

GraphData[{"Haar",703},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",703},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",703},"Polyhedral"]

GraphData[{"Haar",703},"Graph",{"3D","Polyhedron"}]

{"Haar", 536870930}

Names

GraphData[{"Haar",536870930},"StandardName"]

GraphData[{"Haar",536870930},"StandardNames"]

Primary

GraphData[{"Haar",536870930}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Haar",536870930},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Haar",536870930},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Haar",536870930},"Edges"]

HoneycombToroidalGraph[2,30,8]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Haar",536870930},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Haar",536870930},"Graph","Degenerate"]

Configuration

GraphData[{"Haar",536870930},"Configuration"]

GraphData[{"Haar",536870930},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Haar",536870930},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Haar",536870930},"Polyhedron"]

HoneycombToroidal construction

GraphData[{"Haar",536870930},"NotationRules","HoneycombToroidal"]

g=HoneycombToroidalGraph[2,30,8]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=60},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Haar",536870930}}]]//Timing

gs=GeneralizedHoneycombGraph[60,#]&/@{5,9}

RecognizeGraph/@gs

GeneralizedPetersen

GraphData[{"Haar",536870930},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Haar",536870930},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Haar",536870930},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Haar",536870930},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Haar",536870930},"Planar"]

GraphData[{"Haar",536870930},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Haar",536870930},{"RCN","CN"}]

GraphData[{"Haar",536870930},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Haar",536870930}],TimeConstraint->1])//AbsoluteTiming

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

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

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

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

(g=MinimalCrossingGraph[GraphData[{"Haar",536870930}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Haar",536870930},"Circulant"]

GraphData[{"Haar",536870930},"Graph","Circulant"]//StyleGraphs

Line graph

GraphData[{"Haar",536870930},"Line"]

LineGraphQ[GraphData[{"Haar",536870930}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Haar",536870930}&]

RootGraph[GraphData[{"Haar",536870930}]]

Halin

GraphData[{"Haar",536870930},"Halin"]

GraphData[{"Haar",536870930},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Haar",536870930},"Rigid"]

GraphData[{"Haar",536870930},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Haar",536870930},"Flexible"]

GraphData[{"Haar",536870930},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Haar",536870930},"LCF"]

GraphData[{"Haar",536870930},"HamiltonianCycleCount"]

GraphData[{"Haar",536870930},"LCFSignature"]

GraphData[{"Haar",536870930},"LCFNotations"]

GraphData[{"Haar",536870930},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Divisors[GraphData[{"Haar",536870930},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Haar",536870930}],All][[All,All,1]]]//Timing

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Haar",536870930},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Haar",536870930}],Debug->True]//Timing

GraphData[{"Haar",536870930},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Haar",536870930},"VertexList"],GraphData[{"Haar",536870930},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

gs=LabelGraph/@{,}

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Haar",536870930}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Haar",536870930},"Matchstick"]

GraphData[{"Haar",536870930},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Haar",536870930},"Edges"]]

3D All

GraphData[{"Haar",536870930},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Haar",536870930},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Haar",536870930},"Polyhedral"]

GraphData[{"Haar",536870930},"Graph",{"3D","Polyhedron"}]

Classes

GraphClassesThatAreClass["Haar"]

Intersection@@GraphData["Haar","Classes"]

Pisanski, T. and Randic, M.  "Bridges between Geometry and Graph Theory."  In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C.A.Gorini).  Washington, DC: Math. Assoc. Amer., pp. 174–194, 2000.

Sort[Normal[GroupBy[GraphData["Haar"],GraphData[#,"Girth"]&]]]

Parametrized families

Alkane

seq=Table[GraphData[{"Alkane",n},"Haar"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"Haar"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"Haar"],{n,10}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"Haar"],{n,15}]

Antiprism

Entity["Graph",{"Antiprism",n}]["Haar"]

seq=Table[GraphData[{"Antiprism",n},"Haar"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"Haar"],{n,5}]

Barbell

seq=Table[GraphData[{"Barbell",n},"Haar"],{n,3,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"Haar"],{n,10}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"Haar"],{n,10}]

Book

seq=Table[GraphData[{"Book",n},"Haar"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"Haar"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"Haar"],{n,10}]

Centipede

seq=Table[GraphData[{"Centipede",n},"Haar"],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"Haar"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["Haar"]

seq=Table[GraphData[{"Complete",n},"Haar"],{n,30}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["Haar"]

Sort[GraphData[#,"NotationRules","CompleteBipartite"]&@@@DeleteCases[{#,GraphData[#,"Haar"]}&/@GraphData["CompleteBipartite"],{_,False}]]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["Haar"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"Haar"],{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["Haar"]

DeleteCases[{#,GraphData[#,"Haar"]}&/@GraphData["CompleteTripartite"],{_,False}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["Haar"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"Haar"],{n,10}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"Haar"],{n,2,10}]

Crown

seq=Table[GraphData[{"Crown",n},"Haar"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["Haar"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"Haar"],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["Haar"]

seq=Table[GraphData[{"Cycle",n},"Haar"],{n,3,30}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"Haar"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"Haar"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"Haar"],{n,3,20}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"Haar"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["Haar"]

seq=Table[GraphData[{"Empty",n},"Haar"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"Haar"],{n,15}]

Flower

seq=Table[GraphData[{"Flower",n},"Haar"],{n,5,20}]

FoldedCube

Inferred for n == 10:

seq=Table[GraphData[{"FoldedCube",n},"Haar"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"Haar"],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"Haar"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"Haar"],{n,3,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["Haar"]

DeleteCases[Sort@Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"Haar"]
},{n,10},{m,n}],1],{_,False}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["Haar"]

seq=Table[GraphData[{"Grid",{n,n}},"Haar"],{n,20}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["Haar"]

DeleteCases[Sort@Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"Haar"]
},{n,5},{m,n},{k,m}],2],{_,False}]

Tally[GraphData[{"Grid",{2,3,4}},"DistanceMatrix"]//Normal//Flatten]

Select[Flatten[Table[{k,m,n},{n,10},{m,10},{k,10}],2],Max@@#==2&]

Union[Sort/@%]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["Haar"]

seq=Table[GraphData[{"Grid",{n,n,n}},"Haar"],{n,10}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"Haar"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"Haar"],{n,5}]

Helm

seq=Table[GraphData[{"Helm",n},"Haar"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["Haar"]

Inferred for n > 8:

seq=Table[GraphData[{"Hypercube",n},"Haar"],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["Haar"]

seq=Table[GraphData[{"Keller",n},"Haar"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"Haar"],{n,20}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["Haar"]

DeleteCases[{#,GraphData[#,"Haar"]}&/@GraphData["Knight"],{_,False}]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["Haar"]

seq=Table[GraphData[{"Knight",{n,n}},"Haar"],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["Haar"]

seq=Table[GraphData[{"Ladder",n},"Haar"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"Haar"],{n,20}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"Haar"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["Haar"]

seq=Table[GraphData[{"MoebiusLadder",n},"Haar"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["Haar"]

seq=Table[GraphData[{"Mycielski",n},"Haar"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["Haar"]

seq=Table[GraphData[{"Odd",n},"Haar"],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"Haar"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["Haar"]

seq=Table[GraphData[{"Path",n},"Haar"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"Haar"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["Haar"]

seq=Table[GraphData[{"Prism",n},"Haar"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"Haar"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"Haar"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"Haar"],{n,10}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"Haar"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"Haar"],{n,5}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"Haar"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"Haar"],{n,5}]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"Haar"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"Haar"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["Haar"]

seq=Table[GraphData[{"Star",n},"Haar"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"Haar"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"Haar"],{n,3,20}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"Haar"],{n,3,10}]

Transposition

Entity["Graph",{"Transposition",n}]["Haar"]

seq=Table[GraphData[{"Transposition",n},"Haar"],{n,6}]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["Haar"]

seq=Table[GraphData[{"Trapezohedron",n},"Haar"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"Haar"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"Haar"],{n,0,10}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"Haar"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"Haar"],{n,9}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"Haar"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"Haar"],{n,10}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"Haar"],{n,10}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"Haar"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"Haar"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["Haar"]

seq=Table[GraphData[{"Wheel",n},"Haar"],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"Haar"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"Haar"],{n,2,10}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"Haar"],{n,20}]

Node count of (Subscript[H, n])

Table[(2^(n-1)),{n,10}]

split=Split[VertexCount/@Table[HaarGraph[n],{n,100}]]

Length/@split

Accumulate[%]

LogLogPlot[2Floor[1+Log2[n]],{n,1,10^10},PlotRange->All,PlotLabels->{n,Abs[Subscript[H,n]]}]

Plot[2Floor[1+Log2[n]],{n,1,10^10},PlotRange->All]

2Floor[1+Log2[10^10.]]

Table[MinValue[{n,k==2Floor[1+Log2[n]]},n],{k,2,20,2}]

Plot[2Floor[1+Log2[n]],{n,1,20},PlotRange->All]

nmin=MinValue[{n,62==2Floor[1+Log2[n]]},n]

Table[2Floor[1+Log2[nmin+n]],{n,-1,0}]

{#,GraphData[#,"V"],"Haar"/.GraphData[#,"NotationRules"]}&/@GraphData["Haar",;;10]//Column

Sum[2^k,{k,0,n}]

Solve[-1+(2^(1+n))==k,n]

2Table[Ceiling[Log2[k+1]],{k,20}]

2(1+Table[Floor[Log2[k]],{k,20}])

DeleteCases[{#,h="Haar"/.GraphData[#,"NotationRules"],GraphData[#,"V"],2Ceiling[Log2[h+1]]}&/@GraphData["Haar"],{_,_,x_,x_}]

DeleteCases[{#,h="Haar"/.GraphData[#,"NotationRules"],GraphData[#,"V"],2+2Floor[Log2[h]]}&/@GraphData["Haar"],{_,_,x_,x_}]

Isomorphic

Hladnik et al. 2002

TextGrid[
Drop[
DeleteCases[SortBy[Function[g,With[{haars=Cases[GraphData[g,"StandardNames"],{"Haar",n_}:>n]},
{
g,
If[haars==={},{},First@haars],
Length@haars,
Union[EulerPhi[IntegerLength[#,2]]DigitCount[#,2,1]&/@haars]
}]]/@GraphData["Haar"],#[[2]]&],{_,{},__}],-2],Dividers->All,Alignment->{{Left,{Decimal}}}]

Table

Grid[{#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[Table[{RecognizeGraph[HaarGraph[n]],n},{n,1000}],Flatten[{#}][[1]]&],First],Dividers->All,Alignment->Left]

Reconstruction

Description

Pisanski, T. and Randic, M.  "Bridges between Geometry and Graph Theory."  In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C.A.Gorini).  Washington, DC: Math. Assoc. Amer., pp. 174–194, 2000.

HaarGraph[69]//RecognizeGraph

Stuff

HaarGraph[n_Integer?Positive]:=Module[{l=IntegerDigits[n,2],m},m=Length[l];
Graph[Range[m],UndirectedEdge@@@((#+{0,m})&/@Position[NestList[RotateRight,l,m-1],1])]]

HaarAutomorphismQ[g_Graph,Cycles[cyc_]]:=Module[{len=Length/@cyc,n=VertexCount[g]},And[Length[cyc]==2,Equal@@len,Total[len]==n,AllTrue[cyc,IndependentVertexSetQ[g,#]&]]]

HaarPermutations[g_Graph]:=Module[{},
Select[GroupElements[GraphAutomorphismGroup[g]],HaarAutomorphismQ[g,#]&]
]

HaarGraph[69]//RecognizeGraph

l=IntegerDigits[69,2]

perms=HaarPermutations[GraphData["HeawoodGraph"]]

List@@@EdgeList[GraphData["HeawoodGraph"]]

perms[[1]]

perm=PermutationList[Cycles[{{1,3,5,7,9,11,13},{2,4,6,8,10,12,14}}]]

l=NestList[Permute[#,perm]&,Range[14],7]

Union[Sort/@Join@@(Thread/@Partition[l,2,1])]

Thread[{Range[14],%}]

Length[%142]

GraphData["HeawoodGraph","EdgeList"]

Length[%]

?Permute

Permute[{3,4,5,6,7,8,9,10,11,12,13,14,1,2},]

GroupOrbits[PermutationGroup[{perms[[1]]}],{1\[UndirectedEdge]8}]

GroupOrbits[PermutationGroup[{perms[[1]]}],Range[7]]

RecognizeGraph@%

m=Length[%]

NestList[RotateRight,l,m-1]

Position[%,1]

(#+{0,m})&/@%135

(#-{0,5})&/@{{1,6},{1,9},{1,10},{2,6},{2,7},{2,10},{3,6},{3,7},{3,8},{4,7},{4,8},{4,9},{5,8},{5,9},{5,10}}

a=SparseArray[Thread[%->1]]

Normal[a][[1]]

Q2

GraphData["Q2","IndependentEdgeSets"]

GraphData["Q2","Edges","List"]

GraphData["Q2","NotationRules","Haar"]

IntegerDigits[3,2]

l=IntegerDigits[3,2]

m=Length[l]

NestList[RotateRight,l,m-1]

Position[%,1]

(#+{0,m})&/@%

HaarPermutation[GraphData["Q2"]]

Q3

FindIndependentVertexSet[GraphData["Q3"],{4},All]

GraphData["Q3","Edges","List"]

i=(#+{0,-4})&/@{{1,2},{1,3},{1,5},{2,4},{2,6},{3,4},{3,7},{4,8},{5,6},{5,7},{6,8},{7,8}}

SparseArray[Thread[i->1]]//MatrixForm

GraphData["Q3","NotationRules","Haar"]

l=IntegerDigits[11,2]

m=Length[l]

NestList[RotateRight,l,m-1]

Position[%,1]

(#+{0,m})&/@%

FromDigits[#,2]&/@%169

Cases[GraphData["Q3","StandardNames"],{"Haar",n_}:>n]

HaarPermutations[GraphData["Q3"]]

PermutationList/@%179

PermutationList[Cycles[{{1,4,7,6},{2,3,8,5}}]]

Transpose[{{1,4,7,6},{2,3,8,5}}]

RotateLeft[NestList[RotateRight,l,m-1]]

Position[%,1]

(#+{0,m})&/@%

Graph[UndirectedEdge@@@%241]//RecognizeGraph

M7

GraphData["M7","NotationRules","Haar"]

l=IntegerDigits[67,2]

m=Length[l]

NestList[RotateRight,l,m-1]

FromDigits[#,2]&/@%

Cases[GraphData["M7","StandardNames"],{"Haar",n_}:>n]

Index properties

File

Length[haars=ToExpression/@Import[FileNameJoin[{$GraphDataDirectory,"Catalogs","Haar.txt"}],"Lines"]]

SelectFirst[Partition[Union[haars[[All,1]]],2,1],Subtract@@#=!=-1&]

So Haar's are complete in GraphData up to 1024

Connected

A graph is connected if there is a path between any two of its vertices.  n is  connected if the corresponding Haar graph H(n) is connected.

A291166

(seq=Select[Range[100],ConnectedGraphQ[HaarGraph[#]]&])//Timing

FindSequenceFunction[seq,n]

gf=FindGeneratingFunction[seq,x]

Disconnected

A291165

(seq=Select[Range[5*^3],!ConnectedGraphQ[HaarGraph[#]]&])//Timing

Includes (2^n)

Log2[Last[seq]]

Complement[seq,2^Range[12]]

FindSequenceFunction[seq,n]

gf=FindGeneratingFunction[seq,x]

Smallest giving a new Haar

Monitor[hashes={Hash[CanonicalGraph[HaarGraph[#]]],n=#}&/@Range[1023],n];//Timing

A137706

Sort[SplitBy[Sort[Sort[hashes]],First][[All,1,2]]]

Take[all=SortBy[SplitBy[SortBy[Select[haars,#[[1]]<1025&],Last],Last],#[[1,1]]&],20]

all[[All,1,1]]

Haar equivalent

haarequiv=SortBy[Select[SplitBy[Sort[hashes],First],Length[#]>1&][[All,All,2]],First]

Select[all,Length[#]>1&][[All,All,1]]

Uniquely index a Haar graph

A272919

Complement[Range[1023],Flatten[haarequiv]]

Log2[1024]

Flatten@Table[d=Reverse@Divisors[n];2^(d-1)(2^n-1)/(2^d-1),{n,10}]

Select[all,Length[#]==1&][[All,1,1]]

Cyclically equivalent

The numbers n and m are cyclically equivalent if the binary string of the first number can be cyclically transformed to the binary string of the second number. This means that the string can be cyclically permuted, mirrored or multiplied by a number relatively prime with the string length

Divisors[10]

IntegerDigits[10,2]

Complement[Range[15],Divisors[10]]

CyclicVariants[n_]:=Module[{b=IntegerDigits[n,2],len},
len=Length[b];
relprime=Complement[Range[len],Divisors[len]];
cyclics=Partition[b,len,1,1];
Union[
FromDigits[#,2]&/@DeleteCases[cyclics,{0,__}],
FromDigits[#,2]&/@Reverse/@DeleteCases[cyclics,{__,0}],
Select[n relprime,#<(2^len)&]
]
]

CyclicVariants[137331]

RotateLeft@IntegerDigits[536870930,2]

DeleteCases[cyclics,{0,__}]

FromDigits[#,2]&/@%

Reverse/@DeleteCases[cyclics,{__,0}]

FromDigits[#,2]&/@%

Select[%109,OddQ]

CyclicVariants[536870930]

Select[%,OddQ]

Select[Range[100],EvenQ/@And@@CyclicVariants[#]&]

Select[Range[100],ConnectedGraphQ[HaarGraph[#]]&&EvenQ/@And@@CyclicVariants[#]&]

CyclicVariants[18]

IntegerDigits[18,2]

IntegerDigits[20,2]

Special classes

Accordion

Sort[GraphData[#,"NotationRules","Accordion"]&/@Select[GraphData["Accordion"],GraphData[#,"Haar"]===True&]]

Sort[GraphData[#,"NotationRules","Accordion"]&/@Select[GraphData["Accordion"],GraphData[#,"Haar"]=!=True&]]

Cases[%43,{_?EvenQ,_?EvenQ}]

Circulant

Hladnika et al. 2002

Proposition 4.6. A circulant is a cyclic Haar graph if and only if it is bipartite.

Complement[GraphData[{"Circulant","Haar"}],GraphData[{"Circulant","Bipartite"}]]

Complement[GraphData[{"Circulant","Bipartite"}],GraphData[{"Circulant","Haar"}]]

Complement[GraphData[{"Circulant","Haar","Nonempty"}],GraphData[{"Circulant","Bipartite"}]]

CompleteBipartite

{GraphData[#,"#"],Last[#]}&/@Sort[Cases[GraphData[#,"StandardNames"]&/@GraphData[{"Haar","CompleteBipartite"}],{"Haar",_},2]]

Last/@%

Table[2^n-1,{n,16}]

Table[{{"CompleteBipartite",n},2^n-1},{n,20}]

CrossedPrism

{GraphData[#,"#"],Last[#]}&/@Sort[Cases[GraphData[#,"StandardNames"]&/@GraphData[{"Haar","CrossedPrism"}],{"Haar",_},2]]

Last/@%

{11,37,137,529,2081,8257,32897}-3

HaarGraph[32897]//RecognizeGraph

HaarGraph[131329]//RecognizeGraph

Table[{{"CrossedPrism",2n},2^(2n-1)+2^(n-1)+1},{n,10}]

Crown

{GraphData[#,"#"],Last[#]}&/@Sort[Cases[GraphData[#,"StandardNames"]&/@GraphData[{"Haar","Crown"}],{"Haar",_},2]]

Table[3 2^(n-2)-1,{n,20}]

Table[{n,3 2^(n-2)-1},{n,20}]

Cycle

{GraphData[#,"#"],Last[#]}&/@Sort[Cases[GraphData[#,"StandardNames"]&/@GraphData[{"Haar","Cycle"}],{"Haar",_},2]]

Table[{2n,2^(n-1)+1},{n,2,10}]

Table[2^(n-1)+1,{n,2,10}]

HoneycombToroidal

Select[GraphData["HoneycombToroidal"],GraphData[#,"Haar"]=!=True&]

GraphData[#,"NotationRules","HoneycombToroidal"]&/@%

Knoedel

Select[GraphData["Knoedel"],GraphData[#,"Haar"]=!=True&]

knoedel=Sort[{GraphData[#,"NotationRules","Knoedel"],GraphData[#,"NotationRules","Haar"]}&/@GraphData[{"Haar","Knoedel"}]]

Cases[knoedel,{{1,k_},n_}:>{k,n}]

Table[(2^(n/2-1)),{n,2,10,2}]

Cases[knoedel,{{2,k_},n_}:>{k,n}]

seq=%[[All,2]]

FindSequenceFunction[seq,n]

Cases[knoedel,{{3,k_},n_}:>{k,n}]

seq=%[[All,2]]

Table[(2^n)+5,{n,10}]

LadderRung

{GraphData[#,"#"],Last[#]}&/@Sort[Cases[GraphData[#,"StandardNames"]&/@GraphData[{"Haar","LadderRung"}],{"Haar",_},2]]

Table[{n,2^(n-1)},{n,10}]

Table[2^(n-1),{n,10}]

MoebiusLadder

{GraphData[#,"#"],Last[#]}&/@Sort[Cases[GraphData[#,"StandardNames"]&/@GraphData[{"Haar","MoebiusLadder"}],{"Haar",_},2]]

Table[{2n+1,2^(2n)+3},{n,10}]

Table[2^(2n)+3,{n,10}]

Prism

{GraphData[#,"#"],Last[#]}&/@Sort[Cases[GraphData[#,"StandardNames"]&/@GraphData[{"Haar","Prism"}],{"Haar",_},2]]

Last/@%

Table[{2n,2^(2n-1)+3},{n,10}]

nQ3

GraphData["*Q3"]

Table[GraphData[If[n==1,"",ToString[n]]<>"Q3","NotationRules","Haar"],{n,5}]

seq={11,138,2084,32904,524816};

FindSequenceFunction[DeleteMissing[seq],n]

FindGeneratingFunction[seq,x]

Table[16^n/2,{n,5}]

seq-%

Table[16^n/2+2^(n-1)*(1+2^n),{n,5}]

FullSimplify[16^n/2+2^(n-1)*(1+2^n)]

Table[(2^(-1+n)) (1+(2^n)+(8^n)),{n,10}]

TorusGrid

Select[GraphData[{"Bipartite","TorusGrid"}],GraphData[#,"Haar"]=!=True&]

{GraphData[#,"#"],Last[#]}&/@Sort[Cases[GraphData[#,"StandardNames"]&/@GraphData[{"Haar","TorusGrid"}],{"Haar",_},2]]

GraphData[{"Haar","TorusGrid"}]

Table[{2n+1,2^(2n)+3},{n,10}]

Table[2^(2n)+3,{n,10}]

ZeroTwoBipartite

Select[GraphData[{"Bipartite","ZeroTwo"}],GraphData[#,"Haar"]=!=True&]

Special cases

Hladnik, M.; Maru\v si\v c, D.; and Pisanski, T.  ``Cyclic Haar Graphs.’’  {\it Disc.\ Math.} {\bf 244}, 137--153, 2002.

TwoSquares

n=GraphData[g="TwoSquares","V"]

Select[Range[(2^(n/2-1)),(2^(n/2))],RecognizeGraph[HaarGraph[#]]===g&]

TwoHexagons

n=GraphData[g="TwoHexagons","V"]

Select[Range[(2^(n/2-1)),(2^(n/2))],RecognizeGraph[HaarGraph[#]]===g&]

HeawoodGraph

n=GraphData[g="HeawoodGraph","V"]

Select[Range[(2^(n/2-1)),(2^(n/2))],RecognizeGraph[HaarGraph[#]]===g&]

MoebiusKantorGraph

n=GraphData[g="MoebiusKantorGraph","V"]

Select[Range[(2^(n/2-1)),(2^(n/2))],RecognizeGraph[HaarGraph[#]]===g]

Watkin’s zero-symmetric that has no two consecutive ones in its binary expansion and is not cyclically equivalent to any odd number

The corresponding primitive number 536870930 has the property that it has no two consecutive ones in its binary expansion and is not cyclically equivalent to any odd number. It is the smallest positive integer with this property. Its cubic Haar graph is depicted in Fig. 5.

GraphData[{"Haar",536870930}]

ZeroSymmetricGraphQ[%]//Timing

IntegerDigits[536870930,2]

RecognizeGraph[HaarGraph[53687093]]

img=;

w=HaarGraph[536870930]

Through[{PlanarGraphQ,ZeroSymmetricGraphQ,VertexCount,EdgeCount}[w]]

img=

i2=MaxFilter[img,2]

bi2=ColorNegate[Binarize[i2]]

ComponentMeasurements[bi2,"Image"]

p=ComponentMeasurements[bi2,"Centroid"][[All,2]]

p={{207.14285714285714`,410.7142857142857`},{313.64285714285717`,406.42857142857144`},{113.5`,361.07142857142856`},{218.8846153846154`,355.88461538461536`},{298.125`,352.5`},{402.875`,349.6875`},{226.`,334.`},{288.23333333333335`,330.7`},{150.96666666666667`,321.56666666666666`},{362.11538461538464`,313.11538461538464`},{167.36666666666667`,302.43333333333334`},{237.4375`,302.125`},{274.8125`,300.1875`},{343.79411764705884`,295.2058823529412`},{226.9375`,285.75`},{283.55`,284.8`},{184.96153846153845`,275.1923076923077`},{205.38235294117646`,274.02941176470586`},{56.57692307692308`,270.8076923076923`},{303.8333333333333`,271.1`},{323.11538461538464`,270.11538461538464`},{452.5625`,256.125`},{109.4375`,255.0625`},{133.5`,248.5`},{165.3`,244.36666666666667`},{398.76666666666665`,242.43333333333334`},{374.8333333333333`,240.25`},{340.88461538461536`,237.1153846153846`},{174.5`,226.5`},{330.64285714285717`,220.42857142857142`},{173.5`,201.5`},{329.25`,195.16666666666666`},{163.125`,186.5`},{130.5`,181.33333333333331`},{106.14285714285714`,179.07142857142856`},{338.5`,178.875`},{371.25`,172.83333333333331`},{395.35714285714283`,166.42857142857144`},{52.57142857142857`,165.35714285714283`},{180.76666666666668`,151.56666666666666`},{200.`,152.`},{447.96153846153845`,150.80769230769232`},{298.6875`,148.875`},{318.76666666666665`,147.7`},{220.44736842105263`,137.9736842105263`},{276.8076923076923`,137.03846153846155`},{160.11111111111111`,126.72222222222223`},{229.125`,121.5625`},{337.79411764705884`,119.38235294117646`},{267.11538461538464`,119.11538461538464`},{143.`,108.78571428571428`},{353.57142857142856`,100.35714285714283`},{216.75`,90.875`},{278.7142857142857`,87.85714285714283`},{102.21428571428571`,72.`},{206.8846153846154`,69.11538461538464`},{286.2857142857143`,65.71428571428572`},{391.1666666666667`,60.833333333333314`},{191.21428571428572`,15.142857142857167`},{297.88461538461536`,10.884615384615358`}};

w=Graph[Range[Length@p],Sort/@(UndirectedEdge@@@Join[
Partition[{1,3,19,39,55,59,60,58,42,22,6,2},2,1,1],
{{19,23},{3,9},{1,4},{2,5},{6,10},{22,26},{42,38},{58,52},{60,57},{59,56},{51,55},{39,35}},
Partition[{56,54,52,37,26,14,5,7,9,24,35,47},2,1,1],
Partition[{53,57,49,38,27,10,8,4,11,23,34,51},2,1,1],
{{53,48},{54,50},{49,44},{37,36},{27,28},{14,21},{8,13},{7,12},{11,17},{24,25},{34,33},{47,40}},
Partition[{40,45,50,43,36,30,21,16,12,18,25,31},2,1,1],
Partition[{41,48,46,44,32,28,20,13,15,17,29,33},2,1,1],
{{18,15},{16,20},{30,32},{43,46},{45,41},{31,29}}
]),VertexCoordinates->p,VertexSize->Large,VertexLabels->"Name"]

v=ToCommonEdges[w,GraphData[{"Haar",536870930}]];

v/Max[Flatten[Abs[v]]]

IsomorphicGraphQ[g,HaarGraph[536870930]]

Through[{PlanarGraphQ,ZeroSymmetricGraphQ,VertexCount,EdgeCount}[g]]

lines=ImageLines[img2];

HighlightImage[img,{Orange,Line@Take[lines,10]}]

No two consecutive 1's in binary

NoConsecutiveOnesQ[n_]:=BitAnd[n,2n]==0

Select[Range[700],NoConsecutiveOnesQ]

s1=Select[Range[10^5],BitAnd[#,2#]==0&];//Timing

s2=With[{r=Range[10^5]},Pick[r,BitAnd[r,2r],0]];//Timing

s5=Select[Range[10^5],BitAnd[#,2 #]==0&];//Timing

s3=Select[Range[10^5],!StringMatchQ[IntegerString[#,2],"*11*"]&];//Timing

s3=Select[Range[10^5],!StringMatchQ[IntegerString[#,2],"*11*"]&];//Timing

s4=Select[Range[10^5],!MemberQ[Partition[IntegerDigits[#,2],2,1],{1,1}]&];//Timing

s1==s2==s3==s4==s5

BitAnd[#,2#]&@536870930

Not cyclically equivalent to any odd number

Circulant example

g=HaarGraph/@{49798,53336,33478}

IsomorphicGraphQ@@@Partition[g,2,1]

RecognizeGraph/@g

VertexCount/@g

e=GroupElements[g=System`CyclicGroup[32]];

g1=UndirectedGraph[CayleyGraph[PermutationGroup[e[[{1,2,7,9,14,15}]]]]];

g2=UndirectedGraph[CayleyGraph[PermutationGroup[e[[{2,3,5,11,13,14}]]]]];

IsomorphicGraphQ[g1,g2]

Disconnected

Grid[Sort[{"Haar"/.GraphData[#,"NotationRules"],#,GraphData[#,"Notation"]/.s_String:>Style[s,Italic]}&/@GraphData[{"Haar","Disconnected"}]],Dividers->All,Alignment->{{Decimal,Left},Automatic}]//TraditionalForm

Haar-equivalant but not cyclically equivalent

gs=HaarGraph/@{143559,137331}

IsomorphicGraphQ@@gs

RecognizeGraph/@gs

IntegerDigits[#,2]&/@{143559,137331}

EquivalentCycles[n_]:=Block[{d=IntegerDigits[n,2],l,s},
FromDigits[#,2]&/@Pick[s=Join[l=NestList[RotateLeft,d,Length[d]-1],Reverse/@l],s[[All,1]],1]
]

CyclicallyEquivalentQ[m_Integer,n_Integer]:=Module[{i=IntegerDigits[m,2],j=IntegerDigits[n,2]},
MemberQ[NestList[RotateLeft,j,Length[j]-1],i]
]
CyclicallyEquivalentQ[l_List]:=If[Length[l]==2,
CyclicallyEquivalentQ@@l,
CyclicallyEquivalentQ[First[l],#]&/@And@@Rest[l]
]

CyclicallyEquivalentQ[{143559,137331}]

conhaars=Cases[Table[{HaarGraph[n],n},{n,100}],{g_?ConnectedGraphQ,k_}:>{CanonicalForm[g],k}];

haars=Select[SplitBy[Sort[conhaars],First],Length[#]>1&][[All,All,2]];

Select[haars,!CyclicallyEquivalentQ[#]&]

RecognizeGraph[HaarGraph[17]]

IntegerDigits[#,2]&/@{17,18,20,24}

EquivalentCycles[17]

EquivalentCycles/@{49798,53336,33478}

IntegerDigits[#,2]&/@{17,18,20,24}

EquivalentCycles[37]

Table

TextGrid[Sort[{GraphData[#,"NotationRules","Haar"],GraphData[#,"Name"]}&/@DeleteCases[GraphData["Haar"],{"Circulant"|"CompleteBipartite"|"CrossedPrism"|"Crown"|"Cycle"|"Haar"|"LadderRung"|"MoebiusLadder"|"Prism",_}]],Dividers->All,Alignment->{{Decimal,Left}}]

HaarGraphQ

Hladnik et al. 2002

Lemma 4.2. A graph is a cyclic Haar graph if and only if it admits an automorphism with precisely two orbits of equal size (and no other orbit) which are independent sets of vertices.

All

<<MathWorld`Graphs`

DeleteCases[
Monitor[{gn=#,GraphData[#,"Haar"],HaarGraphQ[GraphData[#]]}&/@GraphData[;;10],gn],
{_,x_,x_}]//Timing

Chunks

<<MathWorld`Graphs`

DeleteCases[
Monitor[{gn=#,GraphData[#,"Haar"],HaarGraphQ[GraphData[#],"ChunkSize"->10]}&/@GraphData[;;10],gn],
{_,x_,x_}]//Timing

DeleteCases[
Monitor[{gn=#,GraphData[#,"Haar"],HaarGraphQ[GraphData[#],"ChunkSize"->100]}&/@GraphData[;;10],gn],
{_,x_,x_}]//Timing

DeleteCases[
Monitor[{gn=#,GraphData[#,"Haar"],HaarGraphQ[GraphData[#],"ChunkSize"->1000]}&/@GraphData[;;10],gn],
{_,x_,x_}]//Timing

DeleteCases[
Monitor[{gn=#,GraphData[#,"Haar"],HaarGraphQ[GraphData[#],"ChunkSize"->(10^4)]}&/@GraphData[;;10],gn],
{_,x_,x_}]//Timing

DeleteCases[
Monitor[{gn=#,GraphData[#,"Haar"],HaarGraphQ[GraphData[#],"ChunkSize"->(10^7)]}&/@GraphData[;;10],gn],
{_,x_,x_}]//Timing

Length[elem1=GroupElements[GraphAutomorphismGroup@StarGraph[10]]]//Timing

aut=GraphAutomorphismGroup@StarGraph[10];//Timing

range=Range[GroupOrder[aut]];//Timing

Length[elem2=GroupElements[aut,range]]//Timing

elem1===elem2

ReverseSort[GraphData[#,"AutomorphismCount"]&/@GraphData[;;10]]

Algorithms

Smallest is always conecklace (though others may be as well)

data={#,GraphData[#,"NotationRules","Haar"],haars=Cases[GraphData[#,"StandardNames"],{"Haar",n_}:>n],ConecklaceQ/@haars}&/@GraphData["Haar",;;50];

DeleteCases[data,{__,{True,___}}]

Take[data,10]//Column

Checking co-necklace:

DeleteCases[Monitor[{
gn=#,
GraphData[#,"NotationRules","Haar"],
HaarIndices[GraphData[#],1,Method->"Incremental"][[1]]
}&/@GraphData["Haar",;;50],gn],{_,x_,x_}]//Timing

Don't check co-necklace:

DeleteCases[Monitor[{
gn=#,
GraphData[#,"NotationRules","Haar"],
HaarIndices[GraphData[#],1,Method->"Incremental"][[1]]
}&/@GraphData["Haar",;;50],gn],{_,x_,x_}]//Timing

"Incremental"

Without non-Haar check:

DeleteCases[Monitor[{
gn=#,
GraphData[#,"NotationRules","Haar"],
HaarIndices[GraphData[#],1,Method->"Incremental"][[1]]
}&/@GraphData["Haar",;;50],gn],{_,x_,x_}]//Timing

DeleteCases[Monitor[{
gn=#,
GraphData[#,"NotationRules","Haar"],
HaarIndices[GraphData[#],1,Method->"Incremental"][[1]]
}&/@GraphData["Haar",;;50],gn],{_,x_,x_}]//Timing

nonhaar=Complement[GraphData[{"Regular","VertexTransitive"},;;30],GraphData["Haar",;;30]]

Monitor[Check[HaarIndices[GraphData[gn=#],1,Method->"Incremental"],Print[#]]&/@nonhaar,gn]//Union//Timing

GraphData["Haar",60;;62]

HaarIndices[GraphData[{"DifferenceSetIncidence",{31,15,7}}],1]//Timing

HaarIndices[GraphData[{"DifferenceSetIncidence",{31,25,20}}],1]//Timing

HaarIndices[GraphData[{"DifferenceSetIncidence",{31,25,20}}],1]//Timing

HaarIndices[GraphData[{"DifferenceSetIncidence",{31,25,20}}],1,"ReportInterval"->10^6,"InitialIndex"->1239400447, Debug->True]//Timing

indx=IntegerDigits[1239400447,2]

Length[indx]

Count[indx,1]

"Subsets"

DeleteCases[Monitor[{
gn=#,
GraphData[#,"NotationRules","Haar"],
HaarIndices[GraphData[#],1,Method->"Subsets"][[1]]
}&/@GraphData["Haar",;;50],gn],{_,x_,x_}]//Timing

"Trott"

DeleteCases[
Monitor[{
gn=#,
GraphData[#,"NotationRules","Haar"],
HaarIndices[GraphData[#],1,Method->"Trott"][[1]]
}&/@Complement[GraphData["Haar",;;50],GraphData["LadderRung"]],gn],
{_,x_,x_}]//Timing

GraphData

GraphClass

GraphClassString[GraphData["Haar"]]

GraphDataString

file=OpenWrite["~/watkins.m"];

WriteString[file,GraphDataString[HaarGraph[536870930],
"Name"->"53687093\[Hyphen]Haar graph",
"AlternateNames"->{"Watkins Haar graph"},
"StandardName"->{"Haar",536870930},
"AlternateStandardNames"->{"WatkinsHaarGraph"},
"Vertices"->{v},
TimeConstraint->10,
"Classes"->{"Haar"},
"NotationRules"->{"Haar"->536870930}
]]

Close[file]