Testing Upward Planarity of Partial $2$-Trees
Authors:
- Steven ChaplickSCSteven Chaplick
- Emilio Di GiacomoEGEmilio Di Giacomo
- Fabrizio FratiFFFabrizio Frati
- Robert GanianRGRobert Ganian
- Chrysanthi N. RaftopoulouCRChrysanthi N. Raftopoulou
- Kirill SimonovKSKirill Simonov
Preprint
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.