Upward Spirality and Upward Planarity Testing

A digraph is upward planar if it admits a planar drawing where all edges are monotone in the upward direction. It is known that the problem of testing a digraph for upward planarity is NP-complete in general. This paper describes an $O(n^4)$-time upward planarity testing algorithm for all digraphs that have a series-parallel structure, where n is the number of vertices of the input. This significantly enlarges the family of digraphs for which a polynomial-time testing algorithm is known. Furthermore, the study is extended to general digraphs, and a fixed parameter tractable algorithm for upward planarity testing is described, whose time complexity is $O(d^t \cdot t \cdot n^3 + d \cdot t^2 \cdot n + d^2 \cdot n^2)$ where t is the number of triconnected components of the digraph and d is an upper bound on the diameter of any split component of the digraph. Our results use the new notion of upward spirality that, informally speaking, is a measure of the “level of winding” that a triconnected component of a digraph G can have in an upward planar drawing of G.