Skip to main content
Journal cover image

Planarity testing in parallel

Publication ,  Journal Article
Ramachandran, V; Reif, J
Published in: Journal of Computer and System Sciences
January 1, 1994

We present a parallel algorithm based on open ear decomposition to construct an embedding of a graph onto the plane or report that the graph is nonplanar. Our parallel algorithm runs on a CRCW PRAM in logarithmic time with a number of processors bounded by that needed for finding connected components in a graph and for performing bucket sort. © 1994 by Academic Press, Inc.

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, 1994

Volume

49

Issue

3

Start / End Page

517 / 561

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
Ramachandran, V., & Reif, J. (1994). Planarity testing in parallel. Journal of Computer and System Sciences, 49(3), 517–561. https://doi.org/10.1016/S0022-0000(05)80070-4
Ramachandran, V., and J. Reif. “Planarity testing in parallel.” Journal of Computer and System Sciences 49, no. 3 (January 1, 1994): 517–61. https://doi.org/10.1016/S0022-0000(05)80070-4.
Ramachandran V, Reif J. Planarity testing in parallel. Journal of Computer and System Sciences. 1994 Jan 1;49(3):517–61.
Ramachandran, V., and J. Reif. “Planarity testing in parallel.” Journal of Computer and System Sciences, vol. 49, no. 3, Jan. 1994, pp. 517–61. Scopus, doi:10.1016/S0022-0000(05)80070-4.
Ramachandran V, Reif J. Planarity testing in parallel. Journal of Computer and System Sciences. 1994 Jan 1;49(3):517–561.
Journal cover image

Published In

Journal of Computer and System Sciences

DOI

EISSN

1090-2724

ISSN

0022-0000

Publication Date

January 1, 1994

Volume

49

Issue

3

Start / End Page

517 / 561

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