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

crossingsembedded graphhomology basisnonseparating cycletopological graph theory

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(5)

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

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)