2026-08-01T05:10:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20238 2024-07-02T07:52:53Z ddc:004 open_access

Fully Dynamic Strongly Connected Components in Planar Digraphs Karczmarz, Adam Smulewicz, Marcin dynamic strongly connected components dynamic strong connectivity dynamic reachability planar graphs In this paper we consider maintaining strongly connected components (SCCs) of a directed planar graph subject to edge insertions and deletions. We show a data structure maintaining an implicit representation of the SCCs within Õ(n^{6/7}) worst-case time per update. The data structure supports, in O(log²{n}) time, reporting vertices of any specified SCC (with constant overhead per reported vertex) and aggregating vertex information (e.g., computing the maximum label) over all the vertices of that SCC. Furthermore, it can maintain global information about the structure of SCCs, such as the number of SCCs, or the size of the largest SCC. To the best of our knowledge, no fully dynamic SCCs data structures with sublinear update time have been previously known for any major subclass of digraphs. Our result should be contrasted with the n^{1-o(1)} amortized update time lower bound conditional on SETH, which holds even for dynamically maintaining whether a general digraph has more than two SCCs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Karczmarz and Marcin Smulewicz 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.95 urn:nbn:de:0030-drops-202388 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.95 eng https://creativecommons.org/licenses/by/4.0/legalcode