一句话：综述 shrub-depth 的定义与性质，并用其刻画简单图 MSO1 转导层级的前 ω 层。
随着 tree-depth 及其在图算法与逻辑中应用的关注增加，一个自然问题是：稠密图是否也有类似且在图补运算下稳定的深度概念。2012 年提出的 shrub-depth 正是这样的图不变量，它与 clique-width 的关系类似于 tree-depth 与 tree-width 的关系。本文对 shrub-depth 的定义和基本性质进行深入综述，并重点讨论其逻辑层面；特别地，作者利用 shrub-depth 刻画了简单图 MSO1 转导层级中低于 ω 的层级。
The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say; one which is stable under graph complementation)? To this end, in a 2012 conference paper, a new notion of shrub-depth has been introduced, such that it is related to the established notion of clique-width in a similar way as tree-depth is related to tree-width. Since then shrub-depth has been successfully used in several research papers. Here we provide an in-depth review of the definition and basic properties of shrub-depth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrub-depth to give a characterization of the lower ${\omega}$ levels of the MSO1 transduction hierarchy of simple graphs.
@article{paperbot833,
title = {Shrub-depth: Capturing Height of Dense Graphs},
author = {Robert Ganian and Petr Hliněný and Jaroslav Nešetřil and Jan Obdržálek and Patrice Ossona de Mendez},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 1},
year = {2019},
doi = {10.23638/lmcs-15(1:7)2019}
}