Shrub-depth: Capturing Height of Dense Graphs

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GANIAN Robert HLINĚNÝ Petr NEŠETŘIL Jaroslav OBDRŽÁLEK Jan OSSONA DE MENDEZ Patrice

Year of publication 2019
Type Article in Periodical
Magazine / Source Logical Methods in Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Web https://lmcs.episciences.org/5149
Doi http://dx.doi.org/10.23638/LMCS-15(1:7)2019
Keywords tree-depth; clique-width; shrub-depth; MSO logic; transduction
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.