Computing the shortest essential cycle

DOI10.1007/S00454-010-9241-8MaRDI QIDQ603870zbMATH OpenOpenAlexFDO

Authors Jeff Erickson, Pratik Worah

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38)

Recommendations

• Finding one tight cycle
• Tightening nonsimple paths and cycles on surfaces
• Shortest non-trivial cycles in directed surface graphs
• Shortest non-trivial cycles in directed and undirected surface graphs

Cites work

• scientific article; zbMATH DE number 6381654 (Why is no real title available?)
• scientific article; zbMATH DE number 5485473 (Why is no real title available?)
• scientific article; zbMATH DE number 5485559 (Why is no real title available?)
• scientific article; zbMATH DE number 5764895 (Why is no real title available?)
• scientific article; zbMATH DE number 5506235 (Why is no real title available?)
• scientific article; zbMATH DE number 52136 (Why is no real title available?)
• scientific article; zbMATH DE number 2079390 (Why is no real title available?)
• scientific article; zbMATH DE number 194437 (Why is no real title available?)
• A Panoramic View of Riemannian Geometry
• A note on two problems in connexion with graphs
• A primer on mapping class groups
• Combinatorics of Train Tracks. (AM-125)
• Computing a canonical polygonal schema of an orientable triangulated surface
• Convexity in graphs
• Embeddings of graphs with no short noncontractible cycles
• Faster shortest-path algorithms for planar graphs
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Graphs on surfaces
• Greedy optimal homotopy and homology generators
• Many distances in planar graphs
• Matching is as easy as matrix inversion
• Minimum cuts and shortest homologous cycles
• Multiple source shortest paths in a genus \(g\) graph
• Optimal pants decompositions and shortest homotopic cycles on an orientable surface
• Optimally cutting a surface into a disk
• Probabilistic embeddings of bounded genus graphs into planar graphs
• Randomly removing \(g\) handles at once
• Singular Lagrangian manifolds and semiclassical analysis.
• Splitting (complicated) surfaces is hard
• Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition
• Tightening non-simple paths and cycles on surfaces
• Topology for Computing

Cited in

(9)

• Optimal system of loops on an orientable surface
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Derandomizing isolation in space-bounded settings
• Approximation algorithms for Euler genus and related problems
• Splitting (complicated) surfaces is hard
• Finding one tight cycle
• Tightening nonsimple paths and cycles on surfaces
• Global minimum cuts in surface embedded graphs
• scientific article; zbMATH DE number 6027233 (Why is no real title available?)

This page was built for publication: Computing the shortest essential cycle

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