Abstract
We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC^1 (UL ∩ co-UL), which is contained in AC 2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^10 n) (corresponding to the complexity class AC^10 ⊆ NC^11). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.