Publications [#237098] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Klein, PN; Reif, JH, EFFICIENT PARALLEL ALGORITHM FOR PLANARITY., Annual Symposium on Foundations of Computer Science Proceedings (January, 1986), pp. 465-477 [doi]
   (last updated on 2026/01/15)

   Abstract:
   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.