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  is only O(\log n)  by Rao [SoCG99]. In this paper we study the terminated 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. More generally, suppose that the terminals could be covered by \gamma faces . In a recent paper Krauthgamer, Lee and Rika SODA19%DIFDELCMD < ] %%% showed an upper bound of O(\log \gamma) on the distortion, improving previous results by Lee and Sidiropoulos [STOC09] and Chekuri et . al. [J.Comb.Theory13].  ] Our contribution is a further improvement of the upper bound to O(\sqrt{\log\gamma}). Note that since every planar graph has at most O(n) faces, any further improvement of this result, will imply an improvement upon Rao's long standing upper bound. It is well known that the flow-cut gap equals to the distortion of the best embedding into \ell_1. In particular , our result provide a polynomial time O(\sqrt{\log \gamma})-approximation to the sparsest cut problem on planar graph , for the case where all the demand pairs can be covered by \gamma faces.
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(\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 \gamma faces %DIFDELCMD < ] %%% , 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 \gamma) by Krauthgamer, Lee and Rika SODA19]. Our contribution is a further improvement on the upper bound to O(\sqrt{\log\gamma}). 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 \gamma})-approximation to the sparsest cut problem on planar graphs , for the case where all the demand pairs can be covered by \gamma faces.
D
.
A
on the distortion
A
,
R
terminated case ,
case
R
More generally, suppose that the terminals could
The more general case, where the set of terminals can
D
. In a recent paper Krauthgamer, Lee and Rika
D
SODA19
R
showed an upper bound of O(\log \gamma) on the distortion, improving previous results
, was studied
D
.
A
The state of the art is an upper bound of O(\log \gamma) by Krauthgamer, Lee and Rika
A
SODA19
A
.
R
of
on
R
Note that since
Since
R
of
on
R
imply an improvement
be a major breakthrough, directly improving
R
It
Moreover, it
R
In particular
Therefore
R
provide
provides
R
graph
graphs