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)


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)