Domino Graph

Author

Eric W. Weisstein
September 28, 2024

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

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

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

Embeddings

<<MathWorld`Graphs`

Names

GraphData["DominoGraph","StandardName"]

GraphData["DominoGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["DominoGraph"]]

Default embedding

GraphPlot[Graph[GraphData["DominoGraph","VertexList"],GraphData["DominoGraph","Edges"]]]

GraphPlot[Graph[GraphData["DominoGraph","VertexList"],GraphData["DominoGraph","Edges"]]]

vec=Through[{Cos,Sin}[-30Degree]];
v={{0,0},{0,1},vec,vec+{0,1},{-1,1}vec,{-1,1}vec+{0,1}};
g=Graph[Range@Length@v,UndirectedEdge@@@{e[5,1,3,4,2,6,5],{1,2}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

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

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

Configuration

GraphData["DominoGraph","Configuration"]

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

Incidence

GraphData["DominoGraph","Incidence"]

Select[GraphData[All],GraphData[#,"LeviGraph","Name"]==="DominoGraph"&]

lines=GraphData["DominoGraph","IncidenceLines"]

Perspective

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

HoneycombToroidal construction

GraphData["DominoGraph","NotationRules","HoneycombToroidal"]

GeneralizedPetersen

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

IGraph

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

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData["DominoGraph","Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

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

Circular construction

GraphData["DominoGraph","Hamiltonian"]

GraphData["DominoGraph","HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData["DominoGraph"],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData["DominoGraph"],#]&/@hc);//Timing

sym={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[sym[[All,-1]]]

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

gs=bilat

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

quad

Planar

GraphData["DominoGraph","Planar"]

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

Planar construction

PlanarGraphEmbedding[GraphData["DominoGraph"],Method->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData["DominoGraph"]],10]

PlanarGraphEmbeddings

(plemb=PlanarGraphEmbeddings[GraphData["DominoGraph"]])//Timing

Length[plemb]

GraphData["DominoGraph","PlanarEmbeddingCount"]

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

(cn=CrossingNumber[GraphData["DominoGraph"],TimeConstraint->86400])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["DominoGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData["DominoGraph","V"]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["DominoGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData["DominoGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["DominoGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData["DominoGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["DominoGraph","Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData["DominoGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["DominoGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData["DominoGraph"],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["DominoGraph","V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData["DominoGraph","Circulant"]

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

Circulant construction

GraphData["DominoGraph","NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData["DominoGraph","Line"]

LineGraphQ[GraphData["DominoGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["DominoGraph"]]

RecognizeGraph[%]

Halin

GraphData["DominoGraph","Halin"]

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

Rigid

GraphData["DominoGraph","Rigid"]

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

Flexible

GraphData["DominoGraph","Flexible"]

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

LCF

GraphData["DominoGraph","LCF"]

GraphData["DominoGraph","HamiltonianCycleCount"]

GraphData["DominoGraph","LCFSignature"]

GraphData["DominoGraph","LCFNotations"]

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

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

UnitDistance

GraphData["DominoGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["DominoGraph","Matchstick"]

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

3D default

Graph3D[GraphData["DominoGraph","Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["DominoGraph","Polyhedral"]

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

GraphData

Subjects

GraphClassString["DominoGraph"]

Matrices

GraphDataMatrices["DominoGraph"]

Construction

Circular

g=Graph[Range[6],UndirectedEdge@@@Join[Partition[Range[6],2,1,1],{{2,5}}],VertexCoordinates->CirclePoints[Csc[Pi/6]/2,6],VertexLabels->"Name"]

r=RecognizeGraph[g]

EdgeLengths[g]

Grid

rg=RecognizeGraph[GridGraph[2,3]]

GraphData[{"Ladder",3},"AllImages"]