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 , pp. 82-88(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item