Orthogonal planarity testing of bounded treewidth graphs

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.