Probabilistic embeddings of bounded genus graphs into planar graphs

Abstract

A probabilistic C-embedding of a (guest) metric M into a collection of(host) metrics M'1, ..., M'k is a randomized mapping F of M intoone of the M'1, ..., M'k such that, for any two points p,q in theguest metric: The distance between F(p) and F(q) in any M'i is not smaller thanthe original distance between p and q. The expected distance between F(p) and F(q) in (random) M'i is notgreater than some constant C times the original distance, for C≥ 1. The constant C is called the distortion of the embedding. Low-distortion probabilistic embeddings enable reducing algorithmicproblems over "hard" guest metrics into "easy" host metrics.We show that every metric induced by a graph of bounded genus can beprobabilistically embedded into planar graphs, with constant distortion. The embedding can be computed efficiently, given a drawing of the graphon a genus-g surface.