Testing Upward Planarity of Partial $2$-Trees

Abstract

We present an $O(n^2)$-time algorithm to test whether an $n$-vertex directed partial $2$-tree is upward planar. This result improves upon the previously best known algorithm, which runs in $O(n^4)$ time.

Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)