Computing the stretch of an embedded graph

DOI10.1137/130945636MaRDI QIDQ2935274zbMATH OpenOpenAlexFDO

Authors S. Cabello, Markus Chimani, Petr Hliněný

Publication date 22 December 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://idus.us.es/handle/11441/60027

zbMATH Keywords

embedded graphcrossingstopological graph theoryhomology basisnonseparating cycle

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Nonnumerical algorithms (68W05) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Recommendations

• Algorithms for the edge-width of an embedded graph
• Minimum cuts and shortest homologous cycles
• Minimum Cuts in Surface Graphs

Cited in

(4)

• Toroidal grid minors and stretch in embedded graphs
• Approximating the Stretch Factor of Euclidean Graphs
• Algorithms for length spectra of combinatorial tori
• Stress of a graph and its computation

This page was built for publication: Computing the stretch of an embedded graph

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