Starfish Graph

Author

Eric W. Weisstein
July 26, 2026

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

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

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

Figure

GraphicsGrid[
Partition[
StyleGraphs[
GraphData["StarfishGraph","Graph","All"]
],
UpTo[4]
],
Dividers->All
]

Embeddings

Primary

GraphData["StarfishGraph"]//StyleGraphs

All

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

Robertson construction

v=Join[CirclePoints[15],CirclePoints[2,5]];
g=Graph[Range[Length[v]],UndirectedEdge@@@Sort[Join[Sort/@Table[{i,Mod[i+3,15,1]},{i,15}],{{6,17},{7,18},{8,18},{9,18},{5,17},{4,17},{1,16},{2,16},{3,16},{13,20},{14,20},{15,20},{10,19},{11,19},{12,19}}]],VertexCoordinates->v,VertexLabels->"Name"]

RecognizeGraph[g]

We say a cubic graph G is cyclically k-connected, for k ≥ 1 an integer, if G has girth ≥ k, and |δG(X)| ≥ k for every X ⊆ V(G) such that both X and V(G)\X include the vertex set of a circuit of G.

Let us say that G is theta-connected if G is cubic and cyclically five-connected, and |δG(X)| ≥ 6 for all X ⊆ V(G) with |X|,|V(G)\X| ≥ 7.  (If G is cubic with girth at least five, and X ⊆ V (G) includes the vertex set of a circuit, then either |δG(X)| ≥ 5 or |X| ≥ 7; so this definition is equivalent to the condition in the abstract.)

VertexCount[g]

CubicGraphQ[g]

GirthByCycles[g]

CrossingNumber[g,MaxIterations->10^3]//AbsoluteTiming

LCF

GraphData["StarfishGraph","LCF"]

GraphData["StarfishGraph","|HC|"]

GraphData["StarfishGraph","LCFSignature"]

GraphData["StarfishGraph","LCFNotations"]

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

UnitDistance

GraphData["StarfishGraph","UnitDistance"]

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

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

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

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData["StarfishGraph","Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData["StarfishGraph","Matchstick"]

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

MinimalCrossing

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

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

Default embedding

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

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData["StarfishGraph"],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData["StarfishGraph"],TimeConstraint->60]//AbsoluteTiming

MinimalCrossingGraph[GraphData["StarfishGraph"],"CrossingNumber"->4]

3D default

Graph3D[GraphData["StarfishGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["StarfishGraph","Polyhedral"]

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

GraphData

GraphDataString

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

WriteString[file,GraphDataString[g,
"StandardName"->"StarfishGraph",
"Name"->"starfish graph",
TimeConstraint->60,
Debug->True,
"Skip"->{"Arboricity"}
]]

Close[file]