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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.