A Face Cover Perspective to <i>ℓ</i> ₁ Embeddings of Planar Graphs

It was conjectured by Gupta et al. 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. In this article, 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 article, Okamura and Seymour 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, was studied by Lee and Sidiropoulos and Chekuri et al. The state of the art is an upper bound of \(O(\log\gamma)\) by Krauthgamer, Lee and Rika. 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.