Canonical Graph Decompositions via Local SeparationsResearch Paper
Tree-decompositions describe the global, tree-like connectivity of a graph: the Robertson–Seymour tree-of-tangles theorem gives, for every graph, a canonical tree-decomposition that efficiently distinguishes all its tangles. Many graphs, though, are tree-like only locally: road networks, Cayley graphs of finite groups, locally chordal graphs. Their…