## EFFICIENT PARALLEL ALGORITHM FOR PLANARITY.

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 Scholars

## Published In

## DOI

## ISSN

## Publication Date

## Start / End Page

### Citation

*Annual Symposium on Foundations of Computer Science (Proceedings)*, 465–477. https://doi.org/10.1109/sfcs.1986.6

*Annual Symposium on Foundations of Computer Science (Proceedings)*, January 1, 1986, 465–77. https://doi.org/10.1109/sfcs.1986.6.

*Annual Symposium on Foundations of Computer Science (Proceedings)*, Jan. 1986, pp. 465–77.

*Scopus*, doi:10.1109/sfcs.1986.6.