Robert Ganian ; Petr Hliněný ; Jaroslav Nešetřil ; Jan Obdržálek ; Patrice Ossona de Mendez - Shrub-depth: Capturing Height of Dense Graphs

lmcs:3798 - Logical Methods in Computer Science, January 31, 2019, Volume 15, Issue 1 - https://doi.org/10.23638/LMCS-15(1:7)2019
Shrub-depth: Capturing Height of Dense GraphsArticle

Authors: Robert Ganian ; Petr Hliněný ORCID; Jaroslav Nešetřil ; Jan Obdržálek ; Patrice Ossona de Mendez ORCID

    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.


    Volume: Volume 15, Issue 1
    Published on: January 31, 2019
    Accepted on: November 30, 2018
    Submitted on: July 19, 2017
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics,Mathematics - Combinatorics,03B70, 05C75, 68R10
    Funding:
      Source : OpenAIRE Graph
    • New Frontiers for Parameterized Complexity; Funder: Austrian Science Fund (FWF); Code: P 31336

    Consultation statistics

    This page has been seen 1606 times.
    This article's PDF has been downloaded 656 times.