Layered separators in minor-closed graph classes with applications

摘要

AbstractGraph 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 can be as large asΩ(n)in graphs withnvertices. This is the case for planar graphs, and more generally, for proper minor-closed classes. We study a special type of graph separator, called alayered separator, which may have linear size inn, but has bounded size with respect to a different measure, called thewidth. We prove, for example, that planar graphs and graphs of bounded Euler genus admit layered separators of bounded width. More generally, we characterise the minor-closed classes that admit layered separators of bounded width as those that exclude a fixed apex graph as a minor.We use layered separators to proveO(log?n)bounds for a number of problems whereO