Tech Report CS-89-20

Optimal Parallel Algorithms for Transitive Closure and Point Location in Planar Structures

Roberto Tamassia and Jeffrey Scott Vitter

January 1989


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)