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
Bounded expansion
Summary
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.
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.