Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Shallow minor
Summary
In graph theory, a shallow minor or limited-depth minor is a restricted form of a graph minor in which the subgraphs that are contracted to form the minor have small diameter. Shallow minors were introduced by , who attributed their invention to Charles E. Leiserson and Sivan Toledo.
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 Si of the vertices of G, each of which forms a connected induced subgraph Hi of H. The minor has a vertex vi for each subset Si, and an edge
vivj whenever there exists an edge from Si to Sj 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 Hi has radius at most d, meaning that it contains a central vertex ci that is within distance d of all the other vertices of Hi. Note that this distance is measured by hop count in Hi, and because of that it may be larger than the distance in G.
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.
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(n1 + ε) edges; thus, the nowhere dense graphs are sparse graphs.
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).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.