Comparison of Maximal Upward Planar Subgraph Computation Algorithms.

A digraph G=(V, E) is \textit{upward planar} if it has a planar drawing with all edges pointing upward. A sub graph \tildeG of a digraph G with an upward planar drawing is called a {\it maximal upward planar sub graph} of G if the addition of any edge in G\backslash\tildeG to \tildeG causes non-upward planarity. Binucci \emph{et al.} showed that finding even the maximum upward planar sub graph of an embedded digraph G\phi is NP-Complete \cite{Walter07}. In this paper, we compare different algorithms to find maximal upward planar sub graph of an embedded digraph. We also use a large test suite of embedded digraphs to gain a deeper understanding of upward planarity and see how the different heuristics perform in practice. [ABSTRACT FROM PUBLISHER]