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.
The two minimum-crossing graph embeddings for the curvy complete graph 
(which has graph crossing
number 18 but rectilinear crossing
number 19) illustrated above were given by Harary and Hill (1962-1963).
The smallest simple graphs that are curvy have graph order 8. Up to graph isomorphism, there are exactly four, summarized in the table below.
| graph |  |  |
16-cell
graph  | 6 | 8 |
 | 9 | 10 |
| 8-double-toroidal graph 8 | 9 | 10 |
complete graph  | 18 | 19 |
A curvy graph that contains no curvy proper topological minor is a minimally curvy graph.
The cycle complement graph 
is also curvy, with 
and 
. Six successive single-edge
deletions give a chain of seven curvy graphs, the smallest of which has 29 edges. This smallest graph has
graph order 10 and 
, but it is not yet known to be a minimally
curvy graph.
The 16-cell graph is a curvy sextic graph and the cycle complement graph 
is a curvy septic
graph, but 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.
