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.

翻译：摘要：有界扩张的概念提供了一种稀疏图类的强大抓捕方式，这些类具有有趣的算法特性。最值得注意的是，每个在有界扩张图类上可定义的一阶逻辑问题都可以在线性时间内解决。稀疏图类的一阶解释和传送导致了更一般的、密集的图类，这些图类似乎继承了它们的稀疏对应物的许多好的算法特性。在本文中，我们展示了人们可以通过来自带有有界扩张的类的lacon-、shrub-和parity-decompositions对带有结构有界扩张的类进行图编码。这些分解对从稀疏到结构稀疏图类的特性提升非常有用。