Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00581
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
|
Journal Supporters
|