2026-07-20T05:13:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4945 2024-03-06T10:35:36Z ddc:004 open_access

Optimal Decremental Connectivity in Planar Graphs Lacki, Jakub Sankowski, Piotr decremental connectivity planar graphs dynamic connectivity algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Lacki and Piotr Sankowski 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.608 urn:nbn:de:0030-drops-49457 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.608 eng https://creativecommons.org/licenses/by/3.0/legalcode