# Randomized parallel algorithm for planar graph isomorphism

Published

Journal Article

We present a parallel randomized algorithm for finding if two planar graphs are isomorphic. Assuming that we have a tree of separators for each planar graph, our algorithm takes O(log(n)) time with P = (n1.5·√log(n)) processors with probability to fail of 1/n or less, where n is the number of vertices. The algorithms 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 processors number to n3/2+ε. This algorithm significantly improves the previous results of n4 processors.

### Duke Authors

### Cited Authors

- Gazit, H; Reif, JH

### Published Date

- December 1, 1990

### Published In

- Algorithms and Architectures

### Start / End Page

- 210 - 219

### Citation Source

- Scopus