A face cover perspective to ℓ1 embeddings of planar graphs

It was conjectured by that every planar graph can be embedded into ℓ 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 ℓ 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 ℓ 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( √ 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 ℓ 1 . Therefore, our result provides a polynomial time O( √ log γ)approximation to the sparsest cut problem on planar graphs, for the case where all the demand pairs can be covered by γ faces.