Caveman Graph

Author

Eric W. Weisstein
February 3, 2023

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

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

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

Figures

GraphicsGrid[{GraphPlot[#,Method->None]&/@Table[CavemanGraph[n,3],{n,3,6}]},Spacings->-20]

GraphicsGrid[{GraphPlot[#,Method->None]&/@Table[CavemanGraph[n,4],{n,3,6}]},Spacings->-20]

GraphicsGrid[{GraphPlot[#,Method->None]&/@Table[CavemanGraph[n],{n,3,6}]},Spacings->-20]

Table[{n,k,RecognizeGraph[CavemanGraph[n,k]]},{n,3,10},{k,3,5}]

Properties

Chords

GraphData["Caveman*"]

def=Select[GraphData["Caveman*"],ListQ[GraphData[#,"Chords"]]&]

Column[{#,HighlightGraph[GraphData[#],GraphData[#,"Chords"]]}]&/@def

GraphData[{"Caveman",{3,5}},"Graph","Labeled"]

new=Select[GraphData["Caveman*"],!ListQ[GraphData[#,"Chords"]]&]

CavemanNonchords[n_]:=Sort[Sort/@Table[Mod[5k+{0,1},5n,1],{k,n}]]

CavemanNonchords[4]

Complement[GraphData[gn={"Caveman",{4,5}},"Edges"],GraphData[gn,"Chords"]]

l=Table[{gn={"Caveman",{n,5}},{0,{Length[chords=Complement[GraphData[gn,"EdgeIndices"],CavemanNonchords[n]]],chords}}},{n,8,10}]

Embeddings

<<MathWorld`Graphs`

GraphData["Caveman"]

{"Caveman", {3, 3}}

GraphData[{"Caveman",{3,3}},"StandardName"]

Primary

GraphData[{"Caveman",{3,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Caveman",{3,3}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{3,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{3,3}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Caveman",{3,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Caveman",{3,3}},"Graph","Degenerate"]

Bilateral

GraphData[{"Caveman",{3,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Caveman",{3,3}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Caveman",{3,3}},"Planar"]

GraphData[{"Caveman",{3,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Caveman",{3,3}},{"RCN","CN"}]

GraphData[{"Caveman",{3,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{3,3}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{3,3}},"Circulant"]

GraphData[{"Caveman",{3,3}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Caveman",{3,3}},"Halin"]

GraphData[{"Caveman",{3,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Caveman",{3,3}},"Rigid"]

GraphData[{"Caveman",{3,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Caveman",{3,3}},"Flexible"]

GraphData[{"Caveman",{3,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Caveman",{3,3}},"LCF"]

GraphData[{"Caveman",{3,3}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{3,3}},"LCFSignature"]

GraphData[{"Caveman",{3,3}},"LCFNotations"]

GraphData[{"Caveman",{3,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Caveman",{3,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{3,3}}],Debug->True]//Timing

GraphData[{"Caveman",{3,3}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Caveman",{3,3}},"VertexList"],GraphData[{"Caveman",{3,3}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Caveman",{3,3}},"Matchstick"]

GraphData[{"Caveman",{3,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Caveman",{3,3}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{3,3}},"Polyhedral"]

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

{"Caveman", {3, 4}}

GraphData[{"Caveman",{3,4}},"StandardName"]

Primary

GraphData[{"Caveman",{3,4}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Caveman",{3,4}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{3,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{3,4}},"Edges"]

g=CavemanGraph[3,4]

RecognizeGraph[g]

Degenerate

GraphData[{"Caveman",{3,4}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Caveman",{3,4}},"Graph","Degenerate"]

Bilateral

GraphData[{"Caveman",{3,4}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Caveman",{3,4}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{3,4}}],All][[All,All,1]]]

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{3,4}}],#]&/@hc

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{3,4}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Caveman",{3,4}},"Planar"]

GraphData[{"Caveman",{3,4}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Caveman",{3,4}},{"RCN","CN"}]

GraphData[{"Caveman",{3,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{3,4}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{3,4}},"Circulant"]

GraphData[{"Caveman",{3,4}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Caveman",{3,4}},"Halin"]

GraphData[{"Caveman",{3,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Caveman",{3,4}},"Rigid"]

GraphData[{"Caveman",{3,4}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Caveman",{3,4}},"Flexible"]

GraphData[{"Caveman",{3,4}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Caveman",{3,4}},"LCF"]

GraphData[{"Caveman",{3,4}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{3,4}},"LCFSignature"]

GraphData[{"Caveman",{3,4}},"LCFNotations"]

GraphData[{"Caveman",{3,4}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Caveman",{3,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{3,4}}],Debug->True]//Timing

GraphData[{"Caveman",{3,4}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Caveman",{3,4}},"VertexList"],GraphData[{"Caveman",{3,4}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Caveman",{3,4}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Caveman",{3,4}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Caveman",{3,4}},"Matchstick"]

GraphData[{"Caveman",{3,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Caveman",{3,4}},"Edges"]]

3D All

GraphData[{"Caveman",{3,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Caveman",{3,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Caveman",{3,4}},"Polyhedral"]

GraphData[{"Caveman",{3,4}},"Graph",{"3D","Polyhedron"}]

{"Caveman", {3, 5}}

GraphData[{"Caveman",{3,5}},"StandardName"]

Primary

GraphData[{"Caveman",{3,5}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{3,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{3,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{3,5}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{3,5}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Caveman",{3,5}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{3,5}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{3,5}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{3,5}},"Circulant"]

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

Halin

GraphData[{"Caveman",{3,5}},"Halin"]

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

Rigid

GraphData[{"Caveman",{3,5}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{3,5}},"Flexible"]

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

LCF

GraphData[{"Caveman",{3,5}},"LCF"]

GraphData[{"Caveman",{3,5}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{3,5}},"LCFSignature"]

GraphData[{"Caveman",{3,5}},"LCFNotations"]

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

UnitDistance

GraphData[{"Caveman",{3,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{3,5}}],Debug->True]//Timing

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Caveman",{3,5}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{3,5}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{3,5}},"Polyhedral"]

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

{"Caveman", {4, 3}}

GraphData[{"Caveman",{4,3}},"StandardName"]

Primary

GraphData[{"Caveman",{4,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Caveman",{4,3}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{4,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{4,3}},"Edges"]

EuclideanDistance@@v[[{1,5}]]

EuclideanDistance@@v[[{1,9}]]//FullSimplify

Norm[v[[1]]+Through[{Cos,Sin}[Pi/4]]]//FullSimplify

c=CirclePoints[{(Sqrt[2]),Pi/4},4];
v=Join[c,Mean/@Partition[c,2,1,1],CirclePoints[{1+(Sqrt[2]),Pi/4},4]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,5,2,6,3,7,4,8,1,9],{2,10},{3,11},{4,12}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Norm[v[[1]]+Through[{Cos,Sin}[Pi/4]]]//FullSimplify

EuclideanDistance@@v[[{1,9}]]//FullSimplify

v=Join[UnitCirclePoints[8,Pi/4],CirclePoints[{(1/2) (2+Csc[(π/8)]),Pi/4},4]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[{1,8},1,9],{3,10},{5,11},{7,12}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

gs={,}

Degenerate

GraphData[{"Caveman",{4,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Caveman",{4,3}},"Graph","Degenerate"]

Bilateral

GraphData[{"Caveman",{4,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Caveman",{4,3}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Caveman",{4,3}},"Planar"]

GraphData[{"Caveman",{4,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Caveman",{4,3}},{"RCN","CN"}]

GraphData[{"Caveman",{4,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{4,3}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{4,3}},"Circulant"]

GraphData[{"Caveman",{4,3}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Caveman",{4,3}},"Halin"]

GraphData[{"Caveman",{4,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Caveman",{4,3}},"Rigid"]

GraphData[{"Caveman",{4,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Caveman",{4,3}},"Flexible"]

GraphData[{"Caveman",{4,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Caveman",{4,3}},"LCF"]

GraphData[{"Caveman",{4,3}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{4,3}},"LCFSignature"]

GraphData[{"Caveman",{4,3}},"LCFNotations"]

GraphData[{"Caveman",{4,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Caveman",{4,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{4,3}}],Debug->True]//Timing

GraphData[{"Caveman",{4,3}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Caveman",{4,3}},"VertexList"],GraphData[{"Caveman",{4,3}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Caveman",{4,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Caveman",{4,3}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Caveman",{4,3}},"Matchstick"]

GraphData[{"Caveman",{4,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Caveman",{4,3}},"Edges"]]

3D All

GraphData[{"Caveman",{4,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Caveman",{4,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Caveman",{4,3}},"Polyhedral"]

GraphData[{"Caveman",{4,3}},"Graph",{"3D","Polyhedron"}]

{"Caveman", {4, 4}}

GraphData[{"Caveman",{4,4}},"StandardName"]

Primary

GraphData[{"Caveman",{4,4}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Caveman",{4,4}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{4,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{4,4}},"Edges"]

g=CavemanGraph[4,4]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Caveman",{4,4}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Caveman",{4,4}},"Graph","Degenerate"]

Bilateral

GraphData[{"Caveman",{4,4}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Caveman",{4,4}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{4,4}}],All][[All,All,1]]]

RotateGraph[First[CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{4,4}}],#]&/@hc],2Pi/16]

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

Planar

GraphData[{"Caveman",{4,4}},"Planar"]

GraphData[{"Caveman",{4,4}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Caveman",{4,4}},{"RCN","CN"}]

GraphData[{"Caveman",{4,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

g=CavemanGraph[4,4,GraphLayout->"MinimalRectilinearCrossingEmbedding"]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{4,4}},"Circulant"]

GraphData[{"Caveman",{4,4}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Caveman",{4,4}},"Halin"]

GraphData[{"Caveman",{4,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Caveman",{4,4}},"Rigid"]

GraphData[{"Caveman",{4,4}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Caveman",{4,4}},"Flexible"]

GraphData[{"Caveman",{4,4}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Caveman",{4,4}},"LCFSignature"]

GraphData[{"Caveman",{4,4}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Caveman",{4,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{4,4}}],Debug->True]//Timing

GraphData[{"Caveman",{4,4}},"Graph","UnitDistance"]//StyleGraphs

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

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Caveman",{4,4}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

gs={,,,,};

UnitDistance construction 1

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Caveman",{4,4}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

g=RotateGraph[,{8,9}]

e[l__]:=Partition[{l},2,1]
s=Sqrt[3]/2;
v={{0,0},{1,0},{1+s,-1/2},{s+1,1/2},{1+2s,0},{s+1,3/2},{s+1,3/2+2s},{s+3/2,3/2+s},{s+1/2,3/2+s},{s-1/2,3/2+s},{s-1/2-s,2+s},{s-1/2-s,1+s},{-1/2-s,3/2+s},{-1/2,s},{-1/2,-s},{-1,0}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,4,6,9,10,12,14,1,15,16,14],e[2,3,5,4],e[9,7,8,6],e[12,13,11,10],{11,12},{8,9},{3,4},{1,16}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

UnitDistanceGraphEmbeddingQ@g

UnitDistance construction 2

v=Join[c=CirclePoints[Csc[Pi/8]/2,8],
p={
Mean[c[[{4,5}]]]+{0,s},
Mean[c[[{6,7}]]]-{s,0},
Mean[c[[{1,8}]]]-{0,s},
Mean[c[[{2,3}]]]+{s,0}
},
{
p[[1]]+{1,0},
p[[2]]+{0,1},
p[[3]]-{1,0},
p[[4]]-{0,1}
}
]

e=Select[Subsets[Range[Length[v]],{2}],SquaredEuclideanDistance@@v[[#]]==1.&]

g=Graph[Range[Length[v]],UndirectedEdge@@@e,VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

Matchstick

GraphData[{"Caveman",{4,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Caveman",{4,4}},"Edges"]]

3D All

GraphData[{"Caveman",{4,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Caveman",{4,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Caveman",{4,4}},"Graph",{"3D","Polyhedron"}]

{"Caveman", {4, 5}}

GraphData[{"Caveman",{4,5}},"StandardName"]

Primary

GraphData[{"Caveman",{4,5}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{4,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{4,5}},"Edges"]

g=CavemanGraph[4,5]

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{4,5}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{4,5}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Caveman",{4,5}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{4,5}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

MinimalCrossingGraph[GraphData[{"Caveman",{4,5}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{4,5}},"Circulant"]

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

Halin

GraphData[{"Caveman",{4,5}},"Halin"]

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

Rigid

GraphData[{"Caveman",{4,5}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{4,5}},"Flexible"]

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

LCF

GraphData[{"Caveman",{4,5}},"LCF"]

GraphData[{"Caveman",{4,5}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{4,5}},"LCFSignature"]

GraphData[{"Caveman",{4,5}},"LCFNotations"]

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

UnitDistance

GraphData[{"Caveman",{4,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{4,5}}],Debug->True]//Timing

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Caveman",{4,5}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{4,5}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{4,5}},"Polyhedral"]

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

{"Caveman", {5, 3}}

GraphData[{"Caveman",{5,3}},"StandardName"]

Primary

GraphData[{"Caveman",{5,3}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{5,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{5,3}},"Edges"]

g=CavemanGraph[5,3]

EuclideanDistance@@v[[{1,6}]]//FullSimplify

Norm[v[[1]]+{0,1}]//FullSimplify

EuclideanDistance@@v[[{1,2}]]//FullSimplify

c=CirclePoints[{(NumericalApproximation[Root, (RowDefault["1.70", FEExpressionsNumericalApproximationElider]), Root[16-20 ((#1)^2)+5 ((#1)^4)&,4], ]),Pi/2},5];
v=Union[c,Mean/@Partition[c,2,1,1],CirclePoints[1+(Sqrt[2+(2/(Sqrt[5]))]),5]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[9,15,13,12,2,11,10,14,8,3,9,5],{7,13},{2,1},{6,10},{4,8}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

UnitDistanceGraphEmbeddingQ@g

Norm[v[[1]]+{0,1}]//FullSimplify

v=Join[UnitCirclePoints[10,Pi/2],CirclePoints[(1/2) (3+(Sqrt[5])),5]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[{1,10},1,13],{3,14},{5,15},{7,11},{9,12}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

gs={,,};

Degenerate

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

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

Bilateral

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

Circular

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

Planar

GraphData[{"Caveman",{5,3}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{5,3}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{5,3}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{5,3}},"Circulant"]

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

Halin

GraphData[{"Caveman",{5,3}},"Halin"]

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

Rigid

GraphData[{"Caveman",{5,3}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{5,3}},"Flexible"]

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

LCF

GraphData[{"Caveman",{5,3}},"LCF"]

GraphData[{"Caveman",{5,3}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{5,3}},"LCFSignature"]

GraphData[{"Caveman",{5,3}},"LCFNotations"]

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

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

UnitDistance

GraphData[{"Caveman",{5,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{5,3}}],Debug->True]//Timing

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Caveman",{5,3}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{5,3}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{5,3}},"Polyhedral"]

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

{"Caveman", {5, 4}}

GraphData[{"Caveman",{5,4}},"StandardName"]

Primary

GraphData[{"Caveman",{5,4}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{5,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{5,4}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{5,4}}],All][[All,All,1]]]

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{5,4}}],#]&/@hc

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{5,4}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Caveman",{5,4}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{5,4}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{5,4}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{5,4}},"Circulant"]

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

Halin

GraphData[{"Caveman",{5,4}},"Halin"]

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

Rigid

GraphData[{"Caveman",{5,4}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{5,4}},"Flexible"]

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

LCF

GraphData[{"Caveman",{5,4}},"LCFSignature"]

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

UnitDistance

GraphData[{"Caveman",{5,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{5,4}}],Debug->True]//Timing

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

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

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Caveman",{5,4}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

gs={,};

UnitDistance construction

g=CavemanGraph[5,4,GraphLayout->"UnitDistanceEmbedding"]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

Matchstick

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

3D default

Graph3D[GraphData[{"Caveman",{5,4}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

{"Caveman", {5, 5}}

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

Primary

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

All

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

Inexact

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

Embedding types

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

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

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

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

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{5,5}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

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

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

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

UnitDistance

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

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Caveman", {6, 3}}

GraphData[{"Caveman",{6,3}},"StandardName"]

Primary

GraphData[{"Caveman",{6,3}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{6,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{6,3}},"Edges"]

g=CavemanGraph[6,3]

EuclideanDistance@@v[[{5,7}]]//FullSimplify

Norm[v[[3]]+Through[{Cos,Sin}[Pi/3]]]//FullSimplify

EuclideanDistance@@v[[{3,15}]]//FullSimplify

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

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

Norm[v[[3]]+Through[{Cos,Sin}[Pi/3]]]//FullSimplify

EuclideanDistance@@v[[{3,14}]]//FullSimplify

v=Join[UnitCirclePoints[12,0],CirclePoints[{1+(Sqrt[2+(Sqrt[3])]),0},6]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[{1,12},1,13],{3,14},{5,15},{7,16},{9,17},{11,18}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

UnitDistanceGraphEmbeddingQ@g

gs={,,}

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{6,3}}],All][[All,All,1]]]

Planar

GraphData[{"Caveman",{6,3}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{6,3}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{6,3}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{6,3}},"Circulant"]

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

Halin

GraphData[{"Caveman",{6,3}},"Halin"]

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

Rigid

GraphData[{"Caveman",{6,3}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{6,3}},"Flexible"]

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

LCF

GraphData[{"Caveman",{6,3}},"LCF"]

GraphData[{"Caveman",{6,3}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{6,3}},"LCFSignature"]

GraphData[{"Caveman",{6,3}},"LCFNotations"]

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

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

UnitDistance

GraphData[{"Caveman",{6,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{6,3}}],Debug->True]//Timing

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Caveman",{6,3}},"VertexList"],GraphData[{"Caveman",{6,3}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Caveman",{6,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Caveman",{6,3}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Caveman",{6,3}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{6,3}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{6,3}},"Polyhedral"]

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

{"Caveman", {6, 4}}

GraphData[{"Caveman",{6,4}},"StandardName"]

Primary

GraphData[{"Caveman",{6,4}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{6,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{6,4}},"Edges"]

g=CavemanGraph[6,4]

RecognizeGraph[g]

g=CavemanGraph[6,4,GraphLayout->"MinimalRectilinearCrossingEmbedding"]

RecognizeGraph[g]

gs={,};

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{6,4}}],All][[All,All,1]]]

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{6,4}}],#]&/@hc

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{6,4}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Caveman",{6,4}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{6,4}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{6,4}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{6,4}},"Circulant"]

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

Halin

GraphData[{"Caveman",{6,4}},"Halin"]

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

Rigid

GraphData[{"Caveman",{6,4}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{6,4}},"Flexible"]

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

LCF

GraphData[{"Caveman",{6,4}},"LCFSignature"]

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

UnitDistance

GraphData[{"Caveman",{6,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{6,4}}],Debug->True]//Timing

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

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

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Caveman",{6,4}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData[{"Caveman",{6,4}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

gs={,,,};

UnitDistance construction

g=CavemanGraph[6,4,GraphLayout->"UnitDistanceEmbedding"]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

Matchstick

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

MinimalCrossing

GraphData[{"Caveman",{6,4}},{"RCN","CN"}]

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

Default embedding

GraphPlot@GraphData[{"Caveman",{6,4}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Caveman",{6,4}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Caveman",{6,4}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

{"Caveman", {6, 5}}

GraphData[{"Caveman",{6,5}},"StandardName"]

Primary

GraphData[{"Caveman",{6,5}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{6,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{6,5}},"Edges"]

g=CavemanGraph[6,5]

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{6,5}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{6,5}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Caveman",{6,5}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{6,5}},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{6,5}},"Circulant"]

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

Halin

GraphData[{"Caveman",{6,5}},"Halin"]

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

Rigid

GraphData[{"Caveman",{6,5}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{6,5}},"Flexible"]

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

LCF

GraphData[{"Caveman",{6,5}},"LCF"]

GraphData[{"Caveman",{6,5}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{6,5}},"LCFSignature"]

GraphData[{"Caveman",{6,5}},"LCFNotations"]

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

UnitDistance

GraphData[{"Caveman",{6,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{6,5}}],Debug->True]//Timing

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Caveman",{6,5}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{6,5}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{6,5}},"Polyhedral"]

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

{"Caveman", {7, 3}}

GraphData[{"Caveman",{7,3}},"StandardName"]

Primary

GraphData[{"Caveman",{7,3}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{7,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{7,3}},"Edges"]

g=CavemanGraph[7,3]

g=CavemanGraph[7,3,GraphLayout->"UnitDistanceEmbedding"]

EuclideanDistance@@v[[{1,8}]]//FullSimplify

EuclideanDistance@@v[[{1,18}]]//FullSimplify

v[[1,2]]+1

c=CirclePoints[{(1/(Sqrt[(1/2) (1-Sin[((3 π)/14)])])),Pi/2},7];
v=Join[c,Mean/@Partition[c,2,1,1],CirclePoints[1+(Sqrt[(2/(1-Sin[((3 π)/14)]))]),7]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,8,2,9,3,10,4,11,5,12,6,13,7,14,1,18],{2,19},{3,20},{4,21},{5,15},{6,16},{7,17}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

gs=CavemanGraph[7,3,GraphLayout->#<>"Embedding"]&/@{"UnitDistance","BisectedPolygon","Polygon"}

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{7,3}}],All][[All,All,1]]]

Planar

GraphData[{"Caveman",{7,3}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{7,3}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{7,3}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{7,3}},"Circulant"]

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

Halin

GraphData[{"Caveman",{7,3}},"Halin"]

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

Rigid

GraphData[{"Caveman",{7,3}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{7,3}},"Flexible"]

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

LCF

GraphData[{"Caveman",{7,3}},"LCF"]

GraphData[{"Caveman",{7,3}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{7,3}},"LCFSignature"]

GraphData[{"Caveman",{7,3}},"LCFNotations"]

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

UnitDistance

GraphData[{"Caveman",{7,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{7,3}}],Debug->True]//Timing

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"Caveman",{7,3}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Caveman",{7,3}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{7,3}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{7,3}},"Polyhedral"]

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

{"Caveman", {7, 4}}

GraphData[{"Caveman",{7,4}},"StandardName"]

Primary

GraphData[{"Caveman",{7,4}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{7,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{7,4}},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{7,4}}],All][[All,All,1]]]

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{7,4}}],#]&/@hc

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

Planar

GraphData[{"Caveman",{7,4}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{7,4}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{7,4}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{7,4}},"Circulant"]

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

Halin

GraphData[{"Caveman",{7,4}},"Halin"]

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

Rigid

GraphData[{"Caveman",{7,4}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{7,4}},"Flexible"]

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

LCF

GraphData[{"Caveman",{7,4}},"LCFSignature"]

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

UnitDistance

GraphData[{"Caveman",{7,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{7,4}}],Debug->True]//Timing

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

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

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Caveman",{7,4}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

gs={,,,,,};

UnitDistance construction

g=CavemanGraph[7,4,GraphLayout->"UnitDistanceEmbedding"]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

Matchstick

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

MinimalCrossing

GraphData[{"Caveman",{7,4}},{"RCN","CN"}]

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

Default embedding

GraphPlot@GraphData[{"Caveman",{7,4}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Caveman",{7,4}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Caveman",{7,4}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

{"Caveman", {7, 5}}

GraphData[{"Caveman",{7,5}},"StandardName"]

Primary

GraphData[{"Caveman",{7,5}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{7,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{7,5}},"Edges"]

g=CavemanGraph[7,5]

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{7,5}}],All][[All,All,1]]]

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

Planar

GraphData[{"Caveman",{7,5}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{7,5}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{7,5}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{7,5}},"Circulant"]

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

Halin

GraphData[{"Caveman",{7,5}},"Halin"]

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

Rigid

GraphData[{"Caveman",{7,5}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{7,5}},"Flexible"]

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

LCF

GraphData[{"Caveman",{7,5}},"LCF"]

GraphData[{"Caveman",{7,5}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{7,5}},"LCFSignature"]

GraphData[{"Caveman",{7,5}},"LCFNotations"]

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

UnitDistance

GraphData[{"Caveman",{7,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{7,5}}],Debug->True]//Timing

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Caveman",{7,5}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{7,5}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{7,5}},"Polyhedral"]

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

{"Caveman", {8, 3}}

GraphData[{"Caveman",{8,3}},"StandardName"]

Primary

GraphData[{"Caveman",{8,3}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{8,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{8,3}},"Edges"]

gs=CavemanGraph[8,3,GraphLayout->#<>"Embedding"]&/@{"UnitDistance","BisectedPolygon","Polygon"}

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{8,3}}],All][[All,All,1]]]

Planar

GraphData[{"Caveman",{8,3}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{8,3}},{"RCN","CN"}]

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

MinimalCrossingGraph[GraphData[{"Caveman",{8,3}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{8,3}},"Circulant"]

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

Halin

GraphData[{"Caveman",{8,3}},"Halin"]

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

Rigid

GraphData[{"Caveman",{8,3}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{8,3}},"Flexible"]

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

LCF

GraphData[{"Caveman",{8,3}},"LCF"]

GraphData[{"Caveman",{8,3}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{8,3}},"LCFSignature"]

GraphData[{"Caveman",{8,3}},"LCFNotations"]

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

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

UnitDistance

GraphData[{"Caveman",{8,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{8,3}}],Debug->True]//Timing

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Caveman",{8,3}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{8,3}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{8,3}},"Polyhedral"]

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

{"Caveman", {8, 4}}

GraphData[{"Caveman",{8,4}},"StandardName"]

Primary

GraphData[{"Caveman",{8,4}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{8,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{8,4}},"Edges"]

g=CavemanGraph[8,4]

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{8,4}}],All][[All,All,1]]]

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

Planar

GraphData[{"Caveman",{8,4}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{8,4}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{8,4}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{8,4}},"Circulant"]

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

Halin

GraphData[{"Caveman",{8,4}},"Halin"]

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

Rigid

GraphData[{"Caveman",{8,4}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{8,4}},"Flexible"]

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

LCF

GraphData[{"Caveman",{8,4}},"LCFSignature"]

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

UnitDistance

GraphData[{"Caveman",{8,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{8,4}}],Debug->True]//Timing

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

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

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Caveman",{8,4}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

gs={,,,};

UnitDistance construction

g=CavemanGraph[8,4,GraphLayout->"UnitDistanceEmbedding"]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

Matchstick

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

3D default

Graph3D[GraphData[{"Caveman",{8,4}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

3D Canonical

GraphData[{"Caveman",{8,4}},"Graph",{"3D","Canonical"}]

{"Caveman", {8, 5}}

GraphData[{"Caveman",{8,5}},"StandardName"]

Primary

GraphData[{"Caveman",{8,5}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{8,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{8,5}},"Edges"]

g=CavemanGraph[8,5]

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{8,5}}],All][[All,All,1]]]

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

Planar

GraphData[{"Caveman",{8,5}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{8,5}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{8,5}}]]

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

g=CavemanGraph[8,5,GraphLayout->"MinimalRectilinearCrossingEmbedding"]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{8,5}},"Circulant"]

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

Halin

GraphData[{"Caveman",{8,5}},"Halin"]

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

Rigid

GraphData[{"Caveman",{8,5}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{8,5}},"Flexible"]

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

LCF

GraphData[{"Caveman",{8,5}},"LCF"]

GraphData[{"Caveman",{8,5}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{8,5}},"LCFSignature"]

GraphData[{"Caveman",{8,5}},"LCFNotations"]

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

UnitDistance

GraphData[{"Caveman",{8,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{8,5}}],Debug->True]//Timing

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Caveman",{8,5}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{8,5}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{8,5}},"Polyhedral"]

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

{"Caveman", {9, 3}}

GraphData[{"Caveman",{9,3}},"StandardName"]

Primary

GraphData[{"Caveman",{9,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Caveman",{9,3}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{9,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{9,3}},"Edges"]

gs=CavemanGraph[9,3,GraphLayout->#<>"Embedding"]&/@{"UnitDistance","BisectedPolygon","Polygon"}

Degenerate

GraphData[{"Caveman",{9,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Caveman",{9,3}},"Graph","Degenerate"]

Bilateral

GraphData[{"Caveman",{9,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Caveman",{9,3}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{9,3}}],All][[All,All,1]]]

Planar

GraphData[{"Caveman",{9,3}},"Planar"]

GraphData[{"Caveman",{9,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Caveman",{9,3}},{"RCN","CN"}]

GraphData[{"Caveman",{9,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{9,3}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{9,3}},"Circulant"]

GraphData[{"Caveman",{9,3}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Caveman",{9,3}},"Halin"]

GraphData[{"Caveman",{9,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Caveman",{9,3}},"Rigid"]

GraphData[{"Caveman",{9,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Caveman",{9,3}},"Flexible"]

GraphData[{"Caveman",{9,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Caveman",{9,3}},"LCF"]

GraphData[{"Caveman",{9,3}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{9,3}},"LCFSignature"]

GraphData[{"Caveman",{9,3}},"LCFNotations"]

GraphData[{"Caveman",{9,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Caveman",{9,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{9,3}}],Debug->True]//Timing

GraphData[{"Caveman",{9,3}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceGraphEmbeddingQ[%]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Caveman",{9,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"Caveman",{9,3}},"Matchstick"]

GraphData[{"Caveman",{9,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Caveman",{9,3}},"Edges"]]

3D All

GraphData[{"Caveman",{9,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Caveman",{9,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Caveman",{9,3}},"Polyhedral"]

GraphData[{"Caveman",{9,3}},"Graph",{"3D","Polyhedron"}]

{"Caveman", {9, 4}}

GraphData[{"Caveman",{9,4}},"StandardName"]

Primary

GraphData[{"Caveman",{9,4}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Caveman",{9,4}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{9,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{9,4}},"Edges"]

g=CavemanGraph[9,4]

RecognizeGraph[g]

Degenerate

GraphData[{"Caveman",{9,4}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Caveman",{9,4}},"Graph","Degenerate"]

Bilateral

GraphData[{"Caveman",{9,4}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Caveman",{9,4}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{9,4}}],All][[All,All,1]]]

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{9,4}}],#]&/@hc

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{9,4}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Caveman",{9,4}},"Planar"]

GraphData[{"Caveman",{9,4}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Caveman",{9,4}},{"RCN","CN"}]

GraphData[{"Caveman",{9,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{9,4}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{9,4}},"Circulant"]

GraphData[{"Caveman",{9,4}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Caveman",{9,4}},"Halin"]

GraphData[{"Caveman",{9,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Caveman",{9,4}},"Rigid"]

GraphData[{"Caveman",{9,4}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Caveman",{9,4}},"Flexible"]

GraphData[{"Caveman",{9,4}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Caveman",{9,4}},"LCFSignature"]

GraphData[{"Caveman",{9,4}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Caveman",{9,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{9,4}}],Debug->True]//Timing

GraphData[{"Caveman",{9,4}},"Graph","UnitDistance"]//StyleGraphs

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

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Caveman",{9,4}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData[{"Caveman",{9,4}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

gs={,,,,,};

UnitDIstance construction

g=CavemanGraph[9,4,GraphLayout->"UnitDistanceEmbedding"]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

Matchstick

GraphData[{"Caveman",{9,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Caveman",{9,4}},"Edges"]]

3D All

GraphData[{"Caveman",{9,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Caveman",{9,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Caveman",{9,4}},"Graph",{"3D","Polyhedron"}]

{"Caveman", {9, 5}}

GraphData[{"Caveman",{9,5}},"StandardName"]

Primary

GraphData[{"Caveman",{9,5}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{9,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{9,5}},"Edges"]

gs={CavemanGraph[9,5],CavemanGraph[9,5,GraphLayout->"MinimalRectilinearCrossingEmbedding"]}

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{9,5}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{9,5}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

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

Length[quad]

Planar

GraphData[{"Caveman",{9,5}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{9,5}},{"RCN","CN"}]

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

Circulant

GraphData[{"Caveman",{9,5}},"Circulant"]

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

Halin

GraphData[{"Caveman",{9,5}},"Halin"]

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

Rigid

GraphData[{"Caveman",{9,5}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{9,5}},"Flexible"]

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

LCF

GraphData[{"Caveman",{9,5}},"LCF"]

GraphData[{"Caveman",{9,5}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{9,5}},"LCFSignature"]

GraphData[{"Caveman",{9,5}},"LCFNotations"]

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

UnitDistance

GraphData[{"Caveman",{9,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{9,5}}],Debug->True]//Timing

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

UnitDistance by refinement

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

LabelGraph@%

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Caveman",{9,5}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{9,5}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{9,5}},"Polyhedral"]

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

{"Caveman", {10, 3}}

GraphData[{"Caveman",{10,3}},"StandardName"]

Primary

GraphData[{"Caveman",{10,3}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{10,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{10,3}},"Edges"]

gs=CavemanGraph[10,3,GraphLayout->#<>"Embedding"]&/@{"UnitDistance","BisectedPolygon","Polygon"}

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{10,3}}],All][[All,All,1]]]

Planar

GraphData[{"Caveman",{10,3}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{10,3}},{"RCN","CN"}]

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{10,3}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{10,3}},"Circulant"]

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

Halin

GraphData[{"Caveman",{10,3}},"Halin"]

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

Rigid

GraphData[{"Caveman",{10,3}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{10,3}},"Flexible"]

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

LCF

GraphData[{"Caveman",{10,3}},"LCF"]

GraphData[{"Caveman",{10,3}},"HamiltonianCycleCount"]

GraphData[{"Caveman",{10,3}},"LCFSignature"]

GraphData[{"Caveman",{10,3}},"LCFNotations"]

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

UnitDistance

GraphData[{"Caveman",{10,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{10,3}}],Debug->True]//Timing

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData[{"Caveman",{10,3}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Caveman",{10,3}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Caveman",{10,3}},"Polyhedral"]

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

{"Caveman", {10, 4}}

GraphData[{"Caveman",{10,4}},"StandardName"]

Primary

GraphData[{"Caveman",{10,4}}]//StyleGraphs[#,ImageSize->Small]&

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Caveman",{10,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Caveman",{10,4}},"Edges"]

g=CavemanGraph[10,4]

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{10,4}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{10,4}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Caveman",{10,4}},"Planar"]

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

MinimalCrossing

GraphData[{"Caveman",{10,4}},{"RCN","CN"}]

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

MinimalCrossingGraph[GraphData[{"Caveman",{10,4}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Caveman",{10,4}},"Circulant"]

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

Halin

GraphData[{"Caveman",{10,4}},"Halin"]

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

Rigid

GraphData[{"Caveman",{10,4}},"Rigid"]

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

Flexible

GraphData[{"Caveman",{10,4}},"Flexible"]

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

LCF

GraphData[{"Caveman",{10,4}},"LCFSignature"]

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

UnitDistance

GraphData[{"Caveman",{10,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Caveman",{10,4}}],Debug->True]//Timing

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

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

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Caveman",{10,4}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

gs={,,,,,,,,};

UnitDistance construction

g=CavemanGraph[10,4,GraphLayout->"UnitDistanceEmbedding"]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

Matchstick

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

3D default

Graph3D[GraphData[{"Caveman",{10,4}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

{"Caveman", {10, 5}}

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

Primary

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

All

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

Inexact

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

Embedding types

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

Default embedding

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

gs=CavemanGraph[10,5,GraphLayout->#<>"Embedding"]&/@{"Clique","MinimalRectilinearCrossing"}

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Caveman",{10,5}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Caveman",{10,5}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

bilat

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

quad

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

MinimalCrossingGraph[GraphData[{"Caveman",{10,5}}]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

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

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

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

GraphData

GraphClassString

GraphData["Caveman*"]

GraphClassString[GraphData["Caveman*"]]

GraphClassString[DeleteCases[GraphData["Caveman*"],{"Caveman",{_,3}}]]

GraphDataString

file=OpenWrite["~/caveman.m"]

Do[WriteString[file,GraphDataString[CavemanGraph[n,k],
"StandardName"->{"Caveman",{n,k}},
"Name"->"("<>ToString[n]<>","<>ToString[k]<>")-caveman graph",
"Information"->"CavemanGraph",
Debug->True,
TimeConstraint->60
]],{n,3,10},{k,3,5}]

Close[file]