An efficient parallel algorithm for planarity


Journal Article

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 Ω(M(n) log2n) 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. © 1988.

Full Text

Duke Authors

Cited Authors

  • Klein, PN; Reif, JH

Published Date

  • January 1, 1988

Published In

Volume / Issue

  • 37 / 2

Start / End Page

  • 190 - 246

Electronic International Standard Serial Number (EISSN)

  • 1090-2724

International Standard Serial Number (ISSN)

  • 0022-0000

Digital Object Identifier (DOI)

  • 10.1016/0022-0000(88)90006-2

Citation Source

  • Scopus