Shallow minor

Shallow minors were introduced by Plotkin, Rao & Smith (1994), who attributed their invention to Charles E. Leiserson and Sivan Toledo.

[1] Nešetřil & Ossona de Mendez (2012) use shallow minors to partition the families of finite graphs into two types.

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

The result is constructive: there exists a polynomial time algorithm that either finds such a separator, or a d-shallow Kh minor.

Plotkin et al. also applied this result to the partitioning of finite element method 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.

A graph that has the complete graph K 4 as a 1-shallow minor. Each of the four vertex subsets indicated by the dashed rectangles induces a connected subgraph with radius one, and there exists an edge between every pair of subsets.