Erickson, Jeff ;
Wang, Yipu
Topologically Trivial Closed Walks in Directed Surface Graphs
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 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 contractibleclosedwalk algorithm also relies on a seminal topological result of Hass and Scott. We also prove that detecting simple bounding cycles is NPhard.
We also describe three polynomialtime 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 contextfree grammar with O(g^2L^2) nonterminals 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 NPhard.
BibTeX  Entry
@InProceedings{erickson_et_al:LIPIcs:2019:10438,
author = {Jeff Erickson and Yipu Wang},
title = {{Topologically Trivial Closed Walks in Directed Surface Graphs}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {34:134:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10438},
URN = {urn:nbn:de:0030drops104383},
doi = {10.4230/LIPIcs.SoCG.2019.34},
annote = {Keywords: computational topology, surfaceembedded graphs, homotopy, homology, strong connectivity, hyperbolic geometry, medial axes, contextfree grammars}
}
11.06.2019
Keywords: 

computational topology, surfaceembedded graphs, homotopy, homology, strong connectivity, hyperbolic geometry, medial axes, contextfree grammars 
Seminar: 

35th International Symposium on Computational Geometry (SoCG 2019)

Issue date: 

2019 
Date of publication: 

11.06.2019 