# Shrub-depth: Capturing Height of Dense Graphs

arXiv: https://arxiv.org/abs/1707.00359 · HTML: https://mlsanity.com/paper/1707.00359/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2017.

## Built on by (most cited first, 1 of 1)

- [Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology](https://mlsanity.com/paper/2312.09646/) (2023)

## Abstract (arXiv)

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 ω levels of the MSO1 transduction hierarchy of simple graphs.