A New Parallel Algorithm for Planarity Testing (original) (raw)

David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332

| | 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 pleqnp \leq npleqn 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. Publication History Versions of this paper appeared as: D.A. Bader and S. Sreshta, ``A New Parallel Algorithm for Planarity Testing,'' UNM-ECE Technical Report 03-002, October 1, 2003. Download this report in Adobe PDF | | | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | | | Last updated: July 25, 2004 | |

Computational Biology

Parallel Computing

Combinatorics