Upward spirality and upward planarity testing

The upward planarity testing problem is known to be NP-hard. We describe an O(n4)-time upward planarity testing and embedding algorithm for the class of digraphs that do not contain rigid triconnected components. We also present a new FPT algorithm that solves the upward planarity testing and embedding problem for general digraphs.