Planarity testing in parallel


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Ramachandran, V; Reif, J

Published Date

  • January 1, 1994

Published In

Volume / Issue

  • 49 / 3

Start / End Page

  • 517 - 561

Electronic International Standard Serial Number (EISSN)

  • 1090-2724

International Standard Serial Number (ISSN)

  • 0022-0000

Digital Object Identifier (DOI)

  • 10.1016/S0022-0000(05)80070-4

Citation Source

  • Scopus