A parameterized algorithm for vertex and edge connectivity of embedded graphs

DOI10.4230/LIPICS.ESA.2024.24MaRDI QIDQ7253079zbMATH OpenFDO

Authors Therese Biedl, Prosenjit Bose, Karthik Murali

Publication date 26 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2024.24

zbMATH Keywords

\(k\)-planar1-planaredge connectivitylinear-timevertex connectivity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Beyond planar graphs. Communications of National Institute of Informatics (NII) Shonan meetings, Shonan, Japan, November 27 -- December 1, 2016
• Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
• Deterministic mincut in almost-linear time
• Deterministic small vertex connectivity in almost linear time
• Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
• Graphs drawn with few crossings per edge
• Local flow partitioning for faster edge connectivity
• Map graphs
• Maximum flow and minimum-cost flow in almost-linear time
• On computing the vertex connectivity of 1-plane graphs
• On Optimal 2- and 3-Planar Graphs
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The graph crossing number and its variants: a survey
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Vertex connectivity in poly-logarithmic max-flows
• Zur Struktur 1‐planarer Graphen

Cited in

(1)

• Cops and robbers for graphs on surfaces with crossings

This page was built for publication: A parameterized algorithm for vertex and edge connectivity of embedded graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7253079)