Parallel complexity of partitioning a planar graph into vertex-induced forests

AbstractWe 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 K4-free or K2,3-free graph (special planar graph) into two subsets, each of which induces a forest