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)