Two fixed-parameter tractable algorithms for testing upward planarity

In this paper we consider the problem of testing an arbitrary digraph G = (V, E) for upward planarity. In particular we describe two fixed-parameter tractable algorithms for testing the upward planarity of G. The first algorithm that we present can test the upward planarity of G in O(2^t · t! · V|²)-time where t is the number of triconnected components of G. The second algorithm that we present uses a standard technique known as kernelisation and can test the upward planarity of G in O(|V ² + k⁴ · (2k)!)-time, where k = E -|V|.