Coarse Grained Parallel Graph Planarity Testing.
Edson N. Cáceres, Albert P.C. Chan, Frank Dehne, Siang Wun Song · 2000
We present a coarse grained parallel algorithm for planarity testing and planar embedding. The algorithm requires O(log² p) communication rounds and linear sequential work per round. It assumes that the local memory per processor, N/p, is larger than p for some fixed > 0. This assumption is true for all commercially available multiprocessors. Our result implies a BSP algorithm with O(log² p) supersteps, O(g log² (p) N/p ) communication, and O(log² (p) N/p ) local computation. Our algorithm is based on the general structure of a previous PRAM method presented by Klein, using a parallel implementation of PQ-trees. The main contribution of this paper lies in the study of many of the individual PRAM steps that are very inefficient on existing commercial parallel machines. We present non-trivial, efficient, CGM implementations of the various parts of the overall strategy proposed by Klein. Our main result is a parallel planarity testing algorithm which is much more practical and efficient on commercially available multiprocessors.