# Tech Report CS-89-45

## Parallel Transitive Closure and Point Location in Planar Structures

### Abstract:

We present parallel algorithms for several graph and geometric problems, including transitive closure and topological sorting in planar {\em 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.

(complete text in pdf)