Dart Graph

Author

Eric W. Weisstein
July 4, 2024

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

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

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

Embeddings

<<MathWorld`Graphs`

"DartGraph"

Names

GraphData["DartGraph","StandardName"]

GraphData["DartGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["DartGraph","EdgeList"]]

Default embedding

GraphPlot[GraphData["DartGraph","Edges"],GraphLayout->"LayeredEmbedding"]

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

RecognizeGraph[g]

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

RecognizeGraph@g

Degenerate

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

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

Configuration

GraphData["DartGraph","Configuration"]

GraphData["DartGraph","Graph","Configuration"]//StyleGraphs

Perspective

GraphData["DartGraph","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["DartGraph","Polyhedron"]

HoneycombToroidal construction

GraphData["DartGraph","NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData["DartGraph","Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData["DartGraph","Graph","IGraph"]//StyleGraphs

Bilateral

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

Circular

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

Circular construction

GraphData["DartGraph","Hamiltonian"]

GraphData["DartGraph","HamiltonianCycleCount"]

Planar

GraphData["DartGraph","Planar"]

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

MinimalCrossing

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

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

Circulant

GraphData["DartGraph","Circulant"]

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

Circulant construction

GraphData["DartGraph","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["DartGraph"]])//Timing

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

compl=GraphData["DartGraph","ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Line graph

GraphData["DartGraph","Line"]

LineGraphQ[GraphData["DartGraph"]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== "DartGraph"&]

RootGraph[GraphData["DartGraph"]]

RecognizeGraph[%]

Halin

GraphData["DartGraph","Halin"]

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

Rigid

GraphData["DartGraph","Rigid"]

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

Flexible

GraphData["DartGraph","Flexible"]

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

LCF

GraphData["DartGraph","LCF"]

GraphData["DartGraph","HamiltonianCycleCount"]

GraphData["DartGraph","LCFSignature"]

GraphData["DartGraph","LCFNotations"]

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

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

UnitDistance

GraphData["DartGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData["DartGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["DartGraph","Matchstick"]

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

3D default

Graph3D[GraphData["DartGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["DartGraph","Polyhedral"]

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

3D Canonical

GraphData["DartGraph","Graph",{"3D","Canonical"}]

"DartComplementGraph"

Names

GraphData["DartComplementGraph","StandardName"]

GraphData["DartComplementGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["DartComplementGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData["DartComplementGraph","Configuration"]

GraphData["DartComplementGraph","Graph","Configuration"]//StyleGraphs

Perspective

GraphData["DartComplementGraph","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["DartComplementGraph","Polyhedron"]

HoneycombToroidal construction

GraphData["DartComplementGraph","NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData["DartComplementGraph","Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData["DartComplementGraph","Graph","IGraph"]//StyleGraphs

Bilateral

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

Circular

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

Circular construction

GraphData["DartComplementGraph","Hamiltonian"]

GraphData["DartComplementGraph","HamiltonianCycleCount"]

Planar

GraphData["DartComplementGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

(cn=CrossingNumber[GraphData["DartComplementGraph"],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["DartComplementGraph"],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["DartComplementGraph"],TimeConstraint->5 3600])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["DartComplementGraph"],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["DartComplementGraph","Circulant"]

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

Circulant construction

GraphData["DartComplementGraph","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["DartComplementGraph"]])//Timing

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

compl=GraphData["DartComplementGraph","ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

DegenerateGraphEmbeddingTypes/@gs

Line graph

GraphData["DartComplementGraph","Line"]

LineGraphQ[GraphData["DartComplementGraph"]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== "DartComplementGraph"&]

RootGraph[GraphData["DartComplementGraph"]]

RecognizeGraph[%]

Halin

GraphData["DartComplementGraph","Halin"]

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

Rigid

GraphData["DartComplementGraph","Rigid"]

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

Flexible

GraphData["DartComplementGraph","Flexible"]

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

LCF

GraphData["DartComplementGraph","LCF"]

GraphData["DartComplementGraph","HamiltonianCycleCount"]

GraphData["DartComplementGraph","LCFSignature"]

GraphData["DartComplementGraph","LCFNotations"]

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

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

UnitDistance

GraphData["DartComplementGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData["DartComplementGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["DartComplementGraph","Matchstick"]

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

3D default

Graph3D[GraphData["DartComplementGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["DartComplementGraph","Polyhedral"]

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

3D Canonical

GraphData["DartComplementGraph","Graph",{"3D","Canonical"}]

GraphData

Subjects

GraphClassString["DartGraph"]

Matrices

GraphDataMatrices["DartGraph"]