Metraipolis › archive › dc_33efdf2a2394

Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into $\ell_1$ and Trees with a Polynomial Distortion (in $k$) — arXiv:2610.10888

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.10888
License (as archived)
CC0-1.0
Archived
2026-10-09T06:36:21.128Z
SHA-256 of the archived text
861dba5b8ec288581c5663387bd0d20e6c33b06c6f4e5f5211a8e6f7bc1c208e
Stable URL of this page
https://metraipolis.com/documento/dc_33efdf2a2394

How to cite

Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into $\ell_1$ and Trees with a Polynomial Distortion (in $k$) — arXiv:2610.10888 — arXiv (en), https://arxiv.org/abs/2610.10888 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_33efdf2a2394 (Metraipolis archive dc_33efdf2a2394, sha256 861dba5b8ec288581c5663387bd0d20e6c33b06c6f4e5f5211a8e6f7bc1c208e)
BibTeX
@misc{dc33efdf2a2394,
  title = {Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into $ell_1$ and Trees with a Polynomial Distortion (in $k$) — arXiv:2610.10888},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.10888},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_33efdf2a2394; sha256 861dba5b8ec288581c5663387bd0d20e6c33b06c6f4e5f5211a8e6f7bc1c208e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10888. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that $k$-outerplanar graphs can be embedded into trees and $\ell_1$ with distortion $2^{O(k)}$. Their result is perhaps the strongest evidence supporting the still-open planar $\ell_1$-embedding conjecture: planar metrics can be embedded into $\ell_1$ with constant distortion. However, the exponential dependency on $k$ in their distortion bound remains the state of the art. Their embedding is obtained by a so-called onion-peeling approach: removing one layer of the graph at a time at the cost of incurring $O(1)$ distortion multiplicatively, and recursively embedding the resulting $(k-1)$-outerplanar graph. In this paper, we devise a new onion peeling approach that peels $k/2$ layers off the input $k$-outerplanar graph at every step. As a result, we obtain the first embedding of $k$-outerplanar graphs into trees and $\ell_1$ with distortion $\operatorname{poly}(k)$, an exponential improvement over the best-known distortion bound [SODA'03]. Our result of embeddings into trees comes closer to the distortion lower bound $\Omega(k)$ for $k$-outerplanar graphs.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Geometry (cs.CG).
Pagina del lavoro: https://arxiv.org/abs/2610.10888 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:57:12.696Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).