Local 2-separators
Johannes Carmesin · arXiv (Cornell University) · 2020
How can sparse graph theory be extended to large networks, where algorithms whose running time is estimated using the number of vertices are not good enough? I address this question by introducing 'Local Separators' of graphs. Applications include: 1. A unique decomposition theorem for graphs along their local 2-separators analogous to the 2-separator theorem; 2. an exact characterisation of graphs with no bounded subdivision of a wheel; 3. an analogue of the tangle-tree theorem of Robertson and Seymour, where the decomposition-tree is replaced by a general graph.