Tech Report CS-89-20
Optimal Parallel Algorithms for Transitive Closure and Point Location in Planar Structures
Roberto Tamassia and Jeffrey Scott Vitter
We present parallel algorithms for several graph and geometric problems, including transitive closure and topological sorting in planar $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 with $n / log n$ processors in the EREW PRAM model.
(complete text in pdf)