Crossed Dodecahedral Graph

Author

Eric W. Weisstein
June 27, 2024

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

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

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

Figure

Brandenburg, F.~J.  ``Straight-Line Drawings of 1-Planar Graphs.''  3 Sep 2021.  https://arxiv.org/abs/2109.01692

Import["/Users/eww/Downloads/arXiv-2109.01692v1/Xdodecaeder.pdf"][[1]]

Embeddings

<<MathWorld`Graphs`

Names

GraphData["CrossedDodecahedralGraph","StandardName"]

GraphData["CrossedDodecahedralGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["CrossedDodecahedralGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData["CrossedDodecahedralGraph","Configuration"]

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

Perspective

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

Projection construction

Manipulate[ProjectionGraph[GraphData["CrossedDodecahedralGraph","Graph",{"3D"}],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

ProjectionGraph[GraphData["CrossedDodecahedralGraph","Graph","3D"],{0,.01,.01}]

ProjectionGraph[GraphData["CrossedDodecahedralGraph","Graph","3D"],{0,0,1}]

DegenerateGraphEmbeddingTypes@

DegenerateGraphEmbeddingTypes[%]

ProjectionGraph[GraphData["CrossedDodecahedralGraph","Graph","3D"],{0,1,0}]

DegenerateGraphEmbeddingTypes[%]

ProjectionGraph[GraphData["CrossedDodecahedralGraph","Graph","3D"],{1,0.01,0}]

ProjectionGraph[GraphData["CrossedDodecahedralGraph","Graph","3D"],{1,1,0}]

ProjectionGraph[GraphData["CrossedDodecahedralGraph","Graph","3D"],{1,0,1,-Pi/2}]

ProjectionGraph[GraphData["CrossedDodecahedralGraph","Graph","3D"],{1,1,1}]

gs={,,,};

HoneycombToroidal construction

GraphData["CrossedDodecahedralGraph","NotationRules","HoneycombToroidal"]

GeneralizedPetersen

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

IGraph

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

Bilateral

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

Circular

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

Planar

GraphData["CrossedDodecahedralGraph","Planar"]

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

MinimalLocalCrossing

Brandenburg, F.~J.  ``Straight-Line Drawings of 1-Planar Graphs.''  3 Sep 2021.  https://arxiv.org/abs/2109.01692

GraphData["CrossedDodecahedralGraph","LocalCrossingNumber"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData["CrossedDodecahedralGraph"],"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["CrossedDodecahedralGraph","Circulant"]

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

Complement graph

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

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

gs=GraphComplement/@%

Line graph

GraphData["CrossedDodecahedralGraph","Line"]

LineGraphQ[GraphData["CrossedDodecahedralGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["CrossedDodecahedralGraph"]]

Halin

GraphData["CrossedDodecahedralGraph","Halin"]

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

Rigid

GraphData["CrossedDodecahedralGraph","Rigid"]

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

Flexible

GraphData["CrossedDodecahedralGraph","Flexible"]

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

LCF

GraphData["CrossedDodecahedralGraph","LCF"]

GraphData["CrossedDodecahedralGraph","HamiltonianCycleCount"]

GraphData["CrossedDodecahedralGraph","LCFSignature"]

GraphData["CrossedDodecahedralGraph","LCFNotations"]

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

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

LCF compute random

FindRandomLCFNotation[GraphData["CrossedDodecahedralGraph"],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData["CrossedDodecahedralGraph"],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"NoncayleyTransitive",{20,41}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"NoncayleyTransitive",{20,41}}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

LCF compute 10^8

Tally[(lcf=LCF[GraphData[{"NoncayleyTransitive",{20,41}}],10^8])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

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

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

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

Length[gs]

gs

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

Length[gs]

gs

LCF compute all

Divisors[GraphData["CrossedDodecahedralGraph","V"]]

Length[FindHamiltonianCycle[GraphData["CrossedDodecahedralGraph"],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData["CrossedDodecahedralGraph"],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["CrossedDodecahedralGraph",".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

i=0;
gs={};
t0=AbsoluteTime[];
count=Length[order2];
Monitor[
Do[
If[!MissingQ[g=BilateralLCFGraph[LCFGraph@@order2[[i]]]],AppendTo[gs,g]],
{i,count}
],
Column[{
ProgressIndicator[i,{1,count}],
Row[{i,"/",count}],
Row[{"estimated time remaining: ",Round[(AbsoluteTime[]-t0) (count/i-1)]," s"}],
Row[{Length[gs]," bilateral graphs"}]
}]
];//Timing

UnitDistance

GraphData["CrossedDodecahedralGraph","UnitDistance"]

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

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

UnitDistance by refinement

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

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

LabelGraph@

DegenerateGraphEmbeddingTypes@

gs={RotateGraph[,{5,12}],RotateGraph[,{2,6}],RotateGraph[,{9,10}]}

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData["CrossedDodecahedralGraph","Matchstick"]

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

3D default

Graph3D[GraphData["CrossedDodecahedralGraph","Edges"]]

3D construction

v=PolyhedronData["Dodecahedron","VertexCoordinates"];

ee=Union[Sort/@Flatten[Subsets[#,{2}]&/@PolyhedronData["Dodecahedron","Faces","List"],1]]

g=Graph[Range[20],UndirectedEdge@@@ee,VertexCoordinates->v]

RecognizeGraph@g

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["CrossedDodecahedralGraph","Polyhedral"]

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

Construction

ee=Union[Sort/@Flatten[Subsets[#,{2}]&/@GraphData["DodecahedralGraph","Faces"],1]]

g=Graph[Range[20],UndirectedEdge@@@ee,VertexCoordinates->GraphData["DodecahedralGraph","VertexCoordinates"],VertexLabels->Automatic]

RecognizeGraph@g

gs=Graph[Range[20],UndirectedEdge@@@ee,VertexCoordinates->#,VertexLabels->Automatic]&/@GraphData["DodecahedralGraph","Embeddings"]

Select[gs,(!DegenerateGraphEmbeddingQ[#])&]

gs=UnlabelGraph/@{,,,,,,,}

Head/@gs

GraphData

GraphDataClassString

GraphDataClassString["CrossedDodecahedralGraph"]