Probabilistic Embeddings of Bounded Genus Graphs Into Planar Graphs

Anastasios Sidiropoulos

MIT

Abstract

Probabilistic embeddings of metric spaces provide a general paradigm for simplifying the input of a broad class of geometric optimization problems, and have found numerous applications to the design of approximation algorithms.

We show that every metric induced by a graph of bounded genus can be probabilistically embedded into planar graphs, with constant distortion. The embedding can be computed efficiently, given a drawing of the graph on a genus-g surface.

This result implies in particular that certain optimization problems over graphs of bounded genus, can be reduced to problems over planar graphs, with a constant loss in the objective function. There are also implications on the embeddability of bounded genus graphs into ell_1.

The talk will be self-contained.

Joint work with Piotr Indyk