| Title: | Linear-time vertex-connectivity for graphs of bounded genus |
|---|
| Authors: | ID Cabello, Sergio (Author)
ID Dobler, Alexander (Author)
ID Fijavž, Gašper (Author)
ID Hamm, Thekla (Author)
ID Wagner, Mirko H. (Author) |
|---|
| Files: |  PDF - Presentation file, download (996,31 KB)
MD5: F45A440D43180C9C15355B23AE252A85
 URL - Source URL, visit https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.56
|
|---|
| Language: | English |
|---|
| Typology: | 1.08 - Published Scientific Conference Contribution |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | vertex-connectivity, graphs on surfaces, genus of a graph |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | Str. 56:1-56:15 |
|---|
| PID: | 20.500.12556/DiRROS-32247  |
|---|
| UDC: | 004.42:519.17 |
|---|
| ISSN on article: | 1868-8969 |
|---|
| DOI: | 10.4230/LIPIcs.ESA.2026.56 |
|---|
| COBISS.SI-ID: | 289440515 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 02.09.2026 |
|---|
| Views: | 20 |
|---|
| Downloads: | 17 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
