A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs (Q1109576)

This paper presents an efficient parallel algorithm for constructing a maximal independent set in planar graphs. The algorithm runs in \(O(\log^ 2 n)\) time with O(n) processors on a PRAM and is within an \(O(\log^ 2 n)\) factor of optimal. The best previously known algorithm for this problem takes \(O(\log^ 2 n)\) time with \(O(n^ 3)\) processors. The key subroutine of the algorithm is an O(log n) time, O(n) processor parallel algorithm for constructing a maximal independent set in a one- page planar graph. This subroutine may be of independent interest.