## A Randomized Parallel Algorithm for Planar Graph Isomorphism

We present a parallel randomized algorithm running on a CRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known algorithms in O(log2 n) time with n1+ε processors, for any ε > O). If n is the number of vertices, our algorithm takes O(log(n)) time with P = O(n1.5 · √log(n)) processors and with a probability of failure of 1/n at most. The algorithm needs 2 · log(m) - log(n) + O(log(n)) random bits. The number of random bits can be decreased to O(log(n)) by increasing the number of processors to n3/2+ε, for any ε > 0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic time parallel algorithm of Miller and Reif (Siam J. Comput. 20 (1991), 1128-1147), which requires n4 randomized processors or n5 deterministic processors. © 1998 Academic Press.

### Duke Scholars

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 0802 Computation Theory and Mathematics

### Citation

*Journal of Algorithms*,

*28*(2), 290–314. https://doi.org/10.1006/jagm.1998.0943

*Journal of Algorithms*28, no. 2 (January 1, 1998): 290–314. https://doi.org/10.1006/jagm.1998.0943.

*Journal of Algorithms*, vol. 28, no. 2, Jan. 1998, pp. 290–314.

*Scopus*, doi:10.1006/jagm.1998.0943.

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 0802 Computation Theory and Mathematics