Optimal parallel algorithm for graph planarity

Published

Journal Article

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 Authors

Cited Authors

  • Ramachandran, V; Reif, J

Published Date

  • November 1, 1989

Published In

Start / End Page

  • 282 - 287

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus