TWO FIXED-PARAMETER TRACTABLE ALGORITHMS FOR TESTING UPWARD PLANARITY
Patrick Joseph Healy, Karol Lynch · International Journal of Foundations of Computer Science · 2006
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(2t · t! · |V|2)-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|2 + k4 · (2k)!)-time, where k = |E| - |V|.