A curvy graph is a graph 
whose rectilinear
crossing number is strictly greater than its graph
crossing number,
 |
The term "curvy graph" is coined here. The inequality means that allowing non-rectilinear graph edges reduces the minimum possible
number of crossings. Equivalently, no crossing-minimum graph
embedding of 
is a straight line embedding.
A curvy graph is called minimally curvy if none of its proper subgraphs is curvy. Since 
for every graph 
, this is equivalent to requiring 
for every proper subgraph 
of 
.
The smallest simple graphs that are curvy have graph order 8. The four such graphs are summarized below.
Minimal crossing and rectilinear crossing embeddings
for the 16-cell graph and complete
graph 
are illustrated above (Harary and Hill 1962-1963).
| graph |  |  | minimally curvy |
16-cell graph  | 6 | 8 | yes |
 -Turán graph | 9 | 10 | no |
| 8-double-toroidal graph 8 | 9 | 10 | yes |
complete graph  | 18 | 19 | no |
The 
-Turán
graph and 
contain the 16-cell graph as a proper subgraph,
whereas 8-double-toroidal graph 8 does not.
Therefore, exactly two of the four graphs in the table are minimally curvy. It remains
open whether any cubic graph is curvy (Pegg 2019,
Schaefer 2026, p. 86).
Despite the similar name, a curvy graph should not be confused with the surface-topological curve graph.
