Portal de Periódicos da CAPES

On-line graph algorithms with SPQR-trees

1990; Springer Science+Business Media; Linguagem: Inglês

10.1007/bfb0032061

1611-3349

Giuseppe Di Battista, Roberto Tamassia,

Data Management and Algorithms

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.