Optimal parallel algorithms for transitive closure and point location in planar structures
Roberto Tamassia, Jeffrey Scott Vitter · 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.