This paper presents a new parallel algorithm for planarity testing based upon the work of Klein and Reif. Our new approach gives correct answers on instances that provoke false positive and false negative results using Klein and Reif's algorithm. The new algorithm has the same complexity bounds as Klein and Reif's algorithm and runs in \bigO{\frac{n\log^{2} n}{p}} time for any number $p \leq n$ processors of a Concurrent Read Exclusive Write (CREW) Parallel RAM (PRAM). Implementations of the major steps of this parallel algorithm exist for symmetric multiprocessors and exhibit speedup when compared to the best sequential approach. Thus, this new parallel algorithm for planarity testing lends itself to a high-performance shared-memory implementation.
