Abstrakt
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 epsilon > 0, posets of height at most h with n elements and whose cover graphs are in the class have dimension O(n(epsilon)).