OREGON STATE UNIVERSITY

You are here

Randomly Removing G Handles at Once

TitleRandomly Removing G Handles at Once
Publication TypeJournal Article
Year of Publication2010
AuthorsBorradaile, G., J. R. Lee, and A. Sidiropoulos
JournalComputational Geometry
Volume43
Issue8
Pagination655 - 662
Date Published10/2010
ISSN09257721
Keywordsgenus, metric embeddings, planar graphs
Abstract

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 2O(g), by iteratively removing the handles. 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 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).

DOI10.1016/j.comgeo.2010.04.007
Short TitleComputational Geometry