On-line graph algorithms with SPQR-trees
Lecture notes in computer sciencePublished 1 January 1990
Giuseppe Di Battista, Roberto Tamassia
Citations96
SJR quartileQ2
SJR score0.35
SNIP0.55
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 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.
Abstract
We present the SPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and show its application to a variety of on-line graph algorithms dealing with triconnectivity, transitive closure, minimum spanning tree, and planarity testing. The results are further extended to general graphs by means of another data structure, the BC-tree.
Keywords
Computer Science
Journal of Computer and System SciencesA data structure for dynamic trees
1,040 Citations1983Daniel D. Sleator, Robert E. Tarjan
SIAM Journal on ComputingDividing a Graph into Triconnected Components
833 Citations1973John E. Hopcroft, Robert E. Tarjan
An algorithm for dividing a graph into triconnected components is presented and is both theoretically optimal to within a constant factor and efficient in practice.
Journal of Computer and System SciencesA linear-time algorithm for a special case of disjoint set union
557 Citations1985Harold N. Gabow, Robert E. Tarjan
Journal of the ACMWorst-case Analysis of Set Union Algorithms
449 Citations1984Robert E. Tarjan, Jan Van Leeuwen
It is shown that two one-pass methods proposed by van Leeuwen and van der Weide are asymptotically optimal, whereas several other methods, including one proposed by Rein and advocated by Dijkstra, are slower than the best methods.
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.
Theoretical Computer ScienceAlgorithms for plane representations of acyclic digraphs
254 Citations1988Giuseppe Di Battista, Roberto Tamassia
This work investigates the problem of representing acyclic digraphs in the plane in such a way that all edges flow in the same direction, e.g., from the left to the right or from the bottom to the top.
Theoretical Computer ScienceComputing an st-numbering
252 Citations1976Shimon Even, Robert E. Tarjan
This paper provides a linear-time algorithm for computing an st-numbering for any biconnected graph and can be combined with some new results by Booth and Lueker to provide alinear-time implementation of the Lempel-Even-Cederbaum planarity-testing algorithm.
Journal of AlgorithmsIncremental algorithms for minimal length paths
154 Citations1991Giorgio Ausiello, Giuseppe F. Italiano +2 more
A new data structure is introduced which is able to answer queries concerning the length of the shortest path between any two vertices in constant time and to trace out the shortest path between any two vertices in time linear in the number of edges reported.
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.
Incremental planarity testing
134 Citations1989Giuseppe Di Battista, Roberto Tamassia
An efficient technique for incremental planarity testing that uses O(n) space and supports tests and insertion of vertices and edges in O(log n) time is presented.
Theoretical Computer ScienceAmortized efficiency of a path retrieval data structure
112 Citations1986Giuseppe F. Italiano
A data structure is presented for the problem of maintaining a digraph under an arbitrary sequence of two kinds of operations: an Add operation that inserts an arc in the digraph, and a Searchpath operation that checks the presence of a path between a pair of nodes.
SIAM Journal on ComputingOn the Complexity of Covering Vertices by Faces in a Planar Graph
83 Citations1988Daniel Bienstock, Clyde Monma
An algorithm is presented which given a graph G and a value k either determines that G is not k-planar or generates an appropriate embedding and associated minimum cover in O(c^k n) time, where c is a constant.
SIAM Journal on ComputingFully Dynamic Point Location in a Monotone Subdivision
62 Citations1989Franco P. Preparata, Roberto Tamassia
A dynamic technique for locating a point in a monotone planar subdivision, whose current number of vertices is n, is presented.
Symposium on Discrete AlgorithmsMaintenance of a minimum spanning forest in a dynamic planar graph
62 Citations1990David Eppstein, Giuseppe F. Italiano +4 more
Journal of AlgorithmsDynamic orthogonal segment intersection search
44 Citations1987Hiroshi Imai, Takao Asano
The data structures developed here give new better solutions for various geometric problems on orthogonal segments by utilizing set-union and set-splitting algorithms.
Lecture notes in computer scienceFinding triconnected components by local replacements
42 Citations1989Donald S. Fussell, Vijaya Ramachandran +1 more
This work presents an almost-optimal parallel algorithm for finding triconnected components on a CRCW PRAM, based on ear decomposition but it employs a new technique, local replacement, to improve the complexity.
Fully dynamic techniques for point location and transitive closure in planar structures
40 Citations1988F. P. Preparata, Roberto Tamassia
Planar st-graphs provide the topological underpinning of a fully dynamic planar point location technique in monotone subdivisions, which is an interesting (unique) specialization of the chain method of Lee-Preparata (1977).
Lecture notes in computer scienceA dynamic data structure for planar graph embedding
37 Citations1988Roberto Tamassia
A dynamic data structure that allows for incrementally constructing a planar embedding of aPlanar graph with n vertices and m edges that finds applications in circuit layout, graphics, motion planning, and computer-aided design.
Area requirement and symmetry display in drawing graphs
30 Citations1989Giuseppe Di Battista, Roberto Tamassia +1 more
This work has shown that every n-vertex planar graph admits a planar straight-line drawing with vertices placed at grid points and 0 (n2) area.
Symposium on Discrete AlgorithmsA data structure for arc insertion and regular path finding
18 Citations1990Adam L. Buchsbaum, Paris C. Kanellakis +1 more
Algorithms and data structures for dynamic graph problems
13 Citations1989Jeffery Westbrook
It is proved that any separable pointer-based algorithm for the set union with backtracking problem requires $\Omega(\log n/\log \log n)$ time per operation, thus showing that the upper bound an amortized time is tight.
IDEALS (University of Illinois Urbana-Champaign)A Characterization of Separating Pairs and Triplets in a Graph
8 Citations2019Arkady Kanevsky, Vijaya Ramachandran
Lecture notes in computer scienceDynamic data structures for series parallel digraphs
8 Citations1989Giuseppe F. Italiano, Alberto Marchetti-Spaccamela +1 more
The authors' data structures are able to report a regular expression describing all the paths between two vertices x and y in O(h+log n), where h≤n is the total number of vertices which are contained in paths from x to y.