Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR19-091 | 7th July 2019 22:33

A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs

TR19-091
Authors: Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, Vinodchandran Variyam, Osamu Watanabe
Publication: 8th July 2019 02:37
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.