Planar Strong Connectivity Helps in Parallel Depth-First Search
Ming‐Yang Kao · SIAM Journal on Computing · 1995
This paper proves that for a strongly connected planar directed graph of size n, a depth-first search tree rooted at a specified vertex can be computed in $O(\log^{5} n)$ time with $n/ \log n$ processors. Previously, for planar directed graphs that may not be strongly connected, the best depth-first search algorithm runs in $O(\log^{10} n)$ time with n processors. Both algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes in its shared memory, and in case of a write conflict, permits an arbitrary processor to succeed.