Parallelism and the maximal path problem

The maximal path problem is the following: Given a graph G = (V, E) and a vertex r, find a path starting at r that cannot be extended without encountering a node that is already on the path. We shall show that if all nodes have degree at most D(n), the problem can be solved in O(D(n) log³ n) time using O(n²) processors. We also obtain an NC algorithm for the maximal path problem in planar graphs. Finally, we show that the problem of computing the lexicographically minimal maximal path is P-complete, even when restricted to planar graphs.