# Fatness and Flatness

Preprint · Arnold Filtser, Hung Le, Nikolas Mählmann, Marcin Pilipczuk, Michał Pilipczuk

- Archive id: arxiv:2607.21474
- Published: 2026-07-23
- arXiv: https://arxiv.org/abs/2607.21474
- Source URL: https://arxiv.org/abs/2607.21474
- PDF: https://arxiv.org/pdf/2607.21474
- Provenance: arxiv

## Abstract

Fat minors are the metric analog of graph minors that are tailored to the analysis of metric (edge-weighted) graphs and, more generally, metric spaces having a suitable notion of shortest paths. Despite a large interest in this notion, not much is known about the structure of metric graphs excluding a fixed fat minor. We prove that if a metric graph $G$ excludes a fixed graph $H$ as a $δ$-fat minor, for some $δ\>0$, then $G$ enjoys the metric analog of flatness (aka uniform quasi-wideness) - a structural property from the field of Sparsity. In essence, our flatness result says that for any $α\\geq β$ large enough compared to $δ$, in every large enough set $A$ in $G$ one can find a sizable subset $B$ that becomes $α$-scattered after removing a bounded number of balls of radius $β$. We call this property drill-flatness. Notably, the proof only relies on excluding shallow fat minors: every branch set has radius at most $2α$. As a corollary, we prove that metric graphs that exclude a fixed $δ$-fat minor have bounded $\\varepsilon$-scatter dimension if we consider only $\\varepsilon$-scatters at distances large enough compared to $δ$. By combining this with the results of Abbasi et al. \[FOCS 2023\], we infer that the $k$-Center problem on instances excluding $H$ as a $δ$-fat minor admits an approximation algorithm that finds a solution of cost at most $(1+\\varepsilon)\\cdot\\mathsf{OPT}+{\\cal O}(δ/\\varepsilon^2)$ in time ${\\cal O}\_{H,\\varepsilon}(n^{{\\cal O}(1)})$. This is one of the first algorithmic results for general fat-minor-free metrics. We also study drill-flatness in hereditary classes of (unweighted) graphs, where we obtain a characterization equating drill-flatness with excluding shallow induced minors. This is an induced analog of the equivalence between flatness and nowhere denseness - one of central results of Sparsity.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.