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.
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