Simple Graph

Author

Eric W. Weisstein
January 19, 2024

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

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

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

Classes of Simple Graphs

g={AntiprismGraph,CompleteGraph,Cycle,EmptyGraph,GearGraph,PrismGraph,Star,Wheel};

ShowGraphArray[Map[If[Head[#]===Graph&&SimpleQ[#],#,{}]&,
Transpose[Table[Through[g[n]],{n,8}]],
{2}],
AspectRatio->1,
VertexStyle->Disk[.1],
VertexColor->Red,
GraphicsSpacing->{.3,.1}]

Simple Graph Counts

A000088

Table[SimpleGraphCount[n],{n,11}]//Timing

Length/@Graphs/@Range[9]//Timing

Compute

file=OpenWrite["~/b000088.txt"]

$Version

Do[
Print[{n,(WriteString[file,StringRiffle[ToString/@{n,cnt=SimpleGraphCount[n]}," "]<>"\n"];N[cnt])//Timing}],
{n,100}]

Linux (byblis66)

Do[
Print[{n,(WriteString[file,StringRiffle[ToString/@{n,cnt=SimpleGraphCount[n]}," "]<>"\n"];N[cnt])//Timing}],
{n,100}]

Table

counts=Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/SimpleGraphCounts.txt","Table"];

TextGrid[counts,Dividers->All,BaseStyle->6]

Plot

counts=Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/SimpleGraphCounts.txt","Table"];

bug(423253): When given large exact values, ListPlot issues ListPlot::prng: Value of option PlotRange -> {{0,100.},{0,1.610313993983456*10^900}} is not All ...

ListPlot[counts]

bug(423254): When given large exact values, ListLogPlot issues General::munfl, gives pinked plot, pink tooltip, and red cell bracket

ListLogPlot[counts]

With k edges

(g=Table[NumberOfGraphs[n,k],{n,6},{k,0,Binomial[n,2]}])//ColumnForm

e=Table[M/@Graphs[n],{n,9}];

ColumnForm[c=Counts/@e]

ID Number: A008406
Sequence:  1,1,1,1,1,1,1,1,1,2,3,2,1,1,1,1,2,4,6,6,6,4,2,1,1,1,1,2,5,9,
           15,21,24,24,21,15,9,5,2,1,1,1,1,2,5,10,21,41,65,97,131,148,
           148,131,97,65,41,21,10,5,2,1,1,1,1,2,5,11,24,56,115,221
Name:      Triangle T(n,k) giving number of graphs with n >= 1 nodes and k edges,
              (0 <= k <= n(n-1)/2).
References L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 264.
           F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
           F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY,
              1973, p. 240.
           J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958,
              p. 146.
Links:     G. Royle, Small graphs
Example:   1; 1,1; 1,1,1,1; 1,1,2,3,2,1,1 [ the last batch giving the numbers of
              graphs with 4 nodes and from 0 to 6 edges ].
See also:  Row sums give A000088.
           Cf. A046742, A046751, A000664, A000717, A001432, A001431, A001430,
              A001433, A001434, A048179, A048180 etc.
           Cf. also A039735.
Keywords:  nonn,tabf,nice
Offset:    1
Author(s): njas

Average number of edges for graphs on n nodes

m=Mean/@e

Table[n(n-1)/4,{n,9}]

Through[{Numerator,Denominator}[m]]

Total numbers of edges

Plus@@@e

m (NumberOfGraphs/@Range[9])

Timing[edges=Table[n(n-1)/4 NumberOfGraphs[n],{n,20}]]

Graphs with n nodes

1–7 Nodes

Do[Print[Timing[{n,ListGraphs[n]//Length}]],{n,7}]

8 Nodes

(g8=Graphs[8])//Length//Timing//AbsoluteTiming

ByteCount[g8]/10^6. MB

(g8=Graphs[8,"Format"->"AdjacencyMatrix"])//Length//Timing//AbsoluteTiming

ByteCount[g8]/10^6. MB

9 Nodes

(g9=Graphs[9])//Length//Timing//AbsoluteTiming

ByteCount[g9]/10^6. MB

(g9=Graphs[9,"Format"->"AdjacencyMatrix"])//Length//Timing//AbsoluteTiming

ByteCount[g9]/10^6. MB

10 Nodes

(g10=Graphs[10])//Length//Timing//AbsoluteTiming

{ByteCount[g10],MaxMemoryUsed[]}/10^9. GB

(g10=Graphs[10,"Format"->"AdjacencyMatrix"])//Length//Timing//AbsoluteTiming

{ByteCount[g10],MaxMemoryUsed[]}/10^9. GB

StringLength[g10=Import["/Volumes/Users/eww/Mathematica/Paclets/GraphData/Collections/McKay/graph10.g6.gz","String"]]//Timing

Length[gs=StringSplit[g10]]//Timing

file=OpenWrite["/Volumes/Users/eww/Mathematica/Paclets/GraphData/_Graphs10/CanonicalForm.m"]

Monitor[Do[WriteString[file,StringReplace[ToString[CanonicalForm[ImportString[gs[[i]],{"Graph6","AdjacencyMatrix"}][[1]]]]," "->""]<>"\n"],{i,Length[gs]}],i]//Timing

Close[file]

Counts

Need pair group of this:

Table[CycleIndexPolynomial[System`SymmetricGroup[n],Array[a,n]],{n,5}]/.a[k_]:>Subscript[a,k]//Column//TraditionalForm

GraphStructure[n_Integer]:=Module[{x,var,poly},
var=Array[x,n];
poly=CycleIndexPolynomial[System`SymmetricGroup[n],var];
Transpose[List@@@CoefficientRules[poly,var]]
]

SimpleGraphCount[p_]:=Module[{j,h,n,q,r},
{j,h}=GraphStructure[p];
Sum[h[[i]]2^(
Sum[n j[[i,2n]]+2n Binomial[j[[i,2n]],2],{n,Floor[p/2]}]+
Sum[n j[[i,2n+1]]+(2n+1)Binomial[j[[i,2n+1]],2],{n,0,Floor[(p-1)/2]}]+
Sum[j[[i,q]] j[[i,r]] GCD[q,r],{q,p},{r,q+1,p}]
),
{i,Length[j]}
]
]

Table[SimpleGraphCount[n],{n,15}]

Enumeration (old)

Table[Expand[(#/#[[1,1]])]&@SymmetricGroupIndex[n,x]/.x[k_]:>Subscript[x,k],{n,2,7}]//TableForm//TraditionalForm

GraphStructure[n_Integer]:=Module[
{
poly=SymmetricGroupIndex[n,x],
d,dtl,l,s,v
},
v=Variables[poly];
dtl=Internal`DistributedTermsList[poly,v];
{l,s}=Transpose[First[dtl]]
]/; n>=2

GraphR[p_,g_]:=Module[{j,h,n,q,r},
{j,h}=GraphStructure[p];
Expand[
p!Sum[h[[i]]*
Product[(g[n]g[2n]^(n-1))^j[[i,2n]] g[2n]^(2n Binomial[j[[i,2n]],2]),{n,Floor[p/2]}]*
Product[g[2n+1]^(n j[[i,2n+1]]+(2n+1)Binomial[j[[i,2n+1]],2]),{n,0,Floor[(p-1)/2]}]*
Product[g[LCM[q,r]]^(j[[i,q]] j[[i,r]] GCD[q,r]),{q,p},{r,q+1,p}],
{i,Length[j]}]
]
]

GraphEnumerate[p_]:={
GraphStructure[p],
Expand[p!SymmetricGroupIndex[p,f]],
GraphR[p,g],
r=Expand[GraphR[p,g]/p!/.g[n_]->1+x^n],
r/.x:>1
}

Enumeration of simple graphs

GraphEnumerate[2]//PolyaForm

GraphEnumerate[3]//PolyaForm

GraphEnumerate[4]//PolyaForm

GraphEnumerate[5]//PolyaForm

GraphEnumerate[6]//PolyaForm

GraphEnumerate[7]//PolyaForm

With[{p=20},
Expand[GraphR[p,g]/p!/.g[n_]->2]
]//Timing

With[{p=24},
Expand[GraphR[p,g]/p!/.g[n_]->2]
]//Timing

Last[%]-195704906302078447922174862416726256004122075267063365754368

Algorithms

https://oeis.org/A000088

IntegerPartitions

permcount[v_]:=Module[{m=1,s=0,k=0,t},For[i=1,i<=Length[v],i++,t=v[[i]];k=If[i>1&&t==v[[i-1]],k+1,1];m*=t*k;s+=t];s!/m];
edges[v_]:=Sum[GCD[v[[i]],v[[j]]],{i,2,Length[v]},{j,1,i-1}]+Total[Quotient[v,2]];
a1[n_]:=Module[{s=0},Do[s+=permcount[p]*2^edges[p],{p,IntegerPartitions[n]}];s/n!];

Array[a1,25]//Timing

Do[Print[{n,a1[10n]//Timing}],{n,6}]

Sum

b[n_,i_,l_]:=If[n==0||i==1,1/n!2^(Function[p,Sum[Ceiling[(p[[j]]-1)/2]+Sum[GCD[p[[k]],p[[j]]],{k,j-1}],{j,Length[p]}]][Join[l,Table[1,{n}]]]),Sum[b[n-i j,i-1,Join[l,Table[i,{j}]]]/j!/i^j,{j,0,n/i}]];
a2[n_]:=b[n,n,{}];

Array[a2,25]//Timing

Do[Print[{n,a2[10n]//Timing}],{n,6}]

Embeddings

<<MathWorld`Graphs`

5

{5, 10}

Names

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

GraphData[{5,10},"StandardNames"]

Primary

GraphData[{5,10}]//StyleGraphs[#,ImageSize->Small]&

Configuration

GraphData[{5,10},"Configuration"]

GraphData[{5,10},"Graph","Configuration"]//StyleGraphs

All

GraphData[{5,10},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{5,10},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{5,10},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{5,10},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{5,10},"Graph","Degenerate"]

Perspective

GraphData[{5,10},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{5,10},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{5,10},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{5,10},"Planar"]

GraphData[{5,10},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{5,10},{"RCN","CN"}]

GraphData[{5,10},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{5,10},"Circulant"]

GraphData[{5,10},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{5,10},"ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

GraphComplement/@GraphData["DartGraph","Graph","All"]

GraphPlot@

Line graph

GraphData[{5,10},"Line"]

LineGraphQ[GraphData[{5,10}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {5,10}&]

RootGraph[GraphData[{5,10}]]

LineGraph/@GraphData[{7,63},"Graph","All"]

Halin

GraphData[{5,10},"Halin"]

GraphData[{5,10},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{5,10},"Rigid"]

GraphData[{5,10},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{5,10},"Flexible"]

GraphData[{5,10},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{5,10},"LCF"]

GraphData[{5,10},"HamiltonianCycleCount"]

GraphData[{5,10},"LCFSignature"]

GraphData[{5,10},"LCFNotations"]

GraphData[{5,10},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{5,10},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{5,10}],Debug->True]//Timing

GraphData[{5,10},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{5,10},"VertexList"],GraphData[{5,10},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{5,10},"Matchstick"]

GraphData[{5,10},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[Range[5],GraphData[{5,10},"Edges"]]

3D All

GraphData[{5,10},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{5,10},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{5,10},"Polyhedral"]

GraphData[{5,10},"Graph",{"3D","Polyhedron"}]

{5, 31}

Names

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

GraphData[{5,31},"StandardNames"]

Primary

GraphData[{5,31}]//StyleGraphs[#,ImageSize->Small]&

Configuration

GraphData[{5,31},"Configuration"]

GraphData[{5,31},"Graph","Configuration"]//StyleGraphs

All

GraphData[{5,31},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{5,31},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph@GraphData[{5,31},"Edges"],Pi/2]

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

RecognizeGraph[g]

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

gs={,}

Degenerate

GraphData[{5,31},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{5,31},"Graph","Degenerate"]

Perspective

GraphData[{5,31},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{5,31},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{5,31},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{5,31}],All][[All,All,1]]]

circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{5,31}],#]&/@hc

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing//Quiet

gs=bilat

g=RotateGraph[,Pi]

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

Planar

GraphData[{5,31},"Planar"]

GraphData[{5,31},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{5,31},{"RCN","CN"}]

GraphData[{5,31},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{5,31}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{5,31}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{5,31},"Circulant"]

GraphData[{5,31},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{5,31},"ComplementGraph","Name"]

GraphComplement/@GraphData[%,"Graph","All"]

Line graph

GraphData[{5,31},"Line"]

LineGraphQ[GraphData[{5,31}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {5,31}&]

RootGraph[GraphData[{5,31}]]

Halin

GraphData[{5,31},"Halin"]

GraphData[{5,31},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{5,31},"Rigid"]

GraphData[{5,31},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{5,31},"Flexible"]

GraphData[{5,31},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{5,31},"LCF"]

GraphData[{5,31},"HamiltonianCycleCount"]

GraphData[{5,31},"LCFSignature"]

GraphData[{5,31},"LCFNotations"]

GraphData[{5,31},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{5,31}],TimeConstraint->120]

UnitDistance

GraphData[{5,31},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{5,31}],Debug->True]//Timing

GraphData[{5,31},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{5,31},"VertexList"],GraphData[{5,31},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{5,31},"Matchstick"]

GraphData[{5,31},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{5,31},"Edges"]]

3D All

GraphData[{5,31},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{5,31},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{5,31},"Polyhedral"]

GraphData[{5,31},"Graph",{"3D","Polyhedron"}]

6

{6, 95}

GraphData[{6,95},"StandardName"]

Primary

GraphData[{6,95}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{6,95},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{6,95},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{6,95},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{6,95},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{6,95},"Graph","Degenerate"]

Bilateral

GraphData[{6,95},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{6,95},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{6,95}],All][[All,All,1]]]

Length[bilat=Union@DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{6,95}],#]&/@hc]]//Timing

Planar

GraphData[{6,95},"Planar"]

GraphData[{6,95},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{6,95},{"RCN","CN"}]

GraphData[{6,95},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

GraphPlot@MinimalCrossingGraph[GraphData[{6,95}],"CrossingNumber"->0]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{6,95},"Circulant"]

GraphData[{6,95},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{6,95},"Halin"]

GraphData[{6,95},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{6,95},"Rigid"]

GraphData[{6,95},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{6,95},"Flexible"]

GraphData[{6,95},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{6,95},"LCF"]

GraphData[{6,95},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{6,95},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{6,95}],Debug->True]//Timing

GraphData[{6,95},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{6,95},"Matchstick"]

GraphData[{6,95},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{6,95},"Edges"]]

3D All

GraphData[{6,95},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{6,95},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{6,95},"Polyhedral"]

GraphData[{6,95},"Graph",{"3D","Polyhedron"}]

7

{7, 483}

GraphData[{7,483},"StandardName"]

Primary

GraphData[{7,483}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{7,483},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{7,483},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{7,483},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{7,483},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{7,483},"Graph","Degenerate"]

Bilateral

GraphData[{7,483},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{7,483},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{7,483}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{7,483}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{7,483},"Planar"]

GraphData[{7,483},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{7,483},{"RCN","CN"}]

GraphData[{7,483},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{7,483}]]

GraphPlot@RotateGraph[,4Pi/5]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RotateGraph[GraphicsToGraph@,Pi]

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

RecognizeGraph@g

Circulant

GraphData[{7,483},"Circulant"]

GraphData[{7,483},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{7,483},"Halin"]

GraphData[{7,483},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{7,483},"Rigid"]

GraphData[{7,483},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{7,483},"Flexible"]

GraphData[{7,483},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{7,483},"LCF"]

GraphData[{7,483},"HamiltonianCycleCount"]

GraphData[{7,483},"LCFSignature"]

GraphData[{7,483},"LCFNotations"]

GraphData[{7,483},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{7,483},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{7,483}],Debug->True]//Timing

GraphData[{7,483},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{7,483},"VertexList"],GraphData[{7,483},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{7,483},"Matchstick"]

GraphData[{7,483},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{7,483},"Edges"]]

3D All

GraphData[{7,483},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{7,483},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{7,483},"Polyhedral"]

GraphData[{7,483},"Graph",{"3D","Polyhedron"}]

{7, 485}

GraphData[{7,485},"StandardName"]

Primary

GraphData[{7,485}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{7,485},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{7,485},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{7,485},"Edges"]

GraphPlot@RotateGraph[GraphicsToGraph[],{3,4}]

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

RecognizeGraph[g]

Degenerate

GraphData[{7,485},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{7,485},"Graph","Degenerate"]

Bilateral

GraphData[{7,485},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{7,485},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{7,485}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{7,485}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{7,485},"Planar"]

GraphData[{7,485},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{7,485},{"RCN","CN"}]

GraphData[{7,485},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{7,485}]]

GraphPlot@RotateGraph[,4Pi/5]

RotateGraph[GraphicsToGraph@,Pi]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{7,485},"Circulant"]

GraphData[{7,485},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{7,485},"Halin"]

GraphData[{7,485},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{7,485},"Rigid"]

GraphData[{7,485},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{7,485},"Flexible"]

GraphData[{7,485},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{7,485},"LCF"]

GraphData[{7,485},"HamiltonianCycleCount"]

GraphData[{7,485},"LCFSignature"]

GraphData[{7,485},"LCFNotations"]

GraphData[{7,485},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{7,485},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{7,485}],Debug->True]//Timing

GraphData[{7,485},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{7,485},"VertexList"],GraphData[{7,485},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{7,485},"Matchstick"]

GraphData[{7,485},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{7,485},"Edges"]]

3D All

GraphData[{7,485},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{7,485},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{7,485},"Polyhedral"]

GraphData[{7,485},"Graph",{"3D","Polyhedron"}]

{7, 498}

GraphData[{7,498},"StandardName"]

Primary

GraphData[{7,498}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{7,498},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{7,498},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{7,498},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{7,498},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{7,498},"Graph","Degenerate"]

Bilateral

GraphData[{7,498},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{7,498},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{7,498}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{7,498}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{7,498},"Planar"]

GraphData[{7,498},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{7,498},{"RCN","CN"}]

GraphData[{7,498},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

GraphPlot@MinimalCrossingGraph[GraphData[{7,498}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{7,498},"Circulant"]

GraphData[{7,498},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{7,498},"Halin"]

GraphData[{7,498},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{7,498},"Rigid"]

GraphData[{7,498},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{7,498},"Flexible"]

GraphData[{7,498},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{7,498},"LCF"]

GraphData[{7,498},"HamiltonianCycleCount"]

GraphData[{7,498},"LCFSignature"]

GraphData[{7,498},"LCFNotations"]

GraphData[{7,498},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{7,498},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{7,498}],Debug->True]//Timing

GraphData[{7,498},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{7,498},"VertexList"],GraphData[{7,498},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{7,498},"Matchstick"]

GraphData[{7,498},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{7,498},"Edges"]]

3D All

GraphData[{7,498},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{7,498},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{7,498},"Polyhedral"]

GraphData[{7,498},"Graph",{"3D","Polyhedron"}]

{7, 1028}

GraphData[{7,1028},"StandardName"]

Primary

GraphData[{7,1028}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{7,1028},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{7,1028},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph[GraphData[{7,1028},"Edges"]],Pi/2]

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

RecognizeGraph[g]

Degenerate

GraphData[{7,1028},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{7,1028},"Graph","Degenerate"]

Bilateral

GraphData[{7,1028},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{7,1028},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{7,1028}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{7,1028}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

bilat

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

Planar

GraphData[{7,1028},"Planar"]

GraphData[{7,1028},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{7,1028},{"RCN","CN"}]

GraphData[{7,1028},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{7,1028}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{7,1028}],TimeConstraint->10])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{7,1028},"Circulant"]

GraphData[{7,1028},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{7,1028},"Halin"]

GraphData[{7,1028},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{7,1028},"Rigid"]

GraphData[{7,1028},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{7,1028},"Flexible"]

GraphData[{7,1028},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{7,1028},"LCF"]

GraphData[{7,1028},"HamiltonianCycleCount"]

GraphData[{7,1028},"LCFSignature"]

GraphData[{7,1028},"LCFNotations"]

GraphData[{7,1028},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{7,1028},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{7,1028}],Debug->True]//Timing

GraphData[{7,1028},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{7,1028},"VertexList"],GraphData[{7,1028},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{7,1028},"Matchstick"]

GraphData[{7,1028},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{7,1028},"Edges"]]

3D All

GraphData[{7,1028},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{7,1028},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{7,1028},"Polyhedral"]

GraphData[{7,1028},"Graph",{"3D","Polyhedron"}]

{7, 1032} == {"KTree", {4, {7, 2}}}

Names

GraphData[{7,1032},"StandardName"]

GraphData[{7,1032},"StandardNames"]

{7, 1033}

GraphData[{7,1033},"StandardName"]

Primary

GraphData[{7,1033}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{7,1033},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{7,1033},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph[GraphData[{7,1033},"Edges"],GraphLayout->"SpringEmbedding"],-Pi/2]

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

RecognizeGraph[g]

BilateralGraphEmbeddingTypes[g]

Degenerate

GraphData[{7,1033},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{7,1033},"Graph","Degenerate"]

Bilateral

GraphData[{7,1033},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{7,1033},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{7,1033}],All][[All,All,1]]]

Length[bilat=Union@DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{7,1033}],#]&/@hc]]//Timing

bilat

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

Planar

GraphData[{7,1033},"Planar"]

GraphData[{7,1033},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{7,1033},{"RCN","CN"}]

GraphData[{7,1033},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{7,1033}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{7,1033}],TimeConstraint->10])//AbsoluteTiming

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

Table[MinimalCrossingGraph[GraphData[{7,1033}],"CrossingNumber"->cn,RandomSeed->i],{i,100}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{7,1033},"Circulant"]

GraphData[{7,1033},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{7,1033},"Halin"]

GraphData[{7,1033},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{7,1033},"Rigid"]

GraphData[{7,1033},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{7,1033},"Flexible"]

GraphData[{7,1033},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{7,1033},"LCF"]

GraphData[{7,1033},"HamiltonianCycleCount"]

GraphData[{7,1033},"LCFSignature"]

GraphData[{7,1033},"LCFNotations"]

GraphData[{7,1033},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{7,1033},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{7,1033}],Debug->True]//Timing

GraphData[{7,1033},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{7,1033},"VertexList"],GraphData[{7,1033},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

GraphPlot@

Matchstick

GraphData[{7,1033},"Matchstick"]

GraphData[{7,1033},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{7,1033},"Edges"]]

3D All

GraphData[{7,1033},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{7,1033},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{7,1033},"Polyhedral"]

GraphData[{7,1033},"Graph",{"3D","Polyhedron"}]

{7, 1038}

GraphData[{7,1038},"StandardName"]

Primary

GraphData[{7,1038}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{7,1038},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{7,1038},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph@GraphData[{7,1038},"Edges"],Pi/2]

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

RecognizeGraph[g]

Degenerate

GraphData[{7,1038},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{7,1038},"Graph","Degenerate"]

Bilateral

GraphData[{7,1038},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{7,1038},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{7,1038}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{7,1038}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{7,1038},"Planar"]

GraphData[{7,1038},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{7,1038},{"RCN","CN"}]

GraphData[{7,1038},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{7,1038}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{7,1038}],TimeConstraint->10])//AbsoluteTiming

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

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

GraphPlot@RotateGraph[,-Pi/2]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{7,1038},"Circulant"]

GraphData[{7,1038},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{7,1038},"Halin"]

GraphData[{7,1038},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{7,1038},"Rigid"]

GraphData[{7,1038},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{7,1038},"Flexible"]

GraphData[{7,1038},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{7,1038},"LCF"]

GraphData[{7,1038},"HamiltonianCycleCount"]

GraphData[{7,1038},"LCFSignature"]

GraphData[{7,1038},"LCFNotations"]

GraphData[{7,1038},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{7,1038},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{7,1038}],Debug->True]//Timing

GraphData[{7,1038},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{7,1038},"VertexList"],GraphData[{7,1038},"EdgeList"]],MaxIterations->500]

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

Matchstick

GraphData[{7,1038},"Matchstick"]

GraphData[{7,1038},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{7,1038},"Edges"]]

3D All

GraphData[{7,1038},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{7,1038},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{7,1038},"Polyhedral"]

GraphData[{7,1038},"Graph",{"3D","Polyhedron"}]

{7, 1039}

GraphData[{7,1039},"StandardName"]

Primary

GraphData[{7,1039}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{7,1039},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{7,1039},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{7,1039},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{7,1039},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{7,1039},"Graph","Degenerate"]

Bilateral

GraphData[{7,1039},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{7,1039},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{7,1039}],All][[All,All,1]]]

Length[bilat=Union@DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{7,1039}],#]&/@hc]]//Timing

bilat

gs=RotateGraph@@@Transpose[{bilat,{Pi,Pi,0}}]

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

Planar

GraphData[{7,1039},"Planar"]

GraphData[{7,1039},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{7,1039},{"RCN","CN"}]

GraphData[{7,1039},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{7,1039}],TimeConstraint->1])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{7,1039},"Circulant"]

GraphData[{7,1039},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{7,1039},"Halin"]

GraphData[{7,1039},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{7,1039},"Rigid"]

GraphData[{7,1039},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{7,1039},"Flexible"]

GraphData[{7,1039},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{7,1039},"LCF"]

GraphData[{7,1039},"HamiltonianCycleCount"]

GraphData[{7,1039},"LCFSignature"]

GraphData[{7,1039},"LCFNotations"]

GraphData[{7,1039},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{7,1039},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{7,1039}],Debug->True]//Timing

GraphData[{7,1039},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{7,1039},"VertexList"],GraphData[{7,1039},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{7,1039},"Matchstick"]

GraphData[{7,1039},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{7,1039},"Edges"]]

3D All

GraphData[{7,1039},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{7,1039},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{7,1039},"Polyhedral"]

GraphData[{7,1039},"Graph",{"3D","Polyhedron"}]

8

{8, 11585}

GraphData[{8,11585},"StandardName"]

Primary

GraphData[{8,11585}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{8,11585},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{8,11585},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{8,11585},"Edges"]

GraphPlot@RotateGraph[GraphicsToGraph@,Pi/2]

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

RecognizeGraph[g]

Degenerate

GraphData[{8,11585},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{8,11585},"Graph","Degenerate"]

Bilateral

GraphData[{8,11585},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{8,11585},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{8,11585}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{8,11585}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

bilat

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

Planar

GraphData[{8,11585},"Planar"]

GraphData[{8,11585},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{8,11585},{"RCN","CN"}]

GraphData[{8,11585},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{8,11585}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{8,11585}],TimeConstraint->10])//AbsoluteTiming

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

Table[MinimalCrossingGraph[GraphData[{8,11585}],"CrossingNumber"->cn,RandomSeed->i],{i,100}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{8,11585},"Circulant"]

GraphData[{8,11585},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{8,11585},"Halin"]

GraphData[{8,11585},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{8,11585},"Rigid"]

GraphData[{8,11585},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{8,11585},"Flexible"]

GraphData[{8,11585},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{8,11585},"LCF"]

GraphData[{8,11585},"HamiltonianCycleCount"]

GraphData[{8,11585},"LCFSignature"]

GraphData[{8,11585},"LCFNotations"]

GraphData[{8,11585},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{8,11585},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{8,11585}],Debug->True]//Timing

GraphData[{8,11585},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{8,11585},"VertexList"],GraphData[{8,11585},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{8,11585},"Matchstick"]

GraphData[{8,11585},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{8,11585},"Edges"]]

3D All

GraphData[{8,11585},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{8,11585},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{8,11585},"Polyhedral"]

GraphData[{8,11585},"Graph",{"3D","Polyhedron"}]

{8, 11690}

GraphData[{8,11690},"StandardName"]

Primary

GraphData[{8,11690}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{8,11690},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{8,11690},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{8,11690},"Edges"]

GraphPlot@RotateGraph[GraphicsToGraph@,-Pi/2]

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

RecognizeGraph[g]

Degenerate

GraphData[{8,11690},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{8,11690},"Graph","Degenerate"]

Bilateral

GraphData[{8,11690},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{8,11690},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{8,11690}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{8,11690}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

bilat

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

Planar

GraphData[{8,11690},"Planar"]

GraphData[{8,11690},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{8,11690},{"RCN","CN"}]

GraphData[{8,11690},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{8,11690}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{8,11690}],TimeConstraint->10])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{8,11690},"Circulant"]

GraphData[{8,11690},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{8,11690},"Halin"]

GraphData[{8,11690},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{8,11690},"Rigid"]

GraphData[{8,11690},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{8,11690},"Flexible"]

GraphData[{8,11690},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{8,11690},"LCF"]

GraphData[{8,11690},"HamiltonianCycleCount"]

GraphData[{8,11690},"LCFSignature"]

GraphData[{8,11690},"LCFNotations"]

GraphData[{8,11690},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{8,11690},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{8,11690}],Debug->True]//Timing

GraphData[{8,11690},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{8,11690},"VertexList"],GraphData[{8,11690},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{8,11690},"Matchstick"]

GraphData[{8,11690},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{8,11690},"Edges"]]

3D All

GraphData[{8,11690},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{8,11690},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{8,11690},"Polyhedral"]

GraphData[{8,11690},"Graph",{"3D","Polyhedron"}]

{8, 12212}

GraphData[{8,12212},"StandardName"]

Primary

GraphData[{8,12212}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{8,12212},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{8,12212},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{8,12212},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{8,12212},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{8,12212},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{8,12212},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{8,12212},"Planar"]

GraphData[{8,12212},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{8,12212},{"RCN","CN"}]

GraphData[{8,12212},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{8,12212}],TimeConstraint->10])//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{8,12212}],"CrossingNumber"->cn]]

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

GraphData[{8,12212},"Graph","Labeled"]

VertexDegree[%,8]

RecognizeGraph@VertexDelete[GraphData[{8,12212},"Graph","Labeled"],{2}]

g0=GraphData[{"CompleteKPartite",{1,1,1,1,1,2}},"Graph",{"Labeled","MinimalCrossing"}][[1]]

Position[VertexDegree[%],5]//Flatten

g=Graph[Range[8],Join[EdgeList[g0],UndirectedEdge@@@{{1,8}}],VertexCoordinates->Append[v=GraphEmbedding[g0],v[[1]]+v[[1]]-v[[5]]],VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{8,12212},"Circulant"]

GraphData[{8,12212},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{8,12212},"Halin"]

GraphData[{8,12212},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{8,12212},"LCF"]

GraphData[{8,12212},"HamiltonianCycleCount"]

GraphData[{8,12212},"LCFSignature"]

GraphData[{8,12212},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{8,12212},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{8,12212}],Debug->True]//Timing

GraphData[{8,12212},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{8,12212},"VertexList"],GraphData[{8,12212},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{8,12212},"Matchstick"]

GraphData[{8,12212},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{8,12212},"Edges"]]

3D All

GraphData[{8,12212},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{8,12212},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{8,12212},"Polyhedral"]

GraphData[{8,12212},"Graph",{"3D","Polyhedron"}]

{8, 12214}

GraphData[{8,12214},"StandardName"]

Primary

GraphData[{8,12214}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{8,12214},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{8,12214},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{8,12214},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{8,12214},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{8,12214},"Graph","Degenerate"]

Bilateral

GraphData[{8,12214},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{8,12214},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{8,12214}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{8,12214}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

bilat

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

Planar

GraphData[{8,12214},"Planar"]

GraphData[{8,12214},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{8,12214},{"RCN","CN"}]

GraphData[{8,12214},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{8,12214}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{8,12214}],TimeConstraint->10])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{8,12214},"Circulant"]

GraphData[{8,12214},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{8,12214},"Halin"]

GraphData[{8,12214},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{8,12214},"Rigid"]

GraphData[{8,12214},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{8,12214},"Flexible"]

GraphData[{8,12214},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{8,12214},"LCF"]

GraphData[{8,12214},"HamiltonianCycleCount"]

GraphData[{8,12214},"LCFSignature"]

GraphData[{8,12214},"LCFNotations"]

GraphData[{8,12214},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{8,12214},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{8,12214}],Debug->True]//Timing

GraphData[{8,12214},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{8,12214},"VertexList"],GraphData[{8,12214},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{8,12214},"Matchstick"]

GraphData[{8,12214},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{8,12214},"Edges"]]

3D All

GraphData[{8,12214},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{8,12214},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{8,12214},"Polyhedral"]

GraphData[{8,12214},"Graph",{"3D","Polyhedron"}]

{8, 12215}

Names

GraphData[{8,12215},"StandardName"]

GraphData[{8,12215},"StandardNames"]

Primary

GraphData[{8,12215}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{8,12215},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{8,12215},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{8,12215},"Edges"]

GraphPlot@RotateGraph[GraphicsToGraph@,-1]

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

RecognizeGraph[g]

Degenerate

GraphData[{8,12215},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{8,12215},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{8,12215},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{8,12215}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{8,12215}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{8,12215},"Planar"]

GraphData[{8,12215},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{8,12215},{"RCN","CN"}]

GraphData[{8,12215},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{8,12215}],TimeConstraint->1])//AbsoluteTiming

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

Table[MinimalCrossingGraph[GraphData[{8,12215}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union//Timing

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{8,12215},"Circulant"]

GraphData[{8,12215},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{8,12215},"Halin"]

GraphData[{8,12215},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{8,12215},"LCF"]

GraphData[{8,12215},"HamiltonianCycleCount"]

GraphData[{8,12215},"LCFSignature"]

GraphData[{8,12215},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{8,12215},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{8,12215}],Debug->True]//Timing

GraphData[{8,12215},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{8,12215},"VertexList"],GraphData[{8,12215},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{8,12215},"Matchstick"]

GraphData[{8,12215},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{8,12215},"Edges"]]

3D All

GraphData[{8,12215},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{8,12215},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{8,12215},"Polyhedral"]

GraphData[{8,12215},"Graph",{"3D","Polyhedron"}]

{8, 12291}

GraphData[{8,12291},"StandardName"]

Primary

GraphData[{8,12291}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{8,12291},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{8,12291},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{8,12291},"Edges"]

GraphPlot@RotateGraph[GraphicsToGraph@,-Pi/2]

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

RecognizeGraph[g]

Degenerate

GraphData[{8,12291},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{8,12291},"Graph","Degenerate"]

Bilateral

GraphData[{8,12291},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{8,12291},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{8,12291}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{8,12291}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

bilat

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

Planar

GraphData[{8,12291},"Planar"]

GraphData[{8,12291},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{8,12291},{"RCN","CN"}]

GraphData[{8,12291},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{8,12291}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{8,12291}],TimeConstraint->10])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{8,12291},"Circulant"]

GraphData[{8,12291},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{8,12291},"Halin"]

GraphData[{8,12291},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{8,12291},"Rigid"]

GraphData[{8,12291},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{8,12291},"Flexible"]

GraphData[{8,12291},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{8,12291},"LCF"]

GraphData[{8,12291},"HamiltonianCycleCount"]

GraphData[{8,12291},"LCFSignature"]

GraphData[{8,12291},"LCFNotations"]

GraphData[{8,12291},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{8,12291},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{8,12291}],Debug->True]//Timing

GraphData[{8,12291},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{8,12291},"VertexList"],GraphData[{8,12291},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{8,12291},"Matchstick"]

GraphData[{8,12291},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{8,12291},"Edges"]]

3D All

GraphData[{8,12291},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{8,12291},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{8,12291},"Polyhedral"]

GraphData[{8,12291},"Graph",{"3D","Polyhedron"}]

{8, 12332}

GraphData[{8,12332},"StandardName"]

Primary

GraphData[{8,12332}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{8,12332},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{8,12332},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{8,12332},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{8,12332},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{8,12332},"Graph","Degenerate"]

Bilateral

GraphData[{8,12332},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{8,12332},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{8,12332}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{8,12332}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

bilat

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

Planar

GraphData[{8,12332},"Planar"]

GraphData[{8,12332},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{8,12332},{"RCN","CN"}]

GraphData[{8,12332},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{8,12332}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{8,12332}],TimeConstraint->10])//AbsoluteTiming

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{8,12332},"Circulant"]

GraphData[{8,12332},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{8,12332},"Halin"]

GraphData[{8,12332},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{8,12332},"Rigid"]

GraphData[{8,12332},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{8,12332},"Flexible"]

GraphData[{8,12332},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{8,12332},"LCF"]

GraphData[{8,12332},"HamiltonianCycleCount"]

GraphData[{8,12332},"LCFSignature"]

GraphData[{8,12332},"LCFNotations"]

GraphData[{8,12332},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{8,12332},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{8,12332}],Debug->True]//Timing

GraphData[{8,12332},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{8,12332},"VertexList"],GraphData[{8,12332},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{8,12332},"Matchstick"]

GraphData[{8,12332},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{8,12332},"Edges"]]

3D All

GraphData[{8,12332},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{8,12332},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{8,12332},"Polyhedral"]

GraphData[{8,12332},"Graph",{"3D","Polyhedron"}]

{8, 12333}

GraphData[{8,12333},"StandardName"]

Primary

GraphData[{8,12333}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{8,12333},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{8,12333},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{8,12333},"Edges"]

RotateGraph[GraphicsToGraph@,Pi/2]

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

RecognizeGraph[g]

Degenerate

GraphData[{8,12333},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{8,12333},"Graph","Degenerate"]

Bilateral

GraphData[{8,12333},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{8,12333},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{8,12333}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{8,12333}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

bilat

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

Planar

GraphData[{8,12333},"Planar"]

GraphData[{8,12333},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{8,12333},{"RCN","CN"}]

GraphData[{8,12333},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{8,12333}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{8,12333}],TimeConstraint->10])//AbsoluteTiming

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

Table[MinimalCrossingGraph[GraphData[{8,12333}],"CrossingNumber"->cn,RandomSeed->i],{i,200}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{8,12333},"Circulant"]

GraphData[{8,12333},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{8,12333},"Halin"]

GraphData[{8,12333},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{8,12333},"Rigid"]

GraphData[{8,12333},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{8,12333},"Flexible"]

GraphData[{8,12333},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{8,12333},"LCF"]

GraphData[{8,12333},"HamiltonianCycleCount"]

GraphData[{8,12333},"LCFSignature"]

GraphData[{8,12333},"LCFNotations"]

GraphData[{8,12333},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{8,12333},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{8,12333}],Debug->True]//Timing

GraphData[{8,12333},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceGraphEmbeddingQ[%]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{8,12333},"Matchstick"]

GraphData[{8,12333},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{8,12333},"Edges"]]

3D All

GraphData[{8,12333},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{8,12333},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{8,12333},"Polyhedral"]

GraphData[{8,12333},"Graph",{"3D","Polyhedron"}]

{8, 12334}

Names

GraphData[{8,12334},"StandardName"]

GraphData[{8,12334},"StandardNames"]

Primary

GraphData[{8,12334}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{8,12334},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{8,12334},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{8,12334},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{8,12334},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{8,12334},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{8,12334},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{8,12334},"Planar"]

GraphData[{8,12334},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{8,12334},{"RCN","CN"}]

GraphData[{8,12334},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{8,12334}],TimeConstraint->10])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

GraphPlot@

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{8,12334},"Circulant"]

GraphData[{8,12334},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{8,12334},"Halin"]

GraphData[{8,12334},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{8,12334},"LCF"]

GraphData[{8,12334},"HamiltonianCycleCount"]

GraphData[{8,12334},"LCFSignature"]

GraphData[{8,12334},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{8,12334},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{8,12334}],Debug->True]//Timing

GraphData[{8,12334},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{8,12334},"VertexList"],GraphData[{8,12334},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{8,12334},"Matchstick"]

GraphData[{8,12334},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{8,12334},"Edges"]]

3D All

GraphData[{8,12334},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{8,12334},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{8,12334},"Polyhedral"]

GraphData[{8,12334},"Graph",{"3D","Polyhedron"}]

{8, 12339}

GraphData[{8,12339},"StandardName"]

Primary

GraphData[{8,12339}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{8,12339},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{8,12339},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{8,12339},"Edges"]

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

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

RecognizeGraph[g]

Degenerate

GraphData[{8,12339},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{8,12339},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{8,12339},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{8,12339}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{8,12339}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

bilat

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

Planar

GraphData[{8,12339},"Planar"]

GraphData[{8,12339},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{8,12339},{"RCN","CN"}]

GraphData[{8,12339},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{8,12339}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{8,12339},"Circulant"]

GraphData[{8,12339},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{8,12339},"Halin"]

GraphData[{8,12339},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{8,12339},"LCF"]

GraphData[{8,12339},"HamiltonianCycleCount"]

GraphData[{8,12339},"LCFSignature"]

GraphData[{8,12339},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{8,12339},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{8,12339}],Debug->True]//Timing

GraphData[{8,12339},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{8,12339},"VertexList"],GraphData[{8,12339},"EdgeList"]]]

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{8,12339},"Matchstick"]

GraphData[{8,12339},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{8,12339},"Edges"]]

3D All

GraphData[{8,12339},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{8,12339},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{8,12339},"Polyhedral"]

GraphData[{8,12339},"Graph",{"3D","Polyhedron"}]

9

{9, 122423}

Names

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

GraphData[{9,122423},"StandardNames"]

Primary

GraphData[{9,122423}]//StyleGraphs[#,ImageSize->Small]&

Configuration

GraphData[{9,122423},"Configuration"]

GraphData[{9,122423},"Graph","Configuration"]//StyleGraphs

All

GraphData[{9,122423},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{9,122423},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{9,122423},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{9,122423},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{9,122423},"Graph","Degenerate"]

Perspective

GraphData[{9,122423},"Graph","Perspective"]//StyleGraphs

Bilateral

GraphData[{9,122423},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{9,122423},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{9,122423}],All][[All,All,1]]]

Planar

GraphData[{9,122423},"Planar"]

GraphData[{9,122423},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{9,122423},{"RCN","CN"}]

GraphData[{9,122423},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{9,122423}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{9,122423}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{9,122423},"Circulant"]

GraphData[{9,122423},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{9,122423},"ComplementGraph","Name"]

Line graph

GraphData[{9,122423},"Line"]

LineGraphQ[GraphData[{9,122423}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {9,122423}&]

RootGraph[GraphData[{9,122423}]]

Halin

GraphData[{9,122423},"Halin"]

GraphData[{9,122423},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{9,122423},"Rigid"]

GraphData[{9,122423},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{9,122423},"Flexible"]

GraphData[{9,122423},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{9,122423},"LCF"]

GraphData[{9,122423},"HamiltonianCycleCount"]

GraphData[{9,122423},"LCFSignature"]

GraphData[{9,122423},"LCFNotations"]

GraphData[{9,122423},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{9,122423},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{9,122423}],Debug->True]//Timing

GraphData[{9,122423},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{9,122423},"VertexList"],GraphData[{9,122423},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

gs={,,,,,};

Matchstick

GraphData[{9,122423},"Matchstick"]

GraphData[{9,122423},"Graph","Matchstick"]//StyleGraphs

Matchstick construction

GraphPlot@GraphData[{9,122423},"Graph","UnitDistance"][[1]]

g=LabelGraph@GraphicsToGraph@

UnitDistanceEmbeddingRefine@g

s=Sqrt[3]/2;
v={{-x,0},{x,0},{0,a},{0,z},{0,h},{-x,1},{x-s,1/2},{s-x,1/2},{x,1}};

eqn=UnitEdgeEquations[v,EdgeList[g]]//FullSimplify//Union

var=Variables[Subtract@@@eqn]

Length/@{eqn,var}

soln=Solve[Join[eqn,{0<z<a,x>0}],var,Reals]//FullSimplify

soln[[1]]/.c_ConditionalExpression:>First[c]

N[%]

Manipulate[g=Graph[Range@Length@v,EdgeList[g],VertexCoordinates->(v/.{h->1-a,x->(Sqrt[-((-2+a) a)]),z->(1/2) (1+(Sqrt[1+4 (-2+a) a+4 (Sqrt[3]) (Sqrt[(2-a) a])]))}/.a->a0)],{a0,3/2,2}]

GraphEmbedding[g]

3D default

Graph3D[GraphData[{9,122423},"Edges"]]

3D All

GraphData[{9,122423},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{9,122423},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{9,122423},"Polyhedral"]

GraphData[{9,122423},"Graph",{"3D","Polyhedron"}]