Parallel Algorithms for Depth-First Searches I. Planar Graphs

Abstract

This paper presents an unbounded-parallel algorithm for performing a depth-first search of a planar undirected graph. The algorithm uses $O(n^4 )$ processors and executes in $O(\log ^3 n)$-time. It had previously been conjectured that the problem of computing a depth-first spanning tree was inherently sequential.