Publications [#236922] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Klein, PN; Reif, JH, An efficient parallel algorithm for planarity, Journal of Computer and System Sciences, vol. 37 no. 2 (January, 1988), pp. 190-246, Elsevier BV, ISSN 0022-0000 [doi]
   (last updated on 2026/01/15)

   Abstract:
   We describe a parallel algorithm for testing a graph for planarity, and for finding an embedding of a planar graph. For a graph on n vertices, the algorithm runs in O(log²n) steps on n processors of a parallel RAM. The previous best parallel algorithm for planarity testing also ran in O(log²n) time (J. Ja'Ja' and J. Simon, J Comput.11, No. 2 (1982), 313-328), but used a reduction to solving linear systems, and hence required Ω(M(n) log²n) processors, where M(n) is the sequential time for n × n matrix multiplication, whereas our processor bounds are within a polylog factor of optimal. The most significant aspect of our parallel algorithms is the use of a sophisticated data structure for representing sets of embeddings, the PQ-tree of K. Booth and G. Lueker, J. Comput. System Sci.13, No. 3 (1976), 335-379). Previously no parallel algorithms for PQ-trees were known. We have efficient parallel algorithms for manipulating PQ-trees, which we use in our planarity algorithm. © 1988.