Logo

Login | Create Account

A Linear Time Implementation of SPQR-Trees

Gutwenger, Carsten and Mutzel, Petra (2001) A Linear Time Implementation of SPQR-Trees. [Conference Paper]

Full text not available from this repository.

Abstract

The data structure SPQR-tree represents the decomposition of a biconnected graph with respect to its triconnected components. SPQR-trees have been introduced by Di Battista and Tamassia [8] and, since then, became quite important in the field of graph algorithms. Theoretical papers using SPQR-trees claim that they can be implemented in linear time using a modification of the algorithm by Hopcroft and Tarjan [15] for decomposing a graph into its triconnected components. So far no correct linear time implementation of either triconnectivity decomposition or SPQR-trees is known to us. Here, we show the incorrectness of the Hopcroft and Tarjan algorithm [15], and correct the faulty parts. We describe the relationship between SPQR-trees and triconnected components and apply the resulting algorithm to the computation of SPQR-trees. Our implementation is publically available in AGD [1].

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:306
Deposited By:Selbach, Anna
Deposited On:24 Nov 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1984&spage=77

Repository Staff Only: item control page

References

AGD User Manual (Version 1.1.2), Feb. 2000. Max-Planck-Institut Saarbrücken, Technische Universität Wien, Universität zu Köln, Universität Trier. See also http://www.mpi-sb.mpg.de/AGD/.

G. Di Battista and R. Tamassia. On-line graph algorithms with SPQR-trees. In M.S. Paterson, editor, Proc. of the 17th International Colloqium on Automata, Languages and Prog. ramming (ICALP), volume 443 of Lecture Notes in Computer Science, pages 598-611. Springer-Verlag, 1990.

P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. In Proc. 5th Workshop Algorithms, Data Struct., volume 1272 of Lecture Notes in Computer Science, pages 331-344, 1998.

P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Optimal upward planarity testing of single-source digraphs. SIAM J. Comput., 27(1):132-169, 1998.

D. Biemstock and C. L. Monma. On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica, 5(1):93-109, 1990.

Elias Dahlhaus. A linear time algorithm to recognize clustered planar graphs and its parallelization. In C. L. Lucchesi and A. V. Moura, editors, LATIN '98: Theoretical Informatics, Third Latin American Symposium, volume 1380 of Lecture Notes in Computer Science, pages 239-248. Springer-Verlag, 1998.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, and F. Vargiu. An experimental comparision of four graph drawing algorithms. Comput. Geom. Theory Appl., 7:303-326, 1997.

G. Di Battista and R. Tamassia. Incremental planarity testing. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 436-441, 1989.

G. Di Battista and R. Tamassia. On-line maintanance of triconnected components with SPQR-trees. Algorithmica, 15:302-318, 1996.

G. Di Battista and R. Tamassia. On-line planarity testing. SIAM J. Comput., 25(5):956-997, 1996.

W. Didimo. Dipartimento di Informatica e Automazione, Università di Roma Tre, Rome, Italy, Personal Communication.

GD Toolkit Online Documentation. See http://www.dia.uniroma3.it/~gdt.

C. Gutwenger and P. Mutzel. A linear time implementation of SPQR-trees. Technical report, Technische Universität Wien, 2000. To appear.

C. Gutwenger, P. Mutzel, and R. Weiskircher. Inserting an edge into a planar graph. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01). ACM Press, 2001. To appear.

J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2(3):135-158, 1973.

J. E. Hopcroft and R. E. Tarjan. Efficient planarity testing. Journal of the ACM, 21:549-568, 1974.

G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, Special Issue on Graph Drawing, 16(1):4-32, 1996.

T. Lengauer. Hierarchical planarity testing. Journal of the ACM, 36:474-509, 1989.

S. MacLaine. A structural characterization of planar combinatorial graphs. Duke Math. J., 3:460-472, 1937.

K. Mehlhorn and S. Näher. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999. to appear.

P. Mutzel and R.Weiskircher. Optimizing over all combinatorial embeddings of a planar graph. In G. Cornuéjols, R. Burkard, and G. Woeginger, editors, Proceedings of the Seventh Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 1610 of LNCS, pages 361-376. Springer-Verlag, 1999.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.