  We study straight-line drawings of graphs where the vertices are placed in
convex position in the plane, i.e., \emph{convex drawings}. We consider two
families of graph classes with convex drawings: \emph{outer $k$-planar} graphs,
where each edge is crossed by at most $k$ other edges; and, \emph{outer
$k$-quasi-planar} graphs where no $k$ edges can mutually cross.
  We show that the outer $k$-planar graphs are
$\lfloor3.5\sqrt{k}\rfloor$-degenerate, and consequently that every outer
$k$-planar graph can be colored with $\lfloor3.5\sqrt{k}\rfloor + 1$ colors. We
further show that every outer $k$-planar graph has a balanced vertex separator
of size at most $2k+3$. For each fixed $k$, these small balanced separators
allow us to test outer $k$-planarity in quasi-polynomial time, e.g., this
implies that none of these recognition problems is NP-hard unless the
Exponential Time Hypothesis fails. We also show that the class of outer
$k$-quasi-planar graphs and the class of planar graphs are incomparable.
  Finally, we restrict outer $k$-planar and outer $k$-quasi-planar drawings to
\emph{full} drawings (where no crossing appears on the boundary of the outer
face) and to \emph{closed} drawings (where the vertex sequence on the boundary
of the outer face is a Hamiltonian cycle in the graph). For each $k$, we
express \emph{closed outer $k$-planarity} and \emph{closed outer
$k$-quasi-planarity} in \emph{extended monadic second-order logic}. Due to a
result of Wood and Telle (New York J. Math., 2007) every outer $k$-planar graph
has treewidth at most $3k+11$. Thus, Courcelle's theorem implies that closed
outer $k$-planarity is linear time testable. We leverage this result to further
show that full outer $k$-planarity can also be tested in linear time.
