PARALLEL COMPLEXITY OF PARTITIONING A PLANAR GRAPH INTO VERTEX-INDUCED FORESTS

We present the first NC algorithm for partitioning the vertex set of a given planar graph into three subsets, each of which induces a forest . The algorithm runs in O(log n log n) time using O(n/(log n log*n)) processors on an EREW PRAM. We also present optimal NC algorithms for partitioning the vertex set of a given K-4-free or K-2,K-3-free graph (special planar graph) into two subsets, each of which induces a fores t.