Linear-time vertex-connectivity for graphs of bounded genusCabello, Sergio (Avtor) Dobler, Alexander (Avtor) Fijavž, Gašper (Avtor) Hamm, Thekla (Avtor) Wagner, Mirko H. (Avtor) vertex-connectivitygraphs on surfacesgenus of a graphWe 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.20262026-09-02 12:21:27Neznano32247sl