Optimal parallel algorithms on planar graphs

Few existing parallel graph algorithms achieve optimality when applied to very sparse graphs such as planar graphs. We describe optimal PRAM algorithms for the connected components, spanning tree, biconnected components, and strong orientation problems that work on classes of undirected graphs including planar graphs and graphs of bounded genus. The running times achieved for n-vertex input graphs are O(log n) on the CRCW PRAM and O(log n log ∗ n) on the EREW PRAM. We also give (non-optimal) randomized EREW PRAM algorithms using O(log n) time and n processors, and non-uniform deterministic EREW PRAM algorithms using O(log n) time and O(n 2) processors.

Authors

• Torben Hagerup

Keywords

No keywords are indexed for this paper.