Finding shortest non-trivial cycles in directed graphs on surfaces

DOI10.1145/1810959.1810988zbMath1284.05272OpenAlexW1995901838MaRDI QIDQ5405878

Éric Colin de Verdière, Sergio Cabello, Francis Lazarus

Publication date: 3 April 2014

Published in: Proceedings of the twenty-sixth annual symposium on Computational geometry (Search for Journal in Brave)

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

zbMATH Keywords

surfacedirected graphembedded graphcomputational topologytopological graph theorynon-contractible cyclenon-separating cycle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Minimum Cuts in Surface Graphs ⋮ Algorithms for the edge-width of an embedded graph ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Topologically trivial closed walks in directed surface graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The complexity of separating points in the plane

This page was built for publication: Finding shortest non-trivial cycles in directed graphs on surfaces