Linear-time vertex-connectivity for graphs of bounded genus

Cabello, Sergio (author), Dobler, Alexander (author), Fijavž, Gašper (author), Hamm, Thekla (author), Wagner, Mirko H. (author)

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.

• Language: English
• Keywords: vertex-connectivity, graphs on surfaces, genus of a graph
• Work type: Article
• Typology: 1.08 - Published Scientific Conference Contribution
• Organization: FMF - Faculty of Mathematics and Physics; FRI - Faculty of Computer and Information Science
• Publication status: Published
• Publication version: Version of Record
• Year: 2026
• Number of pages: Str. 56:1-56:15
• PID: 20.500.12556/RUL-186597
• UDC: 004.42:519.17
• ISSN on article: 1868-8969
• DOI: 10.4230/LIPIcs.ESA.2026.56
• COBISS.SI-ID: 289440515
• Publication date in RUL: 03.09.2026

Record is a part of a proceedings

• Title: 34th Annual European Symposium on Algorithms
• COBISS.SI-ID: 289437955

Record is a part of a journal

• Title: Leibniz international proceedings in informatics
• Shortened title: Leibniz int. proc. inform.
• Publisher: Schloss Dagstuhl, Leibniz-Zentrum für Informatik
• ISSN: 1868-8969
• COBISS.SI-ID: 523260441

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.