Randomly removing g handles at once

Glencora Borradaile, James R. Lee, Anastasios Sidiropoulos

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…