2014/09/25 by Jakub Łącki, Łącki, Jakub, Piotr Sankowski +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1409.7240
openalex publication_date 2014/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show an algorithm for dynamic maintenance of connectivity information in an undirected planar graph subject to edge deletions. Our algorithm may answer connectivity queries of the form `Are vertices u and v connected with a path?' in constant time. The queries can be intermixed with any sequence of edge deletions, and the algorithm handles all updates in O(n) time. This results improves over previously known O(n log n) time algorithm.