Jaws Graph

Author

Eric W. Weisstein
July 26, 2026

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

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

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

Figure

GraphicsGrid[
Partition[
StyleGraphs[
GraphData["JawsGraph","Graph","All"]
],
UpTo[3]
],
Dividers->All
]

Embeddings

Primary

GraphData["JawsGraph","Graph"]//StyleGraphs

All

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

Halin

GraphData["JawsGraph","Halin"]

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

LCF

GraphData["JawsGraph","LCF"]

GraphData["JawsGraph","LCFSignature"]

GraphData["JawsGraph","LCFNotations"]

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

UnitDistance

GraphData["JawsGraph","UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

g=RotateGraph[LabelGraph@IndexGraph@,{2,19}]

gs={,};

Matchstick

GraphData["JawsGraph","Matchstick"]

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

MinimalCrossing

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

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

Default embedding

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

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

RecognizeGraph[g]

MinimalCrossing construction

g=RotateGraph[MinimalCrossingGraph[GraphData["JawsGraph"],"CrossingNumber"->2]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData["JawsGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["JawsGraph","Polyhedral"]

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

Construction

Robertson et al. 2019

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

RecognizeGraph[g]

VertexCount[g]

CubicGraphQ[g]

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

AlmostPlanarGraphQ[g]//Timing

StringReplace[ExportString[g,"Graph6"],">>graph6<<"|"\n"->""]

MinimalRectilinearCrossing

g=MinimalCrossingGraph[g,"CrossingNumber"->2]

quads=AdjacencyList[g,#]&/@{21,22}

Pairs[l_]:=Module[{twos={l[[1]],#}&/@Rest[l]},
{#,Complement[l,#]}&/@twos
]

p1=Pairs[quads[[1]]]

p2=Pairs[quads[[2]]]

combs=Flatten[#,1]&/@Flatten[Outer[List,p1,p2,1],1]

Length[combs]

g0=Graph[Range[20],Select[EdgeList[g],FreeQ[#,21|22]&],VertexCoordinates->Take[GraphEmbedding[g],20]]

gs=EdgeAdd[g0,UndirectedEdge@@@#]&/@combs

GraphPlot/@Pick[gs,IsomorphicGraphQ[#,jaws]&/@gs]

Rotate[,2.1]

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

IsomorphicGraphQ[g,jaws]

RectilinearCrossingCount@g

ToCommonEdges[g,jaws]

GraphData

GraphDataString

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

WriteString[file,GraphDataString[g,
"StandardName"->"JawsGraph",
"Name"->"jaws graph",
"EmbeddingClasses"->{{"Degenerate","Primary"}},
TimeConstraint->10,
Debug->True,
"Skip"->{"Arboricity"}
]]

Close[file]