Probabilistic embeddings of bounded genus graphs into planar graphs

zbMATH Open1207.05040MaRDI QIDQ3602875FDOQ3602875

Authors: Anastasios Sidiropoulos, Piotr Indyk 

Publication date: 12 February 2009

Recommendations

• Planarizing an unknown surface
• Randomly removing \(g\) handles at once
• Plane embeddings of planar graph metrics
• Plane embeddings of planar graph metrics
• A lower bound on the distortion of embedding planar metrics into Euclidean space

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (14)

• Local certification of graphs with bounded genus
• A note on multiflows and treewidth
• Shortest path embeddings of graphs on surfaces
• Randomly removing \(g\) handles at once
• Planarizing an unknown surface
• A tight upper bound on the probabilistic embedding of series-parallel graphs
• Pathwidth, trees, and random embeddings
• Computing the shortest essential cycle
• Randomly removing \(g\) handles at once
• \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees
• Shortest path embeddings of graphs on surfaces
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• The random graph embeds in the curve graph of any infinite genus surface
• Quasimetric embeddings and their applications

This page was built for publication: Probabilistic embeddings of bounded genus graphs into planar graphs

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