Harries Graph

Author

Eric W. Weisstein
November 1, 2023

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

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

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

Embeddings

<<MathWorld`Graphs`

Names

GraphData["HarriesGraph","StandardName"]

GraphData["HarriesGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["HarriesGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Perspective

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

Perspective construction

GraphData["HarriesGraph","Polyhedron"]

Bilateral

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

Circular

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

Planar

GraphData["HarriesGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

cn=55;

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["HarriesGraph","Circulant"]

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

Complement graph

GraphData["HarriesGraph","ComplementGraph","Name"]

Line graph

GraphData["HarriesGraph","Line"]

LineGraphQ[GraphData["HarriesGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["HarriesGraph"]]

Halin

GraphData["HarriesGraph","Halin"]

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

Rigid

GraphData["HarriesGraph","Rigid"]

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

Flexible

GraphData["HarriesGraph","Flexible"]

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

LCF

GraphData["HarriesGraph","LCF"]

GraphData["HarriesGraph","HamiltonianCycleCount"]

GraphData["HarriesGraph","LCFSignature"]

GraphData["HarriesGraph","LCFNotations"]

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

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

LCF compute all

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

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

UnitDistance

GraphData["HarriesGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["HarriesGraph","Matchstick"]

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

3D default

Graph3D[GraphData["HarriesGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["HarriesGraph","Polyhedral"]

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

Properties

Matrices

GraphDataMatrices["HarriesGraph"]

Quit

Table

TableForm[GraphDataTable["HarriesGraph",x],TableDepth->2]//TraditionalForm

Automorphisms using Combinatorica (the *long* way!)

Automorphisms[CombinatoricaGraph["HarriesGraph"]]//Timing

GraphData

GraphClassString

GraphClassString["HarriesGraph"]