Randomly removing g handles at once

Details Randomly removing g handles at once Randomly removing g handles at once

2010-03-07

arxiv.org/abs/1003.1426v1

Computer Science

Computational Geometry

Scientific paper

Indyk and Sidiropoulos (2007) proved that any orientable graph of genus $g$ can be probabilistically embedded into a graph of genus $g-1$ with constant distortion. Viewing a graph of genus $g$ as embedded on the surface of a sphere with $g$ handles attached, Indyk and Sidiropoulos' method gives an embedding into a distribution over planar graphs with distortion $2^{O(g)}$, by iteratively removing the handles. By removing all $g$ handles at once, we present a probabilistic embedding with distortion $O(g^2)$ for both orientable and non-orientable graphs. Our result is obtained by showing that the nimum-cut graph of Erickson and Har Peled (2004) has low dilation, and then randomly cutting this graph out of the surface using the Peeling Lemma of Lee and Sidiropoulos (2009).

Affiliated with

Also associated with

No associations

Rating

Randomly removing g handles at once does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Randomly removing g handles at once, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomly removing g handles at once will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-667402