# Minimum cycle and homology bases of surface embedded graphs

arXiv: https://arxiv.org/abs/1607.05112 · HTML: https://mlsanity.com/paper/1607.05112/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2016.

## Built on by (most cited first, 2 of 2)

- [Dist2Cycle: A Simplicial Neural Network for Homology Localization](https://mlsanity.com/paper/2110.15182/) (2021)
- [Geometric Localization of Homology Cycles](https://mlsanity.com/paper/2406.03183/) (2024)

## Abstract (arXiv)

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 (mathbbZ2)-homology classes) of an undirected graph 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ω+22gn2+m)-time algorithm for graphs embedded on an orientable surface of genus g. The best known existing algorithms for surface embedded graphs are those for general graphs: an O(mω) time Monte Carlo algorithm and a deterministic O(nm2/log n + n2 m) time algorithm. For the minimum homology basis problem, we give a deterministic O((g+b)3 n log n + m)-time algorithm for graphs embedded on an orientable or non-orientable surface of genus g with b boundary components, assuming shortest paths are unique, improving on existing algorithms for many values of g and n. The assumption of unique shortest paths can be avoided with high probability using randomization or deterministically by increasing the running time of the homology basis algorithm by a factor of O(log n).