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 drawing
of 
is a straight
line drawing.
The two minimum-crossing drawings 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 complete multipartite graph 
contains the 16-cell
graph 
as a subgraph iff
 |
Necessity follows because each part can contribute at most two vertices to such a subgraph. Conversely, choose eight vertices,
at most two from each part. Each pair chosen from the same part forms a part of 
. Pair the singly chosen vertices and delete the matching
joining those pairs. Thus every complete
multipartite graph satisfying this inequality,
other than the 16-cell graph itself, contains a
smaller curvy subgraph and therefore cannot be a minimally curvy graph. This includes 
and 
.
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.
