Degree-constrained decompositions of graphs: bounded treewidth and planarity

Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel

Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2006), Degree-constrained decompositions of graphs: bounded treewidth and planarity, Theoretical Computer Science, 355, 3, p. 389-395. http://dx.doi.org/10.1016/j.tcs.2006.01.024

Type

Article accepté pour publication ou publié

Date

2006

Journal name

Theoretical Computer Science

Volume

355

Number

Publisher

Elsevier

Pages

389-395

Abstract (EN)

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 vset membership, variantV1 has degree at least a(v) inside V1 and each vset membership, variantV2 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.

Subjects / Keywords

Polynomial Algorithm; Treewidth; Graph decomposition; Planar graphs; PTAS