Skip to main content

Optimal parallel algorithm for graph planarity

Publication ,  Journal Article
Ramachandran, V; Reif, J
Published in: Annual Symposium on Foundations of Computer Science (Proceedings)
January 1, 1989

The authors present a parallel algorithm based on open ear decomposition which, given a graph G on n vertices, constructs an embedding of G onto the plane or reports that G is nonplanar. This parallel algorithm runs on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM) in O(log n) time with the same processor bound as graph connectivity.

Duke Scholars

Published In

Annual Symposium on Foundations of Computer Science (Proceedings)

DOI

ISSN

0272-5428

Publication Date

January 1, 1989

Start / End Page

282 / 287
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Ramachandran, V., & Reif, J. (1989). Optimal parallel algorithm for graph planarity. Annual Symposium on Foundations of Computer Science (Proceedings), 282–287. https://doi.org/10.1109/sfcs.1989.63491
Ramachandran, V., and J. Reif. “Optimal parallel algorithm for graph planarity.” Annual Symposium on Foundations of Computer Science (Proceedings), January 1, 1989, 282–87. https://doi.org/10.1109/sfcs.1989.63491.
Ramachandran V, Reif J. Optimal parallel algorithm for graph planarity. Annual Symposium on Foundations of Computer Science (Proceedings). 1989 Jan 1;282–7.
Ramachandran, V., and J. Reif. “Optimal parallel algorithm for graph planarity.” Annual Symposium on Foundations of Computer Science (Proceedings), Jan. 1989, pp. 282–87. Scopus, doi:10.1109/sfcs.1989.63491.
Ramachandran V, Reif J. Optimal parallel algorithm for graph planarity. Annual Symposium on Foundations of Computer Science (Proceedings). 1989 Jan 1;282–287.

Published In

Annual Symposium on Foundations of Computer Science (Proceedings)

DOI

ISSN

0272-5428

Publication Date

January 1, 1989

Start / End Page

282 / 287