Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
From MaRDI portal
Publication:5741734
DOI10.1137/1.9781611973105.26zbMath1421.68174arXiv1111.6990OpenAlexW1507614398MaRDI QIDQ5741734
Publication date: 15 May 2019
Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1111.6990
Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Minimum Cuts in Surface Graphs ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Topologically trivial closed walks in directed surface graphs ⋮ Unnamed Item ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable