Journal Article

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.

Duke Authors

Cited Authors

  • Klein, PN; Reif, JH

Published Date

  • December 1, 1986

Published In

Start / End Page

  • 465 - 477

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus