A graph is rectilinear planar if it admits a planar orthogonal drawing without bends. While testing rectilinear planarity is NP-hard in general, 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(n2log 2n) -time algorithm to test rectilinear planarity of partial 2-trees, which improves over the current best bound of O(n3log n). Moreover, for series-parallel graphs where no two parallel-components 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 in 1998 to describe how much an orthogonal drawing of a subgraph is rolled-up in an orthogonal drawing of the graph.

Rectilinear Planarity of Partial 2-Trees

Didimo W.;Liotta G.;Ortali G.
2023

Abstract

A graph is rectilinear planar if it admits a planar orthogonal drawing without bends. While testing rectilinear planarity is NP-hard in general, 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(n2log 2n) -time algorithm to test rectilinear planarity of partial 2-trees, which improves over the current best bound of O(n3log n). Moreover, for series-parallel graphs where no two parallel-components 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 in 1998 to describe how much an orthogonal drawing of a subgraph is rolled-up in an orthogonal drawing of the graph.
2023
978-3-031-22202-3
978-3-031-22203-0
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1553149
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact