Greenfield Graph

Author

Eric W. Weisstein
June 4, 2023

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

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

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

Source

https://digital.wpi.edu/concern/student_works/nk322f836?locale=en

Greenfield, K.B.  "The Fixing Number of a Graph."  B.S. thesis.  Worcester, MA: Worcester Polytechnic Institute, 2011.

Embeddings

<<MathWorld`Graphs`

Names

GraphData["GreenfieldGraph","StandardName"]

GraphData["GreenfieldGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["GreenfieldGraph","EdgeList"]]

Default embedding

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

v=Union@@(Subdivide[Sequence@@#,3]&/@Partition[CirclePoints[3],2,1,1]);
v=Join[v,Mean[v[[#]]]&/@{{4,6},{5,7},{2,3}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[8,3,5,9,7,6,1,4,2,8],e[4,10,6],e[5,11,7],e[3,12,2]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

v[[5,2]]-2RegionDistance[Line@v[[{4,6}]],v[[5]]]//FullSimplify

v=Join[UnitCirclePoints[9],CirclePoints[(1/2) Csc[(π/9)]-2 Sin[(π/9)],3]];
g=Graph[Range@Length@v,Sort[Sort/@(UndirectedEdge@@@{e[{1,9},1],e[7,12,9],e[6,11,4],e[1,10,3]})],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

UnitDistanceGraphEmbeddingQ@g

v=Join[CirclePoints[9]];
v=Join[v,Mean[v[[#]]]&/@{{4,6},{7,9},{1,3}}];
g=Graph[Range@Length@v,Sort[Sort/@(UndirectedEdge@@@{e[{1,9},1],e[6,10,4],e[1,12,3],e[7,11,9]})],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

gs={,,};

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData["GreenfieldGraph"],All][[All,All,1]]]

Planar

GraphData["GreenfieldGraph","Planar"]

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

MinimalCrossing

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

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

Circulant

GraphData["GreenfieldGraph","Circulant"]

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

Line graph

GraphData["GreenfieldGraph","Line"]

LineGraphQ[GraphData["GreenfieldGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["GreenfieldGraph"]]

Halin

GraphData["GreenfieldGraph","Halin"]

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

Rigid

GraphData["GreenfieldGraph","Rigid"]

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

Flexible

GraphData["GreenfieldGraph","Flexible"]

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

LCF

GraphData["GreenfieldGraph","LCF"]

GraphData["GreenfieldGraph","HamiltonianCycleCount"]

GraphData["GreenfieldGraph","LCFSignature"]

GraphData["GreenfieldGraph","LCFNotations"]

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

UnitDistance

GraphData["GreenfieldGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance construction

LabelGraph@(g0=)

s=1/Sqrt[2];
v={{1/2,0},{2s-x+1/2,h-y},{2s,h},{s,h+s},{0,h+2s},{-s,h+s},{-2s,h},{-(2s-x+1/2),h-y},{-1/2,0},{x,y},{0,h},{-x,y}};

eqn=UnitEdgeEquations[v,EdgeList[g0]]//FullSimplify//Union

var=Variables[Subtract@@@eqn]

soln=Solve[Join[eqn,{x==1/2}],var,PositiveReals]//FullSimplify

gs=Graph[Range@Length@v,EdgeList[g0],VertexCoordinates->(v/.#)]&/@soln

gs={,,,,};

RecognizeGraph/@gs

UnitDistanceGraphEmbeddingQ/@gs

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

gs={,,,RotateGraph[,Pi/2]}

Matchstick

GraphData["GreenfieldGraph","Matchstick"]

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

3D default

Graph3D[GraphData["GreenfieldGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["GreenfieldGraph","Polyhedral"]

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

GraphData

GraphClassString

GraphDataClassString["GreenfieldGraph"]

GraphDataString

file=OpenWrite["~/greenfield.m"]

WriteString[file,GraphDataString[,
"StandardName"->"GreenfieldGraph",
"Name"->"Greenfield graph",
"FixingNumber"->3]]

Close[file]