Beyond Outerplanarity

Abstract

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 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 ⌊3.5 √k⌋-degenerate, and consequently that every √outer k-planar graph can be colored with ⌊3.5 √k⌋ + 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 3-quasi-planar graphs and the class of planar graphs are incomparable.

Finally, we restrict outer k-planar and outer k-quasi-planar drawings to full drawings (where no crossing appears on the boundary of the outer face) and to 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 closed outer k-planarity and closed outer k-quasi-planarity in extended monadic second-order logic. Since every outer k-planar graph has treewidth O(k), 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.