2022/08/26 by Steven Chaplick, Emilio Di Giacomo, Chaplick, Steven +9
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.2208.12548
We present an O(n2)-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(n4) time.