Skip to main content
Journal cover image

An efficient parallel algorithm for planarity

Publication ,  Journal Article
Klein, PN; Reif, JH
Published in: Journal of Computer and System Sciences
January 1, 1988

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.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Journal of Computer and System Sciences

DOI

EISSN

1090-2724

ISSN

0022-0000

Publication Date

January 1, 1988

Volume

37

Issue

2

Start / End Page

190 / 246

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 0806 Information Systems
  • 0805 Distributed Computing
  • 0802 Computation Theory and Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Klein, P. N., & Reif, J. H. (1988). An efficient parallel algorithm for planarity. Journal of Computer and System Sciences, 37(2), 190–246. https://doi.org/10.1016/0022-0000(88)90006-2
Klein, P. N., and J. H. Reif. “An efficient parallel algorithm for planarity.” Journal of Computer and System Sciences 37, no. 2 (January 1, 1988): 190–246. https://doi.org/10.1016/0022-0000(88)90006-2.
Klein PN, Reif JH. An efficient parallel algorithm for planarity. Journal of Computer and System Sciences. 1988 Jan 1;37(2):190–246.
Klein, P. N., and J. H. Reif. “An efficient parallel algorithm for planarity.” Journal of Computer and System Sciences, vol. 37, no. 2, Jan. 1988, pp. 190–246. Scopus, doi:10.1016/0022-0000(88)90006-2.
Klein PN, Reif JH. An efficient parallel algorithm for planarity. Journal of Computer and System Sciences. 1988 Jan 1;37(2):190–246.
Journal cover image

Published In

Journal of Computer and System Sciences

DOI

EISSN

1090-2724

ISSN

0022-0000

Publication Date

January 1, 1988

Volume

37

Issue

2

Start / End Page

190 / 246

Related Subject Headings

  • Computation Theory & Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 0806 Information Systems
  • 0805 Distributed Computing
  • 0802 Computation Theory and Mathematics