A Parallel Algorithm for Finding Maximal Independent Sets in Planar Graphs

The problem of constructing parallel algorithms for finding Maximal Independent Sets in graphs has received considerable attention. In the case that the given graph is planar, the simple efficient parallel algorithm described here may be employed. The method relies on an efficient parallel algorithm for constructing large independent sets in bounded degree graphs. This is accomplished by a simple reduction to the same problem for lists.

Using a linear number of EREW processors, the algorithm identifies a maximal independent set in an arbitrary planar graph in O$(\log n \log^{*} n)$ parallel time. A randomized version of the algorithm runs in O$(\log n)$ expected parallel time.