Layered treewidth/separators with applications
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.