Publications [#237108] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Ramachandran, V; Reif, J, Optimal parallel algorithm for graph planarity, Annual Symposium on Foundations of Computer Science Proceedings (January, 1989), pp. 282-287 [doi]
   (last updated on 2026/01/14)

   Abstract:
   The authors present a parallel algorithm based on open ear decomposition which, given a graph G on n vertices, constructs an embedding of G onto the plane or reports that G is nonplanar. This parallel algorithm runs on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM) in O(log n) time with the same processor bound as graph connectivity.