Bounded expansion

In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, polynomial expansion, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs.

A t-shallow minor of a graph G is defined to be a graph formed from G by contracting a collection of vertex-disjoint subgraphs of radius t, and deleting the remaining vertices of G. A family of graphs has bounded expansion if there exists a function f such that, in every t-shallow minor of a graph in the family, the ratio of edges to vertices is at most f(t).^[1]

Equivalent definitions of classes of bounded expansions are that all shallow minors have chromatic number bounded by a function of t,^[1] or that the given family has a bounded value of a topological parameter. Such a parameter is a graph invariant that is monotone under taking subgraphs, such that the parameter value can change only in a controlled way when a graph is subdivided, and such that a bounded parameter value implies that a graph has bounded degeneracy.^[2]

A stronger notion is polynomial expansion, meaning that the function f used to bound the edge density of shallow minors is a polynomial. If a hereditary graph family obeys a separator theorem, stating that any n-vertex graph in the family can be split into pieces with at most n/2 vertices by the removal of O(n^c) vertices for some constant c < 1, then that family necessarily has polynomial expansion. Conversely, graphs with polynomial expansion have sublinear separator theorems.^[3]

Because of the connection between separators and expansion, every minor-closed graph family, including the family of planar graphs, has polynomial expansion. The same is true for 1-planar graphs, and more generally the graphs that can be embedded onto surfaces of bounded genus with a bounded number of crossings per edge, as well as the biclique-free string graphs, since these all obey similar separator theorems to the planar graphs.^[4][5][6][7] In higher dimensional Euclidean spaces, intersection graphs of systems of balls with the property that any point of space is covered by a bounded number of balls also obey separator theorems^[8] that imply polynomial expansion.

Although graphs of bounded book thickness do not have sublinear separators,^[9] they also have bounded expansion.^[10] Other graphs of bounded expansion include graphs of bounded degree,^[11] random graphs of bounded average degree in the Erdős–Rényi model,^[12] and graphs of bounded queue number.^[2][13]

Instances of the subgraph isomorphism problem in which the goal is to find a target graph of bounded size, as a subgraph of a larger graph whose size is not bounded, may be solved in linear time when the larger graph belongs to a family of graphs of bounded expansion. The same is true for finding cliques of a fixed size, finding dominating sets of a fixed size, or more generally testing properties that can be expressed by a formula of bounded size in the first-order logic of graphs.^[14][15]

For graphs of polynomial expansion, there exist polynomial-time approximation schemes for the set cover problem, maximum independent set problem, dominating set problem, and several other related graph optimization problems.^[16]