Bramble (graph theory)

Expander graphs of bounded degree have treewidth proportional to their number of vertices, and therefore also have brambles of linear order.

However, as Martin Grohe and Dániel Marx showed, for these graphs, a bramble of such a high order must include exponentially many sets.

More strongly, for these graphs, even brambles whose order is slightly larger than the square root of the treewidth must have exponential size.

However, Grohe and Marx also showed that every graph of treewidth k has a bramble of polynomial size and of order

[2] Because brambles may have exponential size, it is not always possible to construct them in polynomial time for graphs of unbounded treewidth.

[3] Bodlaender, Grigoriev, and Koster[4] studied heuristics for finding brambles of high order.

Kreutzer and Tazari[5] provide randomized algorithms that, on graphs of treewidth k, find brambles of polynomial size and of order

[6][7] In a directed graph D, a bramble is a collection of strongly connected subgraphs of D that all touch each other: for every pair of disjoint elements X, Y of the bramble, there must exist an arc in D from X to Y and one from Y to X.