Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes

The concept of bounded expansion provides a robust way to capture sparse graph classes with interesting algorithmic properties. Most notably, every problem definable in first-order logic can be solved in linear time on bounded expansion graph classes. First-order interpretations and transductions of sparse graph classes lead to more general, dense graph classes that seem to inherit many of the nice algorithmic properties of their sparse counterparts. The leading question of this talk is: "How can we generalize the beautiful existing algorithmic results of sparse graphs to dense graphs?" We start with an overview over sparse and dense graph classes and then introduce lacon- and shrub-decompositions. We show that dense graph classes can be exactly characterized by having a sparse lacon- or shrub-decoposition. If one could efficiently compute such a decomposition then one could solve every problem definable in first-order logic in linear time on these classes.