Parallel Transitive Closure and Point Location in Planar Structures

Authors:
  • RTRoberto Tamassia
    Roberto Tamassia
  • JVJeffrey S. Vitter
    Jeffrey S. Vitter

Abstract
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, n being the number of vertices.

This publication has 44 references indexed in Scilit: