We study straight-line drawings of graphs where the vertices are placed in convex position in the plane, i.e., convex drawings. We consider two families of graph classes with nice convex drawings: outer $k$-planar graphs, where each edge is crossed by at most $k$ other edges; and, outer $k$-quasi-planar graphs where no $k$ edges can mutually cross.

We show that the outer $k$-planar graphs are $(\lfloor\sqrt{4k+1}\rfloor+1)$-degenerate, and consequently that every outer $k$-planar graph can be $(\lfloor\sqrt{4k+1}\rfloor+2)$-colored, and this bound is tight. We further show that every outer $k$-planar graph has a balanced 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, i.e., none of these recognition problems are NP-complete unless ETH fails.

For the outer $k$-quasi-planar graphs we discuss the edge-maximal graphs which have been considered previously under different names. We also construct planar 3-trees that are not outer $3$-quasi-planar.

Finally, we restrict outer $k$-planar and outer $k$-quasi-planar drawings to closed drawings, where the vertex sequence on the boundary is a cycle in the graph. For each $k$, we express closed outer $k$-planarity and closed outer $k$-quasi-planarity in extended monadic second-order logic. Thus, since outer $k$-planar graphs have bounded treewidth, closed outer $k$-planarity is linear-time testable by Courcelle's Theorem.

This is joint work with M. Kryven, G. Liotta, A. Löffler, and A. Wolff.