Testing Upward Planarity of Partial $2$-Trees

Authors:
  • SCSteven Chaplick
    Steven Chaplick
  • EGEmilio Di Giacomo
    Emilio Di Giacomo
  • FFFabrizio Frati
    Fabrizio Frati
  • RGRobert Ganian
    Robert Ganian
  • CRChrysanthi N. Raftopoulou
    Chrysanthi N. Raftopoulou
  • KSKirill Simonov
    Kirill Simonov

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.
All Related Versions