Topologically trivial closed walks in directed surface graphs

Jeff Erickson, Yipu Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication35th International Symposium on Computational Geometry, SoCG 2019
EditorsGill Barequet, Yusu Wang
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771047
DOIs
StatePublished - Jun 1 2019
Event35th International Symposium on Computational Geometry, SoCG 2019 - Portland, United States
Duration: Jun 18 2019Jun 21 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume129
ISSN (Print)1868-8969

Conference

Conference35th International Symposium on Computational Geometry, SoCG 2019
CountryUnited States
CityPortland
Period6/18/196/21/19

Keywords

  • Computational topology
  • Context-free grammars
  • Homology
  • Homotopy
  • Hyperbolic geometry
  • Medial axes
  • Strong connectivity
  • Surface-embedded graphs

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Topologically trivial closed walks in directed surface graphs'. Together they form a unique fingerprint.

Cite this