Tech Report CS-89-45

Parallel Transitive Closure and Point Location in Planar Structures

Roberto Tamassia and Jeffrey S. Vitter

October 1989 (revised June 1990)

Abstract:

We present parallel algorithms for several graph and geometric problems, including transitive closure and topological sorting in planar {\em st}-graphs, preprocessing planar subdivisions for point location queries, and construction of visibility representations and drawings of planar graphs. Most of these algorithms achieve optimal $O( \log n)$ running time using $ n / \log n $ processors in the EREW PRAM model, $n$ being the number of vertices.

(complete text in pdf)