2026-07-24T21:15:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17298 2024-03-06T10:59:23Z ddc:004 open_access

Computation of Cycle Bases in Surface Embedded Graphs Fox, Kyle Stanley, Thomas cycle basis surface embedded graphs homology We present an O(n³ g²log g + m) + Õ(n^{ω + 1}) time deterministic algorithm to find the minimum cycle basis of a directed graph embedded on an orientable surface of genus g. This result improves upon the previous fastest known running time of O(m³n + m²n² log n) applicable to general directed graphs. While an O(n^ω + 2^{2g}n² + m) time deterministic algorithm was known for undirected graphs, the use of the underlying field ℚ in the directed case (as opposed to ℤ₂ for the undirected case) presents extra challenges. It turns out that some of our new observations are useful for both variants of the problem, so we present an O(n^ω + n² g² log g + m) time deterministic algorithm for undirected graphs as well. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kyle Fox and Thomas Stanley 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.13 urn:nbn:de:0030-drops-172982 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.13 eng https://creativecommons.org/licenses/by/4.0/legalcode