Randomly removing g handles at once
Glencora Borradailea, James R. Leeb, Anastasios Sidiropoulosc
- aUniversity of Waterloo, Waterloo, ON, Canada
- bUniversity of Washington, Seattle, WA, USA
- cUniversity of Toronto, Toronto, ON, Canada
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
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].
TL;DRBy removing all $g$ handles at once, this work presents a probabilistic embedding with distortion O(g2) for both orientable and non-orientable graphs. (Semantic Scholar)