Paw Graph

Author

Eric W. Weisstein
October 30, 2024

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/PawGraph.nb.

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

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

Embeddings

<<MathWorld`Graphs`

Names

GraphData["PawGraph","StandardName"]

GraphData["PawGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["PawGraph"]]

Default embedding

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

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

RecognizeGraph@g

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

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

Degenerate

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

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

GeneralizedPetersen

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

IGraph

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

Bilateral

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

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

Circular

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

Circular construction

GraphData["PawGraph","Hamiltonian"]

GraphData["PawGraph","LCF"]

GraphData["PawGraph","HamiltonianCycleCount"]

Planar

GraphData["PawGraph","Planar"]

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

Planar construction

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

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

PlanarGraphEmbeddings

GraphData["PawGraph","PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData["PawGraph"],Debug->True])//Timing

Length[plemb]

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["PawGraph","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["PawGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

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

GraphData["PawGraph","Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData["PawGraph","Circulant"]

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

Circulant construction

GraphData["PawGraph","NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData["PawGraph","Line"]

LineGraphQ[GraphData["PawGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["PawGraph"]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

GraphData["PawGraph","Halin"]

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

Rigid

GraphData["PawGraph","Rigid"]

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

Flexible

GraphData["PawGraph","Flexible"]

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

LCF

GraphData["PawGraph","LCF"]

GraphData["PawGraph","HamiltonianCycleCount"]

GraphData["PawGraph","LCFSignature"]

GraphData["PawGraph","LCFNotations"]

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

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

UnitDistance

GraphData["PawGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["PawGraph","Matchstick"]

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

3D default

Graph3D[GraphData["PawGraph","Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["PawGraph","Polyhedral"]

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

GraphData

GraphDataClassString

GraphDataClassString["PawGraph"]

GraphMatrixPlot

GraphMatrixPlot[GraphData@"PawGraph"]