Minimum cycle and homology bases of surface-embedded graphs

Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, Amir Nayyeri

Abstract


We study the problems of finding a minimum cycle basis (a minimum-weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum-weight set of cycles that generates the 1-dimensional $(\mathbb{Z}_2)$-homology classes) of an undirected graph cellularly embedded on a surface. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis.

For the minimum cycle basis problem, we give a deterministic $O(n^ω + 2^{2g} n^2 + m)$-time algorithm for graphs cellularly embedded on an orientable surface of genus $g$. Prior to this work, the best known algorithms for surface-embedded graphs were those for general graphs: an $O(m^ω)$-time Monte Carlo algorithm and a deterministic $O(nm^2/\log n + n^2m)$-time algorithm.

For the minimum homology basis problem, we give a deterministic $O((g + b)^3n\log n + m)$-time algorithm for graphs cellularly embedded on an orientable or non-orientable surface of genus $g$ with $b$ boundary components, improving on existing algorithms for many values of $g$ and $n$. The algorithm assumes that shortest paths are unique; this assumption can be avoided by either using random perturbations of the edge weights guaranteeing a high probability of success or by deterministic means at a cost of an $O(\log n)$ factor increase in running time. 


Full Text:

PDF


DOI: http://dx.doi.org/10.20382/jocg.v8i2a4

ISSN: 1920-180X