Computing the shortest essential cycle

DOI10.1007/s00454-010-9241-8zbMath1207.68417OpenAlexW2102559438MaRDI QIDQ603870

Pratik Worah, Jeff Erickson

Publication date: 8 November 2010

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-010-9241-8

zbMATH Keywords

computational topologytopological graph theorycombinatorial surfaceessential cycles

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Approximation Algorithms for Euler Genus and Related Problems, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Derandomizing Isolation in Space-Bounded Settings, Unnamed Item, Discrete systolic inequalities and decompositions of triangulated surfaces

Cites Work

• A note on two problems in connexion with graphs
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Embeddings of graphs with no short noncontractible cycles
• Splitting (complicated) surfaces is hard
• Matching is as easy as matrix inversion
• Convexity in graphs
• Optimally cutting a surface into a disk
• Singular Lagrangian manifolds and semiclassical analysis.
• Optimal pants decompositions and shortest homotopic cycles on an orientable surface
• Tightening non-simple paths and cycles on surfaces
• Combinatorics of Train Tracks. (AM-125)
• A Panoramic View of Riemannian Geometry
• Topology for Computing
• Computing a canonical polygonal schema of an orientable triangulated surface
• Randomly removing g handles at once
• Minimum cuts and shortest homologous cycles
• Many distances in planar graphs
• Faster shortest-path algorithms for planar graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item