20.500.12556/DiRROS-32247 Linear-time vertex-connectivity for graphs of bounded genus 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. vertex-connectivity graphs on surfaces genus of a graph true false true Angleški jezik Ni določen Neznano 2026-09-02 12:21:27 2026-09-02 12:21:28 2026-09-03 03:56:41 0000-00-00 00:00:00 2026 0 0 Str. 56:1-56:15 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.42:519.17 1868-8969 10.4230/LIPIcs.ESA.2026.56 289440515 289437955 LIPIcs.ESA.2026.56.pdf LIPIcs.ESA.2026.56.pdf 1 F45A440D43180C9C15355B23AE252A85 73d1a359d56faad36a1ad7df291b09812258d36cc3cdbe5f3bf6b50a98f1ff0f 4fd1bf46-a6b8-11f1-8a94-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=50341 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.56 1 11f08a74-a6b8-11f1-8a94-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=50340 Inštitut za matematiko, fiziko in mehaniko 0 0 0