Additional PC-Tree Planarity Conditions

Boyer, John M. (2004) Additional PC-Tree Planarity Conditions. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 82-88 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_10).

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
Additional Information:10.1007/978-3-540-31843-9_10
Classifications:G Algorithms and Complexity > G.770 Planarity Testing
ID Code:575

Repository Staff Only: item control page

References

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

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

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

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

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

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

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

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

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

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)

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

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