Tree decompositions are a powerful tool in both structural
graph theory and graph algorithms. Many hard problems become tractable if
the input graph is known to have a tree decomposition of bounded
“width”. Exhibiting a particular kind of a tree decomposition is also
a useful way to describe the structure of a graph.
Tree decompositions have traditionally been used in the context of
forbidden graph minors; bringing them into the realm of forbidden
induced subgraphs has until recently remained out of reach. Over the last
couple of years we have made significant progress in this direction, exploring
both the classical notion of bounded tree-width, and concepts of more
structural flavor. This talk will survey some of these ideas and
results.