Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Bounded expansion
Résumé
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, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs.
A t-shallow minor of a graph G is defined to be a graph formed from G by contracting a collection of vertex-disjoint subgraphs of radius t, and deleting the remaining vertices of G. A family of graphs has bounded expansion if there exists a function f such that, in every t-shallow minor of a graph in the family, the ratio of edges to vertices is at most f(t).
Equivalent definitions of classes of bounded expansions are that all shallow minors have chromatic number bounded by a function of t, or that the given family has a bounded value of a topological parameter. Such a parameter is a graph invariant that is monotone under taking subgraphs, such that the parameter value can change only in a controlled way when a graph is subdivided, and such that a bounded parameter value implies that a graph has bounded degeneracy.
A stronger notion is polynomial expansion, meaning that the function f used to bound the edge density of shallow minors is a polynomial. If a hereditary graph family obeys a separator theorem, stating that any n-vertex graph in the family can be split into pieces with at most n/2 vertices by the removal of O(nc) vertices for some constant c < 1, then that family necessarily has polynomial expansion. Conversely, graphs with polynomial expansion have sublinear separator theorems.
Because of the connection between separators and expansion, every minor-closed graph family, including the family of planar graphs, has polynomial expansion.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.