### Revision(s):

__
Revision #2 to TR20-074 | 15th September 2021 03:09
__
#### Depth-First Search in Directed Planar Graphs, Revisited

**Abstract:**
We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC^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, which is contained in NC^11).

We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.

**Changes to previous version:**
The title has changed. More details and clarifications are provided in several places.

__
Revision #1 to TR20-074 | 11th April 2021 13:58
__
#### Depth-First Search in Directed Graphs, Revisited

**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 intersect 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, which is contained in NC^11).

We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.

**Changes to previous version:**
The upper bound is weaker; there was an error in Lemmma 27 of the previous version.

### Paper:

__
TR20-074 | 6th May 2020 21:14
__

#### Depth-First Search in Directed Graphs, Revisited

**Abstract:**
We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC^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, which is contained in NC^11).

We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.

### Comment(s):

__
Comment #1 to TR20-074 | 11th April 2021 17:24
__
#### Lemma 27 in the initial ECCC version is incorrect.

**Comment:**
Lemma 27 is incorrect in the initial version of the paper is incorrect. We are posting a new version with a weaker upper bound.