Bounded expansion
id:
bounded-expansion-304-6493528
title:
Bounded expansion
text:
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.
brand slug:
wiki
category slug:
encyclopedia
description:
Family of graphs whose shallow minors are sparse graphs
original url:
https://en.wikipedia.org/wiki/Bounded_expansion
date created:
date modified:
2023-12-06T04:02:14Z
main entity:
{"identifier":"Q25304158","url":"https://www.wikidata.org/entity/Q25304158"}
image:
fields total:
13
integrity:
14