IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332

A New Parallel Algorithm for Planarity Testing

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.

Publication History

Versions of this paper appeared as:
1. D.A. Bader and S. Sreshta, A New Parallel Algorithm for Planarity Testing,'' UNM-ECE Technical Report 03-002, October 1, 2003.

Last updated: July 25, 2004

Computational Biology

Parallel Computing

Combinatorics