Sketched Representations and Orthogonal Planarity of Bounded Treewidth Graphs

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 $O(n^3\log n)$ time for series-parallel graphs, which improves over the previously known $O(n^4)$ bounds.

Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)