Low-Congestion Shortcuts for Graphs Excluding Dense Minors
Mohsen Ghaffari, Bernhard Haeupler · 2021
We prove that any n-node graph G with diameter D admits shortcuts with congestion O(δ D log n) and dilation O(δ D), where δ is the maximum edge-density of any minor of G. Our proof is simple and constructive with a tildeΘ (δ D)-round1 distributed construction algorithm. Our results are tight up to logarithmic factors and generalize, simplify, unify, and strengthen several prior results. For example, for graphs excluding a fixed minor, i.e., graphs with constant δ, only a Õ (D2) bound was known based on a very technical proof that relies on the Robertson-Seymour Graph Structure Theorem.