Vida Dujmović

Monday, May 14 at 11:15 AM

Abstract

Graph separators are a ubiquitous tool in graph theory and computer science. However, in some applications, their usefulness is limited by the fact that the separator 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. These applications include, track layouts, queue layouts, stack layouts, nonrepetitive graph colourings and 3-dimensional grid drawings of graphs.