First-Order Model Checking on Structurally Sparse Graph Classes

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz

A class of graphs is structurally nowhere dense if it can be constructed from a nowhere dense class by a first-order transduction. Structurally nowhere dense classes vastly general…