Limited graph extension

A minor of depth t of graph G is defined as a graph formed from G by contracting a collection of subgraphs of radius t that do not have common vertices and removing the remaining vertices. A family of graphs has a bounded extension if there exists a function f such that for any minor of depth t of a graph from a family, the ratio of the number of edges to the number of vertices does not exceed f ( t ) ^[1] .

Another definition of classes of bounded expansion is that all minors of bounded depth have a chromatic number bounded by some function of t ^[1] , or a given family has a bounded value of the topological parameter . Such a parameter is a graph invariant that is monotonic with respect to the operation of taking a subgraph, such that the parameter value can only be changed in a controlled way when the graph is divided, and from the boundedness of the parameter value it follows that the graph has limited degeneracy ^[2] .

A more rigorous concept is a polynomial extension , which means that the function f used to limit the density of edges of minors of limited depth is polynomial . If an inherited family of graphs satisfies a partition theorem that states that any graph with n vertices in a family can be split into two parts containing at most n / 2 vertices by removing O ( n ^c ) vertices for some constant c <1, then this family necessarily has a polynomial extension. Conversely, graphs with polynomial extension have theorems with a sublinear separator ^[3] .

Since there is a connection between separators and an extension, any family of graphs closed by minors , including a family of planar graphs , has a polynomial extension. The same is true for 1-planar graphs , and, more generally, for graphs that can be embedded in surfaces of a limited genus with a limited number of intersections on an edge, as well as string graphs without biclickers , since there are separator theorems for them similar to theorems for planar graphs ^{[4] [5] [6]} . In higher-dimensional Euclidean spaces, the intersection graphs of ball systems with the property that any point in space is covered by a limited number of balls also satisfy partition theorems ^[7] , which implies the existence of a polynomial extension.

Although graphs of limited book width do not contain sublinear separators ^[8] , they also have limited expansion ^[9] . The class of graphs with bounded extension includes graphs of a limited degree ^[10] , random graphs of a limited average degree in the Erdрдs – Renyi model ^[11], and graphs with a limited number of queues ^{[2] [12]} .

An instance of the subgraph isomorphism problem , in which the goal is to search for a graph of a limited size, which is a subgraph of a larger graph whose size is not unlimited, can be solved in linear time if the larger graph belongs to a family of graphs with bounded extension. The same is true for searching fixed-size clicks , searching for dominant fixed-size sets , or, more generally, checking properties that can be expressed by a limited-size formula in the first-order ^{[13] [14]} .

For graphs with polynomial extension, there are approximate polynomial time schemes for the set cover problem, the maximum independent set problem, the dominant set problem , and some other related optimization problems ^[15] .