Randomly removing g handles at once

DOI10.1016/J.COMGEO.2010.04.007MaRDI QIDQ991176zbMATH OpenOpenAlexFDO

Authors Glencora Borradaile, James R. Lee, Anastasios Sidiropoulos

Publication date 2 September 2010

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2010.04.007

zbMATH Keywords

genusplanar graphsmetric embeddings

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15)

Recommendations

• Randomly removing \(g\) handles at once
• Random triangle removal
• Removing independently even crossings
• Removing Independently Even Crossings
• Random sampling with removal
• Random sampling with removal
• On deleting coordinates from integer vectors
• Deletion along trajectories
• Random marginal and random removal values

Cites work

• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• A tight bound on approximating arbitrary metrics by tree metrics
• Algorithms – ESA 2004
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Excluded minors, network decomposition, and multicommodity flow
• Extending Lipschitz functions via random metric partitions
• Graphs on surfaces
• On the geometry of graphs with a forbidden minor
• Optimally cutting a surface into a disk
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Probabilistic embeddings of bounded genus graphs into planar graphs

Cited in

(5)

• Probabilistic embeddings of bounded genus graphs into planar graphs
• Planarizing an unknown surface
• Argument deletion without events
• Randomly removing \(g\) handles at once
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs

This page was built for publication: Randomly removing \(g\) handles at once

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991176)