TY - GEN

T1 - Topologically trivial closed walks in directed surface graphs

AU - Erickson, Jeff

AU - Wang, Yipu

N1 - Funding Information:
Research on this paper was partially supported by NSF grant CCF-1408763.
Publisher Copyright:
© Jeff Erickson and Yipu Wang.

PY - 2019/6/1

Y1 - 2019/6/1

N2 - Let G be a directed graph with n vertices and m edges, embedded on a surface S, possibly with boundary, with first Betti number β. 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(β(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(g2L2) 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.

AB - Let G be a directed graph with n vertices and m edges, embedded on a surface S, possibly with boundary, with first Betti number β. 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(β(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(g2L2) 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.

KW - Computational topology

KW - Context-free grammars

KW - Homology

KW - Homotopy

KW - Hyperbolic geometry

KW - Medial axes

KW - Strong connectivity

KW - Surface-embedded graphs

UR - http://www.scopus.com/inward/record.url?scp=85068089597&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068089597&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2019.34

DO - 10.4230/LIPIcs.SoCG.2019.34

M3 - Conference contribution

AN - SCOPUS:85068089597

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 35th International Symposium on Computational Geometry, SoCG 2019

A2 - Barequet, Gill

A2 - Wang, Yusu

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 35th International Symposium on Computational Geometry, SoCG 2019

Y2 - 18 June 2019 through 21 June 2019

ER -