Parallel Transitive Closure and Point Location in Planar Structures

R. Tamassia and J. S. Vitter. ``Parallel Transitive Closure and Point Location in Planar Structures,'' SIAM Journal on Computing, 20(4), August 1991, 708-725. A shortened version appears in ``Optimal Parallel Algorithms for Transitive Closure and Point Location in Planar Structures,'' Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '89), Sante Fe, N. M., June 1989, 399-408. Also appears as an invited paper in Proceedings of the International Workshop on Discrete Algorithms and Complexity, Fukuoka, Japan, November 1989, 169-178.

Full text but no figures (gzip-compressed postscript)

Full text but no figures (Adobe pdf format)

Parallel algorithms for several graph and geometric problems are presented, 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 using $n/\log n$ processors in the EREW PRAM model, nbeing the number of vertices.