2026-08-10T23:32:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10438 2024-03-06T10:45:59Z ddc:004 open_access

Topologically Trivial Closed Walks in Directed Surface Graphs Erickson, Jeff Wang, Yipu computational topology surface-embedded graphs homotopy homology strong connectivity hyperbolic geometry medial axes context-free grammars Let G be a directed graph with n vertices and m edges, embedded on a surface S, possibly with boundary, with first Betti number beta. We consider the complexity of finding closed directed walks in G that are either contractible (trivial in homotopy) or bounding (trivial in integer homology) in S. Specifically, we describe algorithms to determine whether G contains a simple contractible cycle in O(n+m) time, or a contractible closed walk in O(n+m) time, or a bounding closed walk in O(beta (n+m)) time. Our algorithms rely on subtle relationships between strong connectivity in G and in the dual graph G^*; our contractible-closed-walk algorithm also relies on a seminal topological result of Hass and Scott. We also prove that detecting simple bounding cycles is NP-hard. We also describe three polynomial-time algorithms to compute shortest contractible closed walks, depending on whether the fundamental group of the surface is free, abelian, or hyperbolic. A key step in our algorithm for hyperbolic surfaces is the construction of a context-free grammar with O(g^2L^2) non-terminals that generates all contractible closed walks of length at most L, and only contractible closed walks, in a system of quads of genus g >= 2. Finally, we show that computing shortest simple contractible cycles, shortest simple bounding cycles, and shortest bounding closed walks are all NP-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeff Erickson and Yipu Wang 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.34 urn:nbn:de:0030-drops-104383 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.34 eng https://creativecommons.org/licenses/by/3.0/legalcode