On computing vertex connectivity of 1-planar graphs

DOI10.1007/S00453-025-01355-3MaRDI QIDQ6894402zbMATH OpenFDO

Authors Therese Biedl, Karthik Murali

Publication date 25 November 2025

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-025-01355-3

zbMATH Keywords

treewidthvertex connectivitylinear-time algorithm1-planar graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Cites work

• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• 1-planarity of graphs with a rotation system
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Algorithms for graphs embeddable with few crossings per edge
• An annotated bibliography on 1-planarity
• Approximation algorithms for NP-complete problems on planar graphs
• Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
• Beyond planar graphs. Communications of National Institute of Informatics (NII) Shonan meetings, Shonan, Japan, November 27 -- December 1, 2016
• Breaking quadratic time for small vertex connectivity and an approximation scheme
• Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
• Connectivity of plane triangulations
• Depth-First Search and Linear Graph Algorithms
• Deterministic small vertex connectivity in almost linear time
• Dividing a Graph into Triconnected Components
• Efficient Planarity Testing
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graphs drawn with few crossings per edge
• Long cycles and spanning subgraphs of locally maximal 1-planar graphs
• Maximum flow and minimum-cost flow in almost-linear time
• Minimal obstructions for 1-immersions and hardness of 1-planarity testing
• On computing the vertex connectivity of 1-plane graphs
• Parameterized complexity of 1-planarity
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Using expander graphs to find vertex connectivity
• Vertex connectivity in poly-logarithmic max-flows

This page was built for publication: On computing vertex connectivity of 1-planar graphs

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