Randomly removing g handles at once
Glencora Borradaile, James Lee and Anastasios Sidiropoulos
It was shown in [Indyk-Sidiropoulos 07] that any orientable graph of genus g can be probabilistically embedded into a graph of genus g-1 with constant distortion. Removing handles one by one gives an embedding into a distribution over planar graphs with distortion 2O(g). By removing all g handles at once, we present a probabilistic embedding with distortion O(g2) for both orientable and non-orientable graphs. Our result is obtained by showing that the minimum-cut graph of [Erickson-HarPeled 04] has low dilation, and then randomly cutting this graph out of the surface using the Peeling Lemma from [Lee-Sidiropoulos 08].
Proceedings of the Annual Symposium on Computational Geometry (SoCG), Aarhus, Denmark, 2009.
[ doi ] [ journal version available ]
