# A Randomized Parallel Algorithm for Planar Graph Isomorphism

Published

Journal Article

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.

### Full Text

### Duke Authors

### Cited Authors

- Gazit, H; Reif, JH

### Published Date

- January 1, 1998

### Published In

### Volume / Issue

- 28 / 2

### Start / End Page

- 290 - 314

### International Standard Serial Number (ISSN)

- 0196-6774

### Digital Object Identifier (DOI)

- 10.1006/jagm.1998.0943

### Citation Source

- Scopus