A face cover perspective to $\ell_1$ embeddings of planar graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909270770974720 |
|---|---|
| author | Filtser, Arnold |
| author_facet | Filtser, Arnold |
| contents | It was conjectured by Gupta et al. [Combinatorica04] that every planar graph can be embedded into $\ell_1$ with constant distortion. However, given an $n$-vertex weighted planar graph, the best upper bound on the distortion is only $O(\sqrt{\log n})$, by Rao [SoCG99]. In this paper we study the case where there is a set $K$ of terminals, and the goal is to embed only the terminals into $\ell_1$ with low distortion. In a seminal paper, Okamura and Seymour [J.Comb.Theory81] showed that if all the terminals lie on a single face, they can be embedded isometrically into $\ell_1$. The more general case, where the set of terminals can be covered by $γ$ faces, was studied by Lee and Sidiropoulos [STOC09] and Chekuri et al. [J.Comb.Theory13]. The state of the art is an upper bound of $O(\log γ)$ by Krauthgamer, Lee and Rika [SODA19]. Our contribution is a further improvement on the upper bound to $O(\sqrt{\logγ})$. Since every planar graph has at most $O(n)$ faces, any further improvement on this result, will be a major breakthrough, directly improving upon Rao's long standing upper bound. Moreover, it is well known that the flow-cut gap equals to the distortion of the best embedding into $\ell_1$. Therefore, our result provides a polynomial time $O(\sqrt{\log γ})$-approximation to the sparsest cut problem on planar graphs, for the case where all the demand pairs can be covered by $γ$ faces. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1903_02758 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | A face cover perspective to $\ell_1$ embeddings of planar graphs Filtser, Arnold Data Structures and Algorithms Computational Geometry It was conjectured by Gupta et al. [Combinatorica04] that every planar graph can be embedded into $\ell_1$ with constant distortion. However, given an $n$-vertex weighted planar graph, the best upper bound on the distortion is only $O(\sqrt{\log n})$, by Rao [SoCG99]. In this paper we study the case where there is a set $K$ of terminals, and the goal is to embed only the terminals into $\ell_1$ with low distortion. In a seminal paper, Okamura and Seymour [J.Comb.Theory81] showed that if all the terminals lie on a single face, they can be embedded isometrically into $\ell_1$. The more general case, where the set of terminals can be covered by $γ$ faces, was studied by Lee and Sidiropoulos [STOC09] and Chekuri et al. [J.Comb.Theory13]. The state of the art is an upper bound of $O(\log γ)$ by Krauthgamer, Lee and Rika [SODA19]. Our contribution is a further improvement on the upper bound to $O(\sqrt{\logγ})$. Since every planar graph has at most $O(n)$ faces, any further improvement on this result, will be a major breakthrough, directly improving upon Rao's long standing upper bound. Moreover, it is well known that the flow-cut gap equals to the distortion of the best embedding into $\ell_1$. Therefore, our result provides a polynomial time $O(\sqrt{\log γ})$-approximation to the sparsest cut problem on planar graphs, for the case where all the demand pairs can be covered by $γ$ faces. |
| title | A face cover perspective to $\ell_1$ embeddings of planar graphs |
| topic | Data Structures and Algorithms Computational Geometry |
| url | https://arxiv.org/abs/1903.02758 |