Planarizing an unknown surface

DOI10.1007/978-3-642-32512-0_23MaRDI QIDQ3167402zbMATH OpenOpenAlexFDO

Authors Yury Makarychev, Anastasios Sidiropoulos

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.4898

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: It has been recently shown that any graph of genus g>0 can be stochastically embedded into a distribution over planar graphs, with distortion Olog (g+1)) [Sidiropoulos, FOCS 2010]. This embedding can be computed in polynomial time, provided that a drawing of the input graph into a genus-g surface is given. We show how to compute the above embedding without having such a drawing. This implies a general reduction for solving problems on graphs of small genus, even when the drawing into a small genus surface is unknown. To the best of our knowledge, this is the first result of this type.

Recommendations

• Probabilistic embeddings of bounded genus graphs into planar graphs
• Randomly removing \(g\) handles at once
• Randomly removing \(g\) handles at once
• Planar drawings of higher-genus graphs
• Drawing Graphs on Surfaces

Cited in

(5)

• Probabilistic embeddings of bounded genus graphs into planar graphs
• Randomly removing \(g\) handles at once
• Planar drawings of higher-genus graphs
• Planar drawings of higher-genus graphs
• Planarization of graphs embedded on surfaces

This page was built for publication: Planarizing an unknown surface

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