# Low Treewidth Embeddings of Planar and Minor-Free Metrics

arXiv: https://arxiv.org/abs/2203.15627 · HTML: https://mlsanity.com/paper/2203.15627/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2022.

## Built on by (most cited first, 2 of 2)

- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)

## Abstract (arXiv)

Cohen-Addad, Filtser, Klein and Le [FOCS'20] constructed a stochastic embedding of minor-free graphs of diameter D into graphs of treewidth Oε(log n) with expected additive distortion +ε D. Cohen-Addad et al. then used the embedding to design the first quasi-polynomial time approximation scheme (QPTAS) for the capacitated vehicle routing problem. Filtser and Le [STOC'21] used the embedding (in a different way) to design a QPTAS for the metric Baker's problems in minor-free graphs. In this work, we devise a new embedding technique to improve the treewidth bound of Cohen-Addad et al. exponentially to Oε(loglog n)2. As a corollary, we obtain the first efficient PTAS for the capacitated vehicle routing problem in minor-free graphs. We also significantly improve the running time of the QPTAS for the metric Baker's problems in minor-free graphs from n^Oε(log(n)) to n^Oε(loglog(n))3. Applying our embedding technique to planar graphs, we obtain a deterministic embedding of planar graphs of diameter D into graphs of treewidth O((loglog n)2)/ε) and additive distortion +ε D that can be constructed in nearly linear time. Important corollaries of our result include a bicriteria PTAS for metric Baker's problems and a PTAS for the vehicle routing problem with bounded capacity in planar graphs, both run in almost-linear time. The running time of our algorithms is significantly better than previous algorithms that require quadratic time. A key idea in our embedding is the construction of an (exact) emulator for tree metrics with treewidth O(loglog n) and hop-diameter O(log log n). This result may be of independent interest.