**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 GraphSearch.

Concept# Graph minor

Summary

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.
The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.
For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time; together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time.
Other results and conjectures involving graph minors include the graph structure theorem, according to which the graphs that do not have H as a minor may be formed by gluing together simpler pieces, and Hadwiger's conjecture relating the inability to color a graph to the existence of a large complete graph as a minor of it. Important variants of graph minors include the topological minors and immersion minors.
An edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices it used to connect. An undirected graph H is a minor of another undirected graph G if a graph isomorphic to H can be obtained from G by contracting some edges, deleting some edges, and deleting some isolated vertices. The order in which a sequence of such contractions and deletions is performed on G does not affect the resulting graph H.
Graph minors are often studied in the more general context of matroid minors. In this context, it is common to assume that all graphs are connected, with self-loops and multiple edges allowed (that is, they are multigraphs rather than simple graphs); the contraction of a loop and the deletion of a cut-edge are forbidden operations.

Official source

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.

Related publications (1)

Related courses (32)

Related concepts (69)

HUM-411: Graphic design II

Le cours vise à faire découvrir les bases du design graphique, ses enjeux, ses différents domaines d'application, ses techniques et ses conventions. Il s'agit d'un enseignement pratique qui repose sur

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

PHYS-117: Physics lab (metrology)

Ce cours est une introduction pratique aux techniques de mesure classiques d'un laboratoire de physique ayant pour but de familiariser les étudiants avec l'acquisition de données, les capteurs, l'anal

Forbidden graph characterization

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.

Homeomorphism (graph theory)

In graph theory, two graphs and are homeomorphic if there is a graph isomorphism from some subdivision of to some subdivision of . If the edges of a graph are thought of as lines drawn from one vertex to another (as they are usually depicted in illustrations), then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the topological sense. In general, a subdivision of a graph G (sometimes known as an expansion) is a graph resulting from the subdivision of edges in G.

Graph minor

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small fraction of edges of the graph controlled by a proximity parameter to get connected components of size independent of n. An important tool for sublinear algorithms and property testing for such classes is the partition oracle, introduced by the seminal work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009). A partition oracle is a local procedure that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a query vertex v, the partition oracle outputs the component containing v in time independent of n. All the answers are consistent with a single hyperfinite decomposition. The partition oracle of Hassidim et al. runs in time exponential in the proximity parameter per query. They pose the open problem of whether partition oracles which run in time polynomial in reciprocal of proximity parameter can be built. Levi-Ron (ICALP 2013) give a refinement of the previous approach, to get a partition oracle that runs in quasipolynomial time per query. In this paper, we resolve this open problem and give polynomial time partition oracles (in reciprocal of proximity parameter) for bounded degree graphs in any minor-closed family. Unlike the previous line of work based on combinatorial methods, we employ techniques from spectral graph theory. We build on a recent spectral graph theoretical toolkit for minor-closed graph families, introduced by the authors to develop efficient property testers. A consequence of our result is an efficient property tester for any monotone and additive with running time property of minor-closed families (such as bipartite planar graphs). Our result also gives query efficient algorithms for additive approximations for problems such as maximum matching, minimum vertex cover, maximum independent set, and minimum dominating set for these graph families.

Related lectures (223)

Linear Transformations: Matrices and Kernels

Covers linear transformations, matrices, kernels, and properties of invertible matrices.

Counterfactuals: SEM and D-SeparationMGT-416: Causal inference

Explores counterfactuals in SEMs and D-Separation in graphical models.