Special issue on Selected papers from the Thirtieth International Symposium on Graph Drawing and Network Visualization, GD 2022
Rectilinear Planarity of Partial 2-Trees
Vol. 27, no. 8, pp. 679-719, 2023. Regular paper.
Abstract A graph is rectilinear planar if it admits a planar orthogonal drawing without bends. While testing rectilinear planarity is NP-hard in general (Garg and Tamassia, 2001), it is a long-standing open problem to establish a tight upper bound on its complexity for partial 2-trees, i.e., graphs whose biconnected components are series-parallel. We describe a new $O(n^2)$-time algorithm to test rectilinear planarity of partial 2-trees, which improves over the current best bound of $O(n^3 \log n)$ (Di Giacomo et al., 2022). Moreover, for partial 2-trees where no two parallel-components in a biconnected component share a pole, we are able to achieve optimal $O(n)$-time complexity. Our algorithms are based on an extensive study and a deeper understanding of the notion of orthogonal spirality, introduced several years ago (Di Battista et al., 1998) to describe how much an orthogonal drawing of a subgraph is rolled-up in an orthogonal drawing of the graph.

 This work is licensed under the terms of the CC-BY license.
Submitted: November 2022.
Reviewed: March 2023.
Revised: April 2023.
Accepted: August 2023.
Final: August 2023.
Published: November 2023.
article (PDF)