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)

• 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
• Computing the shortest essential cycle
• A tight upper bound on the probabilistic embedding of series-parallel graphs
• Pathwidth, trees, and random embeddings
• Randomly removing \(g\) handles at once
• \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees
• Shortest path embeddings of graphs on surfaces
• The random graph embeds in the curve graph of any infinite genus surface
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• 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)