EFFICIENT PARALLEL ALGORITHM FOR PLANARITY.
A parallel algorithm for testing a graph for planarity and for finding an embedding of a planar graph is described. For a graph on n vertices, the algorithm runs in O(log**2 n) steps on n processors of a parallel RAM. The previous best algorithm for planarity testing in parallel polylog time used a reduction to solving linear systems, and hence required OMEGA (n**2 **. **4 **9 **. **. **. ) processors by known methods, whereas the present processor bounds are within a polylog factor of optimal. The most significant aspect of the algorithm is the use of a sophisticated data structure for representing sets of embeddings, called the PQ-tree. Efficient parallel algorithms for manipulating PQ-trees were developed for use in the planarity algorithm.
