2026-07-20T14:45:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16832 2024-03-06T10:58:26Z ddc:004 open_access

On Dynamic α + 1 Arboricity Decomposition and Out-Orientation Christiansen, Aleksander B. G. Holm, Jacob Rotenberg, Eva Thomassen, Carsten Dynamic graphs bounded arboricity data structures A graph has arboricity α if its edges can be partitioned into α forests. The dynamic arboricity decomposition problem is to update a partitioning of the graph’s edges into forests, as a graph undergoes insertions and deletions of edges. We present an algorithm for maintaining partitioning into α+1 forests, provided the arboricity of the dynamic graph never exceeds α. Our algorithm has an update time of Õ(n^{3/4}) when α is at most polylogarithmic in n. Similarly, the dynamic bounded out-orientation problem is to orient the edges of the graph such that the out-degree of each vertex is at all times bounded. For this problem, we give an algorithm that orients the edges such that the out-degree is at all times bounded by α+1, with an update time of Õ(n^{5/7}), when α is at most polylogarithmic in n. Here, the choice of α+1 should be viewed in the light of the well-known lower bound by Brodal and Fagerberg which establishes that, for general graphs, maintaining only α out-edges would require linear update time. However, the lower bound by Brodal and Fagerberg is non-planar. In this paper, we give a lower bound showing that even for planar graphs, linear update time is needed in order to maintain an explicit three-out-orientation. For planar graphs, we show that the dynamic four forest decomposition and four-out-orientations, can be updated in Õ(n^{1/2}) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aleksander B. G. Christiansen and Jacob Holm and Eva Rotenberg and Carsten Thomassen 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.34 urn:nbn:de:0030-drops-168320 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.34 eng https://creativecommons.org/licenses/by/4.0/legalcode