Computing the shortest essential cycle

DOI10.1007/S00454-010-9241-8zbMATH Open1207.68417OpenAlexW2102559438MaRDI QIDQ603870FDOQ603870

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)

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)