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 = broken vertical bar V broken vertical bar, 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 2)-time. The previously known best result is an O(t! (.) 8(t) (.) n(3) + 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(2) + k(4) (2k + 1)!) time, where k = broken vertical bar E broken vertical bar - broken vertical bar V broken vertical bar. We also define a class of non upward planar digraphs.