Depth-first search in directed planar graphs, revisited

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 had a runtime of O(log ^10n) (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.