Drawing outer-1-planar graphs revisited

Abstract

In a recent article (Auer et al., Algorithmica 2016) it was claimed that every outer-1-planar graph has a planar visibility representation of area $O(n\log n)$. In this paper, we show that this is wrong: There are outer-1-planar graphs that require $\Omega(n^2)$ area in any planar drawing. Then we give a construction (using crossings, but preserving a given outer-1-planar embedding) that results in an orthogonal box-drawing with $O(n\log n)$ area and at most two bends per edge.