A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs

This paper presents a parallel algorithm for constructing depth first spanning trees in planar graphs. The algorithm takes $O(\log ^2 n)$ time with $O(n)$ processors on a concurrent read concurrent write parallel random access machine (PRAM). The best previously known algorithm for the problem takes $O(\log ^3 n)$ time with $O(n^4 )$ processors on a PRAM. Our algorithm is within an $O(\log ^2 n)$ factor of optimality.