Degree-3 Treewidth Sparsifiers
Degree-3 Treewidth Sparsifiers
We study treewidth sparsifiers. Informally, given a graph G of treewidth k, a treewidth sparsifier H is a minor of G, whose treewidth is close to k, |V(H)| is small, and the maximum vertex degree in H is bounded. Treewidth sparsifiers of degree 3 are of particular interest, as routing …