A face cover perspective to ℓ 1 embeddings of planar graphs
Arnold Filtser · Society for Industrial and Applied Mathematics eBooks · 2019
It was conjectured by Gupta et al. [Combinatorica04] 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 , 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 . 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 -approximation to the sparsest cut problem on planar graphs, for the case where all the demand pairs can be covered by γ faces.