A minimally curvy graph is a curvy graph 
none of whose proper topological
minors is a curvy graph. Since 
for every graph 
, this is equivalent to requiring 
for every proper topological
minor 
of 
.
In particular, a graph subdivision that is a
curvy graph is not minimally curvy if it subdivides
another curvy graph.
Minimal crossing and rectilinear crossing drawings for these two graphs are illustrated above. Since no graph of graph order less than 8 is
a curvy graph, 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. The 16-cell
graph and 8-double-toroidal graph 8
have no proper subgraphs that are curvy
graphs. They are therefore the only minimally curvy graphs of order at most 8,
up to graph isomorphism. The 16-cell
graph 
has crossing number 6 and rectilinear
crossing number 8. The 8-double-toroidal
graph 8 has crossing number 9 and rectilinear crossing number 10.
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
that is a curvy graph, other than the 16-cell
graph itself, is not a minimally curvy graph. This includes 
and 
.
There also exist minimally curvy graphs with crossing number 4, so the two order-8 examples do not exhaust the minimally curvy graphs.
Bienstock and Dean (1993) constructed graphs with crossing
number 4 and arbitrarily large rectilinear
crossing number. The Hernández-Vélez-Leaños-Salazar
graphs give an explicit construction (Hernández-Vélez et al.
2017, Theorem 2). Choose a curvy graph 
from this construction and let 
be minimal among the topological
minors of 
that are curvy graphs. Then 
is minimally curvy. Since crossing
number does not increase when taking a topological
minor, 
has crossing number at most 4. It cannot
have crossing number at most 3, since in
that case its rectilinear crossing number
would equal its crossing number (Bienstock
and Dean 1993). Hence 
has crossing number
4 and is distinct from both order-8 examples.
