article published yes Monika H Henzinger author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530 We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m 2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log2 n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n 2/3 ) per update or query. Springer Nature1995 eng 0178-4617 1432-054110.1007/bf01189067 136503-538 yes Henzinger M. 1995. Fully dynamic biconnectivity in graphs. Algorithmica. 13(6), 503–538. Henzinger, M. (1995). Fully dynamic biconnectivity in graphs. <i>Algorithmica</i>. Springer Nature. <a href="https://doi.org/10.1007/bf01189067">https://doi.org/10.1007/bf01189067</a> Henzinger, Monika. “Fully Dynamic Biconnectivity in Graphs.” <i>Algorithmica</i>, vol. 13, no. 6, Springer Nature, 1995, pp. 503–38, doi:<a href="https://doi.org/10.1007/bf01189067">10.1007/bf01189067</a>. M. Henzinger, “Fully dynamic biconnectivity in graphs,” <i>Algorithmica</i>, vol. 13, no. 6. Springer Nature, pp. 503–538, 1995. Henzinger, Monika. “Fully Dynamic Biconnectivity in Graphs.” <i>Algorithmica</i>. Springer Nature, 1995. <a href="https://doi.org/10.1007/bf01189067">https://doi.org/10.1007/bf01189067</a>. Henzinger M. Fully dynamic biconnectivity in graphs. <i>Algorithmica</i>. 1995;13(6):503-538. doi:<a href="https://doi.org/10.1007/bf01189067">10.1007/bf01189067</a> M. Henzinger, Algorithmica 13 (1995) 503–538. 116772022-07-27T14:50:46Z2024-11-06T08:12:13Z