AN OPTIMAL PARALLEL ALGORITHM FOR PLANAR CYCLE SEPARATORS

We present an optimal parallel algorithm For computing a cycle separat or of an n-vertex embedded planar undirected graph in O(log n) time on n/log n processors. As a consequence, we also obtain an improved para llel algorithm for constructing a depth-first search tree rooted at an y given vertex in a connected planar undirected graph in O(log(2) n) t ime bn n/log n processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time c omplexities, but with n processors. Our algorithms run on a parallel r andom access machine that permits concurrent reads and concurrent writ es in its shared memory and allows an arbitrary processor to succeed i n case of a write conflict.