Department of
Applied
Mathematics

A tutorial on uniform quasi-wideness

Sebastian Siebertz

Abstract

Nowhere dense classes of graphs form a large variety of classes of uniformly sparse graphs, including the class of planar graphs, actually all classes with excluded (topological) minors and also bounded degree graphs and classes of bounded expansion. The notion of nowhere denseness turns out to be a very robust concept with many seemingly unrelated natural characterisations. In this talk I will give an introduction to uniform quasi-wideness, a notion that provides a characterisation of nowhere denseness that is particularly useful in the context of parameterized complexity.