arXiv preprint ·
Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into $\ell_1$ and Trees with a Polynomial Distortion (in $k$)
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 $Ω(k)$ for $k$-outerplanar graphs.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Rubix: Global Correspondence-Free Point Set Alignment through Assignment Geometry
The Geometry of Hierarchical Navigation: Accuracy and Query Cost for Point Process Input
Deterministic Distance Selection in $O(n^{4/3})$ Time
Ellipsoids from Tangents
On the Parameterized Complexity of Capacitated Stack and Queue Layouts with Colored Edges
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.