Logo

Login | Create Account

Additional PC-Tree Planarity Conditions

Boyer, John M. (2004) Additional PC-Tree Planarity Conditions. [Conference Paper]

Full text not available from this repository.

Abstract

Recent research efforts have produced new algorithms for solving planarity-related problems. One such method performs vertex addition using the PC-tree data structure, which is similar to but simpler than the well-known PQ-tree. For each vertex, the PC-tree is first checked to see if the new vertex can be added without violating certain planarity conditions; if the conditions hold, the PC-tree is adjusted to add the new vertex and processing continues. The full set of planarity conditions are required for a PC-tree planarity tester to report only planar graphs as planar. This paper provides further analyses and new planarity conditions needed to produce a correct planarity algorithm with a PC-tree.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.770 Planarity Testing
ID Code:575
Deposited By:Selbach, Anna
Deposited On:19 Jul 2005
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=3383&spage=82

Repository Staff Only: item control page

References

1. Hopcroft, J., Tarjan, R.: Efficient planarity testing. Journal of the Association for Computing Machinery 21 (1974) 547-568

2. Booth, K.S., Lueker, G.S.: Testing for the consecutive ones prpperty, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences 13 (1976) 335-379

3. Boyer, J., Myrvold, W.: Stop minding your P's and Q's: A simplified O(n) planar embedding algorithm. Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (1999) 140-146

4. Boyer, J., Myrvold, W.: On the cutting edge: Simplified O(n) planarity by edge addition. Accepted to Journal of Graph Algorithms and Applications, August 2004 (Preprint at http:/www. pacificcoast.net/~lightning/planarity.ps) 1-29

5. Shih, W.K., Hsu, W.L.: A new planarity test. Theoretical Computer Science 223 (1999) 179-191

6. Hsu, W.L.: A simple test for the consecutive ones property. Journal of Algorithms 42 (2002) 1-16

7. Hsu, W.L., McConnell, R.: PC-trees and circular-ones arrangements. Theoretical Computer Science 296 (2003) 59-74

8. Hsu, W.L.: PC-trees vs. PQ-trees. Lecture Notes in Computer Science 2108 (2001) 207-217

9. Hsu, W.L., McConnell, R.: PC-trees. submitted to Handbook of Data Structures and Applications, Dinesh P Mehta and Sartaj Sahni ed. (2004)

10. Hsu, W.L.: An efficient implementation of the PC-trees algorithm of shih and hsu's planarity test. Technical Report TR-IIS-03-015, Institute of Information Science, Academia Sinica (2003)

11. Boyer, J.M., Cortese, P.F., Patrignani, M., Di Battista, G.: Stop minding your P's and Q's: Implementing a fast and simple DFS-based planarity testing and embedding algorithm. In Liotta, G., ed.: Proceedings of the 11th International Symposium on Graph Drawing 2003. Volume 2912 of Lecture Notes in Computer Science., Springer-Verlag (2004) 25-36

12. de Fraysseix, H., Rosenstiehl, P.: A characterization of planar graphs by trémaux orders. Combinatorica 5 (1985) 127-135

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.