Fixed-parameter tractable algorithms for testing upward planarity

We consider the problem of testing a digraph G = (V, E) for upward planarity. In particular we present two fixed-parameter tractable algorithms for testing the upward planarity of G. Let n -|V|, let t be the number of triconnected components of G, and let c be the number of cut-vertices of G. The first upward planarity testing algorithm we present runs in O(2^t · t! · n²)-time. The previously known best result is an O(t! · 8^t · n³ + 2^3.2c · t^3.2c · t! · 8^t · n)-time algorithm by Chan. We use the kernelisation technique to develop a second upward planarity testing algorithm which runs in O(n² + K ⁴(2k +1)!) time, where k = |E| - |V|. We also define a class of non upward planar digraphs.