Shrub-depth: Capturing Height of Dense Graphs
From MaRDI portal
Publication:6288558
arXiv1707.00359MaRDI QIDQ6288558FDOQ6288558
Authors: Robert Ganian, Petr Hliněný, J. Nešetřil, Jan Obdržálek, P. Ossona de Mendez 
Publication date: 2 July 2017
Abstract: 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.
Graph theory (including graph drawing) in computer science (68R10) Model theory of finite structures (03C13) Structural characterization of families of graphs (05C75) Specification and verification (program logics, model checking, etc.) (68Q60) Higher-order logic (03B16)
This page was built for publication: Shrub-depth: Capturing Height of Dense Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6288558)
