| Summary: | 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.
In this paper, we show that one can encode graphs from a class with
structurally bounded expansion via lacon-, shrub- and parity-decompositions
from a class with bounded expansion. These decompositions are useful for
lifting properties from sparse to structurally sparse graph classes.
|
|---|