Nowhere Dense Graph Classes and Dimension

08/17/2017
by   Gwenaël Joret, et al.
0

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^ϵ).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset