SPQR-tree

From Wikipedia, the free encyclopedia

The SPQR-tree is a tree data structure that represents the decomposition of a biconnected graph with respect to its triconnected components. It was introduced by Di Battista and Tamassia [1] [2]. Its main application is planarity testing and graph drawing.

 Please help improve this section by expanding it.
Further information might be found on the talk page or at requests for expansion.


[edit] References

  1. ^ Di Battista, G. and Tamassia, R. (1989). "Incremental planarity testing". Foundations of Computer Science, 1989., 30th Annual Symposium on: 436–441. 
  2. ^ Di Battista, G. and Tamassia, R. (1996). "On-Line Maintenance of Triconnected Components with SPQR-Trees". Algorithmica 15 (4): 302–318. 

[edit] Links