First-Order Model Checking on Structurally Sparse Graph Classes
Jan Dreier, Nikolas Mählmann, Sebastian Siebertz · 2023
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 generalize nowhere dense classes and constitute important examples of monadically stable classes. We show that the first-order model checking problem is fixed-parameter tractable on every structurally nowhere dense class of graphs.