What we (do not) know about sublinear separators

-
Zdenek Dvorak, Charles University, Prague

Starting from the famous planar separator theorem of Lipton and Tarjan, the notion of sublinear separators played an important role in the algorithmic graph theory.  However, it began to be explored from the structural point of view only recently.  I will survey the known results on the properties of classes of graphs with sublinear separators and present a number of open questions.