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$.
Upward Spirality and Upward Planarity Testing
DIDIMO, WALTER;GIORDANO, FRANCESCO;LIOTTA, Giuseppe
2009
Abstract
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$.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
