An O(n½+?)-Space and Polynomial-Time Algorithm for Directed Planar Reachability
Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe · 2013
We show that the reach ability problem over {\em directed planar graphs} can be solved simultaneously in polynomial time and approximately $O(\sqrt{n})$ space. In contrast, the best space bound known for the reach ability problem on general directed graphs with polynomial running time is $O(n/2^{\sqrt{\log n}})$.