Deciding first-order properties of nowhere dense graphs

Martin Grohe, Stephan Kreutzer, Sebastian Siebertz

Nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez, form a large variety of classes of "sparse graphs" including the class of planar graphs, actually all clas…