# EFFICIENT PARALLEL ALGORITHM FOR PLANARITY.

Published

Journal Article

A parallel algorithm for testing a graph for planarity and for finding an embedding of a planar graph is described. For a graph on n vertices, the algorithm runs in O(log**2 n) steps on n processors of a parallel RAM. The previous best algorithm for planarity testing in parallel polylog time used a reduction to solving linear systems, and hence required OMEGA (n**2 **. **4 **9 **. **. **. ) processors by known methods, whereas the present processor bounds are within a polylog factor of optimal. The most significant aspect of the algorithm is the use of a sophisticated data structure for representing sets of embeddings, called the PQ-tree. Efficient parallel algorithms for manipulating PQ-trees were developed for use in the planarity algorithm.

### Duke Authors

### Cited Authors

- Klein, PN; Reif, JH

### Published Date

- December 1, 1986

### Published In

### Start / End Page

- 465 - 477

### International Standard Serial Number (ISSN)

- 0272-5428

### Citation Source

- Scopus