|
Abstract : |
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. Key words. parallel algorithms, parallel computation, graph algorithms, planar st-graphs, transitive closure, reachability, planar point location, computational geometry, fractional cascading, graph drawing, visibility AMS(MOS) subject classi cations. 68E05, 68C05, 68C25 1. Introduction. Planar st-graphs, |
