Given a planar graph G and an integer b, OrthogonalPlanarity is the problem of deciding whether G admits an orthogonal drawing with at most b bends in total. We show that OrthogonalPlanarity can be solved in polynomial time if G has bounded treewidth. Our proof is based on an FPT algorithm whose parameters are the number of bends, the treewidth and the number of degree-2 vertices of G. This result is based on the concept of sketched orthogonal representation that synthetically describes a family of equivalent orthogonal representations. Our approach can be extended to related problems such as HV-Planarity and FlexDraw. In particular, both OrthogonalPlanarity and HV-Planarity can be decided in time for series-parallel graphs, which improves over the previously known bounds.

Sketched Representations and Orthogonal Planarity of Bounded Treewidth Graphs

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

Abstract

Given a planar graph G and an integer b, OrthogonalPlanarity is the problem of deciding whether G admits an orthogonal drawing with at most b bends in total. We show that OrthogonalPlanarity can be solved in polynomial time if G has bounded treewidth. Our proof is based on an FPT algorithm whose parameters are the number of bends, the treewidth and the number of degree-2 vertices of G. This result is based on the concept of sketched orthogonal representation that synthetically describes a family of equivalent orthogonal representations. Our approach can be extended to related problems such as HV-Planarity and FlexDraw. In particular, both OrthogonalPlanarity and HV-Planarity can be decided in time for series-parallel graphs, which improves over the previously known bounds.
2019
978-3-030-35801-3
978-3-030-35802-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/1457395
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact