Curvy Graph

Author

Eric W. Weisstein
August 25, 2026

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

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

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

Examples

<<MathWorld`Graphs`

GraphData["Curvy"]

Select[DeleteCases[
GraphData[#,{"#","CN","RCN"}]&/@GraphData["Connected",;;9],
{_,_Missing,_}|{_,_,_Missing}
],
#[[2]]<#[[3]]&
]

Length[%]

Graphs[9,{10,11}]

Graphs[9,{269087,269089,269102}]

CrossingNumber[]

RectilinearCrossingNumber[]

IsomorphicSubgraphQ[GraphData[#],]&/@{"SixteenCellGraph",{"DoubleToroidal",{8,8}}}

Curvy

curvy=SortBy[
Cases[
DeleteCases[
{#,GraphData[#,"CN"],GraphData[#,"RCN"]}&/@GraphData["Connected"],
{_,x_,x_}
],
{_,_Integer,_Integer}
],
Last
]

Minimally curvy

GraphData[RecognizeGraph[#],"Graph","MinimalCrossing"][[1]]&/@SubgraphMinimalGraphs[GraphData/@curvy[[All,1]]]

RecognizeGraph/@%

Figures

K8

Minimal crossing

gs=Annotate[#,{VertexSize->{"Scaled",.03},VertexStyle->LightDarkSwitched@Black,EdgeStyle->LightDarkSwitched@Black}]&/@Join[
GraphData[{"Complete",8},"Graph","MinimalCrossing",PlotLabel->"CN == 18"],
GraphData[{"Complete",8},"Graph","MinimalRectilinearCrossing",PlotLabel->"RCN == 19"]
]

bug(478174): GraphicsRow[{g}] offsets vertices from their actual locations for graphs with curved edges

GraphicsRow[
GraphCrossingDiagram/@gs,Dividers->All,
BaseStyle->{
InsetBoxOptions->{BaseStyle->FontFamily->"Times"}},
ImageSize->700
]

All

GraphicsGrid[
Reverse@Transpose@Outer[
Annotate[
StyleGraphs@GraphData[#,"Graph",#2][[1]],
With[
{
label=Switch[#2,"MinimalRectilinearCrossing","rcn","MinimalCrossing","cn"],
not=GraphData[#,"Notation"]
},
PlotLabel->Column[{
If[MissingQ[not],Style[GraphData[#,"Name"],Italic],not/.s_String?LetterQ:>Style[s,Italic]],
Row[{label,"==",GraphData[#,ToUpperCase[label]]}," "]
},
Alignment->Center]
]
]&,
{"SixteenCellGraph",(*{"CompleteKPartite",{1,1,2,2,2}},*){"DoubleToroidal",{8,8}},{"Complete",8}},
{"MinimalRectilinearCrossing","MinimalCrossing"},
1
],
Alignment->Bottom,Dividers->All,BaseStyle->{InsetBoxOptions->{BaseStyle->Directive[14,FontFamily->"Times"]}}]

Possibly curvy

"Ilypq\Vfw"

<<MathWorld`Graphs`

g=ImportString["Ilypq\\Vfw","Graph6"]

RecognizeGraph@g

Options[FindRectilinearCrossingNumber]

FindRectilinearCrossingNumber[g,Debug->True,MaxIterations->10^6]//AbsoluteTiming

Options[RectilinearCrossingNumber]

RectilinearCrossingNumber[g,MaxIterations->10^6]//AbsoluteTiming

FindCrossingNumber[g,TimeConstraint->10]//AbsoluteTiming

CrossingNumber[g,Method->"WebCompute"]//AbsoluteTiming

Curvy chains

1

curvy=ImportString[#,"Graph6"]&/@{"I}nnnp^Nw","IRl~}zl{w","IrS}|~lzg","I^zDZm^Vw","I}urHt^jw","IxO{}v{^o","Ilypq\\Vfw"}

VertexCount/@curvy

RecognizeGraph/@curvy

RegularGraphQ/@curvy

All seven newly confirmed graphs form a successive one-edge-deletion chain beginning with
\[
\overline{C_{10}}\cong\operatorname{Ci}_{10}(1,2,4,5).
\]I}nnnp^Nw          complement of C10
   ↓ delete one edge
IRl~}zl{w
   ↓
IrS}|~lzg
   ↓
I^zDZm^Vw
   ↓
I}urHt^jw
   ↓
IxO{}v{^o
   ↓
Ilypq\Vfw
Therefore every new confirmed graph is a spanning subgraph of \(\overline{C_{10}}\), retaining all ten vertices. The separately listed \(K_{10}\) is only the known control and is unrelated to this deletion chain.

small=ImportString["Ilypq\Vfw","Graph6"]

FindCrossingNumber[small,Debug->True,TimeConstraint->10]//AbsoluteTiming

CrossingNumber[small,Debug->True,TimeConstraint->10]//AbsoluteTiming

FindRectilinearCrossingNumber[small,Debug->True,ProgressReporting->True,TimeConstraint->20,"Restarts"->1000]//AbsoluteTiming

RectilinearCrossingNumber[small,Debug->True,TimeConstraint->20,"Restarts"->1000]//AbsoluteTiming

{"CycleComplement", 10} is curvy

<<MathWorld`Graphs`

GraphData[{"CycleComplement",10},{"CN","RCN"}]

CrossingNumber[GraphData[{"CycleComplement",10}],Debug->True]//Timing

CrossingNumber[GraphData[{"CycleComplement",10}],Method->"Exact",Debug->True]//Timing

RectilinearCrossingNumber[GraphData[{"CycleComplement",10}],Debug->True,TimeConstraint->60]//AbsoluteTiming

g=FindRectilinearCrossingGraph[GraphData[{"CycleComplement",10}]]

GraphCrossingCount@g

t is proved curvy by combining two independent certificates:
Ordinary crossing number: an OGDF topological drawing with 15 crossings was retained. A separate no-OGDF validator verified every subdivided edge path, all 15 alternating crossing vertices, the rotation system, connectivity, and Euler planarity. Thus  

\operatorname{CN}(G)\le 15.

Rectilinear crossing number: the order-type encoding proved that no straight-line drawing with at most 15 crossings exists. Kissat produced a DRAT proof, independently verified by drat-trim. Thus  

\operatorname{RCN}(G)\ge 16.

Therefore

\operatorname{CN}(G)\le15<16\le\operatorname{RCN}(G),

so it is definitely curvy. Presently, CN is bounded by 11–15 and RCN by 16–17; neither exact value is known.
It is not yet known to be minimally curvy. We checked all 35 single-edge deletions and all 10 vertex deletions and obtained validated ordinary-CN upper-bound drawings, but that does not prove those deletions are noncurvy. To establish minimality, we still need to show every edge-deleted graph has equal ordinary and rectilinear crossing numbers—or otherwise prove it is noncurvy. No known smaller curvy proper subgraph has been found inside it so far.