Layered treewidth/separators with applications
(Vida Dujmović)

Graph separators (and treewidth) are a ubiquitous tool in graph theory and computer science. However, in some applications, their usefulness is limited by the fact that their size depends on the size of the graph. This is the case for planar graphs, and more generally, for proper minor-closed families which can have Omega(sqrt n) separators in graphs with n vertices.

I will talk about a special type of graph separator, called a "layered separator" and the closely-related notion of layered treewidth. These separators may have linear size in n, but have bounded size with respect to a different measure, called width. Planar graphs, graphs of bounded Euler genus, and k-planar graphs admit layered separators of bounded width. I show how (with simple proofs) they can be used to obtain logarithmic bounds for a variety of applications for which O(sqrt n) was the best known long-standing bound. The applications range from various (geometric) graph layouts to graph colourings.