Monotone Drawings of $k$-Inner Planar Graphs

Abstract

A $k$-inner planar graph is a planar graph that has a plane drawing with at most $k$ {internal vertices}, i.e., vertices that do not lie on the boundary of the outer face of its drawing. An outerplanar graph is a $0$-inner planar graph. In this paper, we show how to construct a monotone drawing of a $k$-inner planar graph on a $2(k+1)n\times 2(k+1)n$ grid. In the special case of an outerplanar graph, we can produce a planar monotone drawing on a $n\times n$ grid, improving previously known results.

Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018). Revised introduction