An optimal parallel algorithm for graph planarity
Vijaya Ramachandran, John H. Reif · 1989
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.>