Parallel Transitive Closure and Point Location in Planar Structures
Authors:
- Roberto TamassiaRTRoberto Tamassia
- Jeffrey S. VitterJVJeffrey S. Vitter
- 1 August 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 20 (4) , 708-725
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.
Keywords
This publication has 44 references indexed in Scilit:
- Cascading Divide-and-Conquer: A Technique for Designing Parallel AlgorithmsSIAM Journal on Computing, 1989
- Algorithms for plane representations of acyclic digraphsTheoretical Computer Science, 1988
- Optimal Point Location in a Monotone SubdivisionSIAM Journal on Computing, 1986
- A linear algorithm for embedding planar graphs using PQ-treesJournal of Computer and System Sciences, 1985
- A new point-location algorithm and its practical efficiency: comparison with existing algorithmsACM Transactions on Graphics, 1984
- Representing a planar graph by vertical lines joining different levelsDiscrete Mathematics, 1983
- Parallel Algorithms in Graph Theory: Planarity TestingSIAM Journal on Computing, 1982
- A dichromatic framework for balanced trees1978
- On the vector representation of the reachability in planar directed graphsInformation Processing Letters, 1975
- Organization and maintenance of large ordered indexesActa Informatica, 1972