TR19-091 Authors: Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe

Publication: 8th July 2019 02:37

Downloads: 1217

Keywords:

In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses $O(n^{1/2+\epsilon})$ space. A critical ingredient of their algorithm is a polynomial-time, $\tldO(\sqrt{n})$-space algorithm to compute a separator of a planar graph. The conference version provided a sketch of the algorithm and many nontrivial details were left unexplained. In this work, we provide a detailed construction of their algorithm.