Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth

Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann +3

Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth…