Finding one tight cycle

DOI10.1145/1824777.1824781MaRDI QIDQ2930343zbMATH OpenOpenAlexFDO

Authors S. Cabello, Matt DeVos, Jeff Erickson, Bojan Mohar

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1824777.1824781

zbMATH Keywords

combinatorial surfacenoncontractible cyclenonseparating cycletopological graph theory

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Fundamental group, presentations, free differential calculus (57M05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Tightening nonsimple paths and cycles on surfaces
• Computing the shortest essential cycle
• Shortest non-trivial cycles in directed surface graphs
• Minimum cuts and shortest homologous cycles
• Shortest non-trivial cycles in directed and undirected surface graphs

Cited in

(11)

• Revisiting cycle shrinking
• Topologically trivial closed walks in directed surface graphs
• Algorithms for the edge-width of an embedded graph
• Topologically trivial closed walks in directed surface graphs
• Typical representatives of free homotopy classes in multi-punctured plane
• Tightening nonsimple paths and cycles on surfaces
• Global minimum cuts in surface embedded graphs
• Minimum Cuts in Surface Graphs
• Computing the shortest essential cycle
• The tight orthogonal homotopic bases of closed oriented triangulated surfaces and their computing
• Computing shortest closed curves on non-orientable surfaces

This page was built for publication: Finding one tight cycle

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