Logic and
Theory of
Discrete Systems

Informatik 7

Algorithmic Structure Theory of Sparse Graph Classes

Martin Grohe, Konstantinos Stavropoulos

Algorithmic graph structure theory evolved in the last 10-15 years out of Robertson and Seymour’s structure theory for graph classes with excluded minors. By now, the theory goes beyond classes with excluded minors and, for example, includes graph classes with excluded topological subgraphs, classes of bounded expansion, and nowhere dense graph classes. The idea is to exploit structural insight on the respective graph classes in the design of efficient algorithms.

The core result of Robertson and Seymour’s graph minor theory is a structural decomposition for all graph classes with excluded minors. It states that all graphs in such a class can be decomposed into pieces that are almost embeddable in some fixed surface. Jointly with Ken-Ichi Kawarabayashi (NII, Tokio) and Bruce Reed (McGill University, Montreal), we designed an algorithm for computing such decompositions in quadratic time. Our algorithm is not only faster than previous ones, but also much simpler.

Nowhere dense graph classes were recently introduced by Nešetřil and Ossona de Mendez as a formalization of “sparse graph classes”. They include many other interesting families of graphs classes such as planar graphs and graphs of bounded genus, graphs of bounded degree, graphs of bounded tree width. Many algorithmic results that were first established for more specific graph classes can be generalised to all nowhere dense classes, and nowhere dense classes seem to be a natural limit for such generalisations. Jointly with Stephan Kreutzer and Sebastian Siebertz (both TU Berlin), we proved an “algorithmic meta theorem” for nowhere dense graph classes that is supposed to unify and generalize many algorithmic results for more sparse graph classes.