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. The four such graphs are 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 is called minimally curvy if none of its proper topological minors is curvy. Since 
for every graph 
, this is equivalent to requiring 
for every proper topological
minor 
of 
. In particular, a curvy graph
subdivision of another curvy graph is not minimally curvy.
Since no graph of graph order less than 8 is curvy, a curvy graph of graph order 8 is minimally curvy iff it contains no other curvy graph of graph order 8 as a proper subgraph.
Minimal crossing and rectilinear crossing embeddings for the minimally curvy 16-cell graph and 8-double-toroidal graph 8 are illustrated above.
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 and is not yet known to be minimally curvy.
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 curvy complete
multipartite graph satisfying this inequality,
other than the 16-cell graph itself, is not minimally
curvy. This includes 
and 
in the table above. By contrast, 8-double-toroidal graph 8 does not contain the
16-cell graph as a proper subgraph.
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.
