Probabilistic embeddings of bounded genus graphs into planar graphs

MaRDI QIDQ3602875zbMATH OpenFDO

Authors Anastasios Sidiropoulos, Piotr Indyk

Publication date 12 February 2009

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)

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

Cited in

(14)

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

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)