Given a graph G and an integer b, ORTHOGONALPLANARITY is the problem of testing whether G admits a planar orthogonal drawing with at most b bends. ORTHOGONALPLANARITY is known to be NP-complete. We show that this problem belongs to the XP class when parameterized by treewidth. The proof exploits a fixed-parameter tractable approach that uses two more parameters besides treewidth, namely the natural parameter b and the number of vertices with degree at most two of G. Such approach is based on the new concept of sketched orthogonal representation, which synthetically describes a family of equivalent orthogonal drawings. The approach is general enough to be applicable to other related problems, namely HV-PLANARITY and FLEXDRAW. Also, in the special case of series-parallel graphs we obtain that both ORTHOGONALPLANARITY and HV-PLANARITY can be solved in O(n3log⁡n) time, which improves on the previous O(n4) bounds for these two.

Orthogonal planarity testing of bounded treewidth graphs

Di Giacomo E.;Liotta G.;Montecchiani F.
2022

Abstract

Given a graph G and an integer b, ORTHOGONALPLANARITY is the problem of testing whether G admits a planar orthogonal drawing with at most b bends. ORTHOGONALPLANARITY is known to be NP-complete. We show that this problem belongs to the XP class when parameterized by treewidth. The proof exploits a fixed-parameter tractable approach that uses two more parameters besides treewidth, namely the natural parameter b and the number of vertices with degree at most two of G. Such approach is based on the new concept of sketched orthogonal representation, which synthetically describes a family of equivalent orthogonal drawings. The approach is general enough to be applicable to other related problems, namely HV-PLANARITY and FLEXDRAW. Also, in the special case of series-parallel graphs we obtain that both ORTHOGONALPLANARITY and HV-PLANARITY can be solved in O(n3log⁡n) time, which improves on the previous O(n4) bounds for these two.
2022
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/1501320
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 10
social impact