TREE DECOMPOSITIONS OF GRAPHS
Rolf Niedermeier · 2006
Abstract This chapter provides an introduction to tree decomposition and treewidth, important concepts from modern graph theory. Treewidth is one of the best studied and most significant structural parameters. The construction of tree decompositions is briefly discussed, followed by special considerations applying to planar graphs. The main focus of the chapter is on dynamic programming on tree decompositions, here demonstrated for the problems Vertex Cover and Dominating Set. The chapter closes by sketching the relationship to monadic second-order logic and some related graph width parameters.