graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a shallow minor or limited-depth minor is a restricted form of a

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

in which the subgraphs that are contracted to form the minor have small

diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...

. Shallow minors were introduced by , who attributed their invention to

Charles E. Leiserson Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. H ...

and Sivan Toledo.

Definition

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 Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

''H''_''i'' of ''H''. The minor has a vertex ''v''_''i'' for each subset ''S''_''i'', and an edge ''v''_''i''''v''_''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''., Section 4.2 "Shallow Minors", pp. 62–65.

Special cases

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.

Classification of graph families

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''. 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 graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction ...

s. A more restrictive type of graph family, described similarly, are the graph families of

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, ...

. 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''). If this function exists and is bounded by a

polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...

, the graph family is said to have polynomial expansion.

Separator theorems

As showed, graphs with excluded shallow minors can be partitioned analogously to the

planar separator theorem In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of verti ...

for

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s. In particular, if the complete graph ''K''_''h'' is not a ''d''-shallow minor of an ''n''-vertex graph ''G'', then there exists a subset ''S'' of ''G'', with size such that each connected component of ''G''\''S'' has at most 2''n''/3 vertices. The result is constructive: there exists a polynomial time algorithm that either finds such a separator, or a ''d''-shallow ''K''_''h'' minor.The algorithm of Plotkin et al. takes time ''O''(''mn''/''d''), where ''m'' is the number of edges in the input. improved this for non-sparse graphs to As a consequence they showed that every minor-closed graph family obeys a separator theorem almost as strong as the one for planar graphs. Plotkin et al. also applied this result to the partitioning of

finite element method The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat ...

meshes in higher dimensions; for this generalization, shallow minors are necessary, as (with no depth restriction) the family of meshes in three or more dimensions has all graphs as minors. extends these results to a broader class of high-dimensional graphs. More generally, a hereditary graph family has a separator theorem where the separator size is a sublinear power of ''n'' if and only if it has polynomial expansion.

Notes

References

*. *. *. *. *{{citation , last1 = Nešetřil , first1 = Jaroslav , author1-link = Jaroslav Nešetřil , last2 = Ossona de Mendez , first2 = Patrice , author2-link = Patrice Ossona de Mendez , doi = 10.1007/978-3-642-27875-4 , isbn = 978-3-642-27874-7 , mr = 2920058 , publisher = Springer , series = Algorithms and Combinatorics , title = Sparsity: Graphs, Structures, and Algorithms , volume = 28 , year = 2012 . Graph minor theory