2026-08-25T15:33:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27192 2026-08-25T13:18:17Z ddc:004 open_access

Linear-Time Vertex-Connectivity for Graphs of Bounded Genus Cabello, Sergio Dobler, Alexander Fijavž, Gašper Hamm, Thekla Wagner, Mirko H. vertex-connectivity graphs on surfaces genus of a graph We provide a new linear-time algorithm for determining the vertex-connectivity of graphs with bounded genus. This generalizes and streamlines a linear-time algorithm for graphs with bounded crossing number which was recently obtained by Biedl, Bose and Murali [ESA 2024]. Compared to applying the even more recent fixed parameter linear-time algorithm for deciding bounded vertex-connectivity announced by Korhonen [STOC 2025] to graphs of bounded genus,our algorithm is far simpler, its correctness easier to establish, and it makes use of geometric ideas, as is natural for surface-embedded graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sergio Cabello and Alexander Dobler and Gašper Fijavž and Thekla Hamm and Mirko H. Wagner 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.56 urn:nbn:de:0030-drops-271923 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.56 eng https://creativecommons.org/licenses/by/4.0/legalcode