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.