Linear-time vertex-connectivity for graphs of bounded genus

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

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.

• Jezik: Angleški jezik
• Ključne besede: vertex-connectivity, graphs on surfaces, genus of a graph
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
• Organizacija: FMF - Fakulteta za matematiko in fiziko ; FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2026
• Št. strani: Str. 56:1-56:15
• PID: 20.500.12556/RUL-186597
• UDK: 004.42:519.17
• ISSN pri članku: 1868-8969
• DOI: 10.4230/LIPIcs.ESA.2026.56
• COBISS.SI-ID: 289440515
• Datum objave v RUL: 03.09.2026

Gradivo je del zbornika

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

Gradivo je del revije

• Naslov: Leibniz international proceedings in informatics
• Skrajšan naslov: Leibniz int. proc. inform.
• Založnik: Schloss Dagstuhl, Leibniz-Zentrum für Informatik
• ISSN: 1868-8969
• COBISS.SI-ID: 523260441

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.