Nowhere Dense Graph Classes and Dimension

2017/08/17 by Gwenaël Joret, Piotr Micek, Joret, Gwenaël +5
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1708.05424

v4: Minor changes suggested by a referee

arxiv created 2019/01/31 · arxiv updated 2019/02/04

Abstract

Nowhere dense graph classes provide one of the least restrictive notions of sparsity for graphs. Several equivalent characterizations of nowhere dense classes have been obtained over the years, using a wide range of combinatorial objects. In this paper we establish a new characterization of nowhere dense classes, in terms of poset dimension: A monotone graph class is nowhere dense if and only if for every h ≥ 1 and every ε> 0, posets of height at most h with n elements and whose cover graphs are in the class have dimension O(n^ε).

Related

• Deciding first-order properties of nowhere dense graphs
• Nowhere dense graph classes and algorithmic applications. A tutorial at Highlights of Logic, Games and Automata 2019
• Directed Nowhere Dense Classes of Graphs
• Deciding first-order properties of nowhere dense graphs
• On ultralimits of sparse graph classes