2026-08-17T16:23:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5915 2024-03-06T10:37:16Z ddc:004 open_access

Minimum Cycle and Homology Bases of Surface Embedded Graphs Borradaile, Glencora Chambers, Erin Wolf Fox, Kyle Nayyeri, Amir Cycle basis Homology basis Topological graph theory 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 (Z_2)-homology classes) of an undirected graph embedded on an orientable surface of genus g. 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^omega + 2^2g n^2)-time algorithm. The best known existing algorithms for surface embedded graphs are those for general sparse graphs: an O(n^omega) time Monte Carlo algorithm [Amaldi et. al., ESA'09] and a deterministic O(n^3) time algorithm [Mehlhorn and Michail, TALG'09]. For the minimum homology basis problem, we give an O(g^3 n log n)-time algorithm, improving on existing algorithms for many values of g and n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Glencora Borradaile and Erin Wolf Chambers and Kyle Fox and Amir Nayyeri 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.23 urn:nbn:de:0030-drops-59152 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.23 eng https://creativecommons.org/licenses/by/3.0/legalcode