Drawing outer-1-planar graphs revisited
Vol. 26, no. 1, pp. 59-73, 2022. Regular paper.
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.

 This work is licensed under the terms of the CC-BY license.
Submitted: September 2020.
Reviewed: August 2021.
Revised: October 2021.
Accepted: December 2021.
Final: January 2022.
Published: January 2022.
Communicated by Michael Kaufmann
article (PDF)