Decremental 2- and 3-connectivity on planar graphs
AlgorithmicaPublished 1 September 1996
Dora Giammarresi, Giuseppe F. Italiano
Citations16
SJR quartileQ1
SJR score0.97
SNIP1.11
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The problem of maintaining the 2-edge, 2-vertex, and 3-edge-connected components of a dynamic planar graph subject to edge deletions is studied and time bounds improve previous bounds.
Abstract
We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log2 n) time. This givesO(log2 n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
ACM Transactions on GraphicsPrimitives for the manipulation of general subdivisions and the computation of Voronoi
1,264 Citations1985Leonidas Guibas, Jorge Stolfi
The following problem is discussed: given n points in the plane (the sites) and an arbitrary query point q, find the site that is closest to q, which can be solved by constructing the Voronoi diagram of the griven sites and then locating the query point in one of its regions.
SIAM Journal on ComputingData Structures for On-Line Updating of Minimum Spanning Trees, with Applications
380 Citations1985Greg N. Frederickson
Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph.
Journal of the ACMAn On-Line Edge-Deletion Problem
283 Citations1981Yossi Shiloach, Shimon Even
An algorithm is presented which maintains a data structure in which each question is answered in constant time and for which the total time involved in answering q questions and maintaining the data structure is O(q + I VI) lED.
Data structures for on-line updating of minimum spanning trees
141 Citations1983Greg N. Frederickson
Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph.
AlgorithmicaMaintaining bridge-connected and biconnected components on-line
135 Citations1992Jeffery Westbrook, Robert E. Tarjan
A modified version of the dynamic trees of Sleator and Tarjan is developed that is suitable for efficient recursive algorithms, and used to reduce the running time of the algorithms for both problems toO(mα(m,n), where α is a functional inverse of Ackermann's function.
Journal of AlgorithmsMaintenance of a minimum spanning forest in a dynamic plane graph
129 Citations1992David Eppstein, Giuseppe F. Italiano +4 more
The algorithms can be used to maintain the connected components of a dynamic planar graph in O(log n) time per operation.
Sparsification-a technique for speeding up dynamic graph algorithms
115 Citations1992David Eppstein
Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees
100 Citations2002Greg N. Frederickson
Ambivalent data structures are presented for several problems on undirected graphs and used in finding the k smallest spanning trees of a weighted undirecting graph in O(m log beta (m,n)+min(k/sup 3/2/, km/sup 1/2/)) time, where m and n are understood to be the current number of edges and vertices, respectively.
Lecture notes in computer scienceOn-line graph algorithms with SPQR-trees
96 Citations1990Giuseppe Di Battista, Roberto Tamassia
The SPQR-tree is presented, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconsnected components, and its application to a variety of on-line graph algorithms dealing with triconnectivity, transitive closure, minimum spanning tree, and planarity testing is shown.
On-line maintenance of the four-connected components of a graph
52 Citations2002Arkady Kanevsky, Roberto Tamassia +2 more
The authors present a static data structure that answers k-connectivity queries for k<or=4 that supports queries and updates in time O( alpha (l,n)) amortized, and an efficient algorithm for testing whether graph G is four-connected that runs in O(n alpha (n, n)+m) time using O( n+m) space.
SIAM Journal on ComputingMaintaining the 3-Edge-Connected Components of a Graph On-Line
47 Citations1993Zvi Galil, Giuseppe F. Italiano
This paper shows how to answer the question of whether or not two vertices belong to the same 3-edge-connected component of a connected graph that is undergoing only edge insertions.
Fully dynamic biconnectivity in graphs
39 Citations1992Monika Rauch
The author presents an algorithm for maintaining the bi-connected components of a graph during a sequence of edge insertions and deletions, which is the first sublinear algorithm for this problem.
Improved data structures for fully dynamic biconnectivity
39 Citations1994Monika Rauch
The algorithm for general graphs can also find the biconnected components of all vertices in time $O(n)$ and the update times in general graphs are amortized, showing that the biconsnected component of a graph can be dynamically maintained almost as efficiently as the connected components.
Lecture notes in computer scienceMaintaining biconnected components of dynamic planar graphs
36 Citations1991Zvi Galil, Giuseppe F. Italiano
This work shows how to test at any time whether two vertices belong to the same biconnected component, and how to insert and delete an edge in O(n2/3) time in the worst case, where n is the number of vertices in the graph.
SIAM Journal on ComputingFully Dynamic Algorithms for 2-Edge Connectivity
28 Citations1992Zvi Galil, Giuseppe F. Italiano
It is shown how to test at any time whether two vertices belong to the same 2-edge-connected component, and how to insert and delete an edge in O(m^{2/3} ) time in the worst case, where m is the current number of edges in the graph.
Lecture notes in computer scienceMaintenance of triconnected components of graphs
26 Citations1992J. A. La Poutré
In this paper, optimal algorithms and data structures are presented to maintain the triconnected components of a general graph, under insertions of edges in the graph.
Discrete MathematicsMaintenance of 2- and 3-edge- connected components of graphs I
19 Citations1993J. A. La Poutré, Jan Van Leeuwen +1 more
A data structure is presented to efficiently maintain the 2- and 3-edge-connected components of a graph, under insertions of edges in the graph, in O(1) time.
Lecture notes in computer scienceFully dynamic 2-edge-connectivity in planar graphs
13 Citations1992John Hershberger, Monika Rauch +1 more
A data structure for maintaining 2-edge connectivity information dynamically in a planar graph that requires linear storage and preprocessing time for its construction, supports online updates, and answers a query in O(log n) time.
Lecture notes in computer scienceDynamic 2- and 3-connectivity on planar graphs
3 Citations1992Dora Giammarresi, Giuseppe F. Italiano
This work studies the problem of maintaining the 2-edge, 2-vertex, and 3-edge-connected components of a dynamic planar graph subject to edge deletions and finds that they can be maintained in a total of O(log n) time.