Excluding $K_{2,t}$ as a fat minor
By: Sandra Albrechtsen, Marc Distel, Agelos Georgakopoulos
Potential Business Impact:
Helps computers measure how "stretched" graphs are.
We prove that for every $t \in \mathbb{N}$, the graph $K_{2,t}$ satisfies the fat minor conjecture of Georgakopoulos and Papasoglu: for every $K\in \mathbb{N}$ there exist $M,A\in \mathbb{N}$ such that every graph with no $K$-fat $K_{2,t}$ minor is $(M,A)$-quasi-isometric to a graph with no $K_{2,t}$ minor. We use this to obtain an efficient algorithm for approximating the minimal multiplicative distortion of any embedding of a finite graph into a $K_{2,t}$-minor-free graph, answering a question of Chepoi, Dragan, Newman, Rabinovich, and Vax\`es from 2012.
Similar Papers
$K_{2,3}$-induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two
Combinatorics
Makes complex networks simpler to understand.
A Polynomial-Time Approximation Algorithm for Complete Interval Minors
Data Structures and Algorithms
Finds patterns in ordered pictures.
Polynomial Bounds for the Graph Minor Structure Theorem
Combinatorics
Makes computers solve hard problems much faster.