Degree-constrained decompositions of graphs: Bounded treewidth and planarity

We study the problem of decomposing the vertex set V of a graph into two nonempty parts V1,V2 which induce subgraphs where each vertex v∈V1 has degree at least a(v) inside V1 and each v∈V2 has degree at least b(v) inside V2. We give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. This result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible.