Publications [#236964] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Ramachandran, V; Reif, J, Planarity testing in parallel, Journal of Computer and System Sciences, vol. 49 no. 3 (January, 1994), pp. 517-561, Elsevier BV, ISSN 0022-0000 [doi]
   (last updated on 2026/01/15)

   Abstract:
   We present a parallel algorithm based on open ear decomposition to construct an embedding of a graph onto the plane or report that the graph is nonplanar. Our parallel algorithm runs on a CRCW PRAM in logarithmic time with a number of processors bounded by that needed for finding connected components in a graph and for performing bucket sort. © 1994 by Academic Press, Inc.