research-article

Randomly removing g handles at once

Authors:

Glencora Borradaile,

Anastasios SidiropoulosAuthors Info & Claims

SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

Pages 371 - 376

https://doi.org/10.1145/1542362.1542425

Published: 08 June 2009 Publication History

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 2^O(g). By removing all $g$ handles at once, we present a probabilistic embedding with distortion O(g²) 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].

References

[1]

B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. ACM, 41(1):153--180, 1994.

Digital Library

[2]

Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. Annual Symposium on Foundations of Computer Science, 1996.

Digital Library

[3]

G. Borradaile. Exploiting Planarity for Network Flow and Connectivity Problems. PhD thesis, Brown University, 2008.

Digital Library

[4]

G. Borradaile, E. Demaine, and S. Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded genus graphs. In Proceedings of STACS, 2009.

[5]

D. E. Carroll and A. Goel. Lower bounds for embedding into distributions over excluded minor graph families. In ESA, pages 146--156, 2004.

[6]

J. Erickson and S. Har-Peled. Optimally cutting a surface into a disk. Discrete & Computational Geometry, 31(1):37--59, 2004.

Digital Library

[7]

J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 448--455, 2003.

Digital Library

[8]

J. Fakcharoenphol and K. Talwar. An improved decomposition theorem for graphs excluding a fixed minor. In Proceedings of 6th Workshop on Approximation, Randomization, and Combinatorial Optimization, volume 2764 of Lecture Notes in Computer Science, pages 36--46. Springer, 2003.

[9]

A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Cuts, trees and l 1-embeddings of graphs. In 40th Annual Symposium on Foundations of Computer Science, pages 399--408. IEEE Computer Soc., Los Alamitos, CA, 1999.

Digital Library

[10]

P. Indyk. Tutorial: Algorithmic applications of low-distortion geometric embeddings. Annual Symposium on Foundations of Computer Science, 2001.

Digital Library

[11]

P. Indyk and A. Sidiropoulos. Probabilistic embeddings of bounded genus graphs into planar graphs. In Proceedings of the 23rd Annual Symposium on Computational Geometry. ACM, 2007.

Digital Library

[12]

P. N. Klein, S. A. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 682--690, 1993.

Digital Library

[13]

J. R. Lee and A. Sidiropoulos. On the geometry of graphs with a forbidden minor. To appear, Proceddings of the 41st Annual ACM Symposium on the Theory of Computing, 2009.

Digital Library

[14]

J. Matousek. Lectures on Discrete Geometry. Springer, 2002.

Digital Library

[15]

B. Mohar and C. Thomassen. Graphs on Surfaces. John Hopkins, 2001.

[16]

S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the 15th Annual Symposium on Computational Geometry, pages 300--306, New York, 1999. ACM.

Digital Library

Cited By

Mémoli FSidiropoulos ASridhar V(2018)Quasimetric Embeddings and Their ApplicationsAlgorithmica10.5555/3288645.328866180:12(3803-3824)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.5555/3288645.3288661
Mémoli FSidiropoulos ASridhar V(2018)Quasimetric Embeddings and Their ApplicationsAlgorithmica10.1007/s00453-018-0415-880:12(3803-3824)Online publication date: 13-Feb-2018
https://doi.org/10.1007/s00453-018-0415-8
Fox KKhanna S(2013)Shortest non-trivial cycles in directed and undirected surface graphsProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627843(352-364)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627843
Show More Cited By

Index Terms

Randomly removing g handles at once
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Probabilistic embeddings of bounded genus graphs into planar graphs
SCG '07: Proceedings of the twenty-third annual symposium on Computational geometry

A probabilistic C-embedding of a (guest) metric M into a collection of(host) metrics M'₁, ..., M'_k is a randomized mapping F of M intoone of the M'₁, ..., M'_k such that, for any two points p,q in theguest metric: The distance between F(p) and F(q) in ...
Randomly removing g handles at once

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, ...
Linear kernels for k-tuple and liars domination in bounded genus graphs

A set DV is called a k-tuple dominating set of a graph G=(V,E) if |NG[v]D|k for all vV, where NG[v] denotes the closed neighborhood of v. A set DV is called a liars dominating set of a graph G=(V,E) if (i) |NG[v]D|2 for all vV and (ii) for every pair of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

June 2009

426 pages

ISBN:9781605585017

DOI:10.1145/1542362

Program Chairs:
John Hershberger
Mentor Graphics Corp.
,
Efi Fogel
Tel Aviv University

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '09

Sponsor:

SoCG '09: 25th Annual Symposium on Computational Geometry

June 8 - 10, 2009

Aarhus, Denmark

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
100
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mémoli FSidiropoulos ASridhar V(2018)Quasimetric Embeddings and Their ApplicationsAlgorithmica10.5555/3288645.328866180:12(3803-3824)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.5555/3288645.3288661
Mémoli FSidiropoulos ASridhar V(2018)Quasimetric Embeddings and Their ApplicationsAlgorithmica10.1007/s00453-018-0415-880:12(3803-3824)Online publication date: 13-Feb-2018
https://doi.org/10.1007/s00453-018-0415-8
Fox KKhanna S(2013)Shortest non-trivial cycles in directed and undirected surface graphsProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627843(352-364)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627843
Makarychev YSidiropoulos A(2012)Planarizing an Unknown SurfaceApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-32512-0_23(266-275)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32512-0_23
Erickson JNayyeri ARandall D(2011)Minimum cuts and shortest non-separating cycles via homology coversProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133124(1166-1176)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133124
Erickson JHurtado Fvan Kreveld M(2011)Shortest non-trivial cycles in directed surface graphsProceedings of the twenty-seventh annual symposium on Computational geometry10.1145/1998196.1998231(236-243)Online publication date: 13-Jun-2011
https://dl.acm.org/doi/10.1145/1998196.1998231
Erickson JWorah P(2010)Computing the Shortest Essential CycleDiscrete & Computational Geometry10.5555/3115964.311608944:4(912-930)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.5555/3115964.3116089
Chekuri CShepherd FWeibel CCharikar M(2010)Flow-cut gaps for integer and fractional multiflowsProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873697(1198-1208)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.5555/1873601.1873697
Sidiropoulos A(2010)Optimal Stochastic PlanarizationProceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science10.1109/FOCS.2010.23(163-170)Online publication date: 23-Oct-2010
https://dl.acm.org/doi/10.1109/FOCS.2010.23
Erickson JWorah P(2010)Computing the Shortest Essential CycleDiscrete & Computational Geometry10.1007/s00454-010-9241-844:4(912-930)Online publication date: 28-Jan-2010
https://doi.org/10.1007/s00454-010-9241-8

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents