Tree decompositions: representing a graph by a tree (PIMS network-wide colloquium)

How does one describe the structure of a graph? What is a good way to measure how complicated a given graph is? Tree decompositions are a powerful tool in structural graph theory, designed to address these questions. To obtain a tree decomposition of a graph G, we break G into parts that interact with each other in a simple ("tree-like") manner. But what properties do the parts need to have in order for the decomposition to be meaningful? Traditionally a parameter called the "width" of a decomposition was considered, that is simply the maximum size of a part. In recent years other ways of measuring the complexity of tree decompositions have been proposed, and their properties are being studied. In this talk we will discuss recent progress in this area, touching on  the classical notion of bounded tree-width, concepts of more structural flavor, and the interactions between them.