Polynomial distortion found for embedding k-outerplanar graphs into trees and l1
Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into $\ell_1$ and Trees with a Polynomial Distortion (in $k$)
Data Structures and AlgorithmsComputational Geometry
Summary
Embedding certain types of graphs called k-outerplanar graphs into simpler structures like trees or into a type of geometric space called ℓ1 helps understand their complexity and structure. A previous method peeled off one layer at a time, causing the distortion (loss of accuracy) to grow exponentially with k. The authors developed a new method that removes half the layers at each step, reducing distortion growth to a polynomial rate. This improves on the best-known results and gets closer to known lower bounds on distortion.
What this means in practice
- •For network architects: Design hierarchical networks with more accurate approximations by embedding routing structures into simpler tree models with lower distortion.
- •For computer graphics developers: Improve layout algorithms for planar graph-based visualizations by using polynomial distortion embeddings to reduce complexity.
A theory result. No direct application yet.
Authors
Hsien-Chih Chang, Jonathan Conroy, William Eliot, Hung Le, Vinayak
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.