ECCC-Report TR19-091https://eccc.weizmann.ac.il/report/2019/091Comments and Revisions published for TR19-091en-usMon, 08 Jul 2019 02:37:15 +0300
Paper TR19-091
| A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs |
Ryo Ashida,
Tatsuya Imai,
Kotaro Nakagawa,
A. Pavan,
Vinodchandran Variyam,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2019/091In [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.Mon, 08 Jul 2019 02:37:15 +0300https://eccc.weizmann.ac.il/report/2019/091