Shallow minor

One way of defining a minor of an undirected graph G is by specifying a subgraph H of G, and a collection of disjoint subsets S_i of the vertices of G, each of which forms a connected induced subgraph H_i of H. The minor has a vertex v_i for each subset S_i, and an edge v_iv_j whenever there exists an edge from S_i to S_j that belongs to H.

In this formulation, a d-shallow minor (alternatively called a shallow minor of depth d) is a minor that can be defined in such a way that each of the subgraphs H_i has radius at most d, meaning that it contains a central vertex c_i that is within distance d of all the other vertices of H_i. Note that this distance is measured by hop count in H_i, and because of that it may be larger than the distance in G.^[1]

Shallow minors of depth zero are the same thing as subgraphs of the given graph. For sufficiently large values of d (including all values at least as large as the number of vertices), the d-shallow minors of a given graph coincide with all of its minors.^[1]

Nešetřil & Ossona de Mendez (2012) use shallow minors to partition the families of finite graphs into two types. They say that a graph family F is somewhere dense if there exists a finite value of d for which the d-shallow minors of graphs in F consist of every finite graph. Otherwise, they say that a graph family is nowhere dense.^[2] This terminology is justified by the fact that, if F is a nowhere dense class of graphs, then (for every ε > 0) the n-vertex graphs in F have O(n^1 + ε) edges; thus, the nowhere dense graphs are sparse graphs.^[3]

A more restrictive type of graph family, described similarly, are the graph families of bounded expansion. These are graph families for which there exists a function f such that the ratio of edges to vertices in every d-shallow minor is at most f(d).^[4] If this function exists and is bounded by a polynomial, the graph family is said to have polynomial expansion.