An efficient parallel algorithm for planarity

摘要

We describe a parallel algorithm for testing a graph for planarity, and for finding an embedding of a planar graph. For a graph on n vertices, the algorithm runs in O(log2n) steps on n processors of a parallel RAM. The previous best parallel algorithm for planarity testing also ran in O(log2n) time (J. Ja'Ja' and J. Simon, J Comput.11, No. 2 (1982), 313–328), but used a reduction to solving linear systems, and hence required processors, where M(n) is the sequential time for n × n matrix multiplication, whereas our processor bounds are within a polylog factor of optimal. The most significant aspect of our parallel algorithms is the use of a sophisticated data structure for representing sets of embeddings, the PQ-tree of K. Booth and G. Lueker, J. Comput. System Sci.13, No. 3 (1976), 335–379). Previously no parallel algorithms for PQ-trees were known. We have efficient parallel algorithms for manipulating PQ-trees, which we use in our planarity algorithm.