Pitfalls of using PQ-Trees in Automatic Graph Drawing

Jünger, Michael and Leipert, Sebastian and Mutzel, Petra (1997) Pitfalls of using PQ-Trees in Automatic Graph Drawing. [Preprint]

WarningThere is a more recent version of this item available.

[img] Other
109Kb

Abstract

A number of erroneous attempts involving PQ-trees in the context of automatic graph drawing algorithms have been presented in the literature in recent years. In order to prevent future research from constructing algorithms with similar errors we point out some of the major mistakes. In particular, we examine erroneous usage of the PQ-tree data structure in algorithms for computing maximal planar subgraphs and an algorithm for testing leveled planarity of leveled directed acyclic graphs with several sources and sinks.

Item Type:Preprint
Classifications:M Methods > M.500 Layered
P Styles > P.480 Layered
G Algorithms and Complexity > G.770 Planarity Testing
P Styles > P.540 Planar
G Algorithms and Complexity > G.840 Planarization
M Methods > M.700 Planarization-based
ID Code:20
Alternative Locations:http://e-archive.informatik.uni-koeln.de/278/

Available Versions of this Item

Repository Staff Only: item control page

References

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

Chiba, N. and Nishizeki, T. and Abe, S. and Ozawa, T. (1985) A linear algorithm for embedding planar graphs using PQ-trees. Journal of Computer and System Sciences, 30 54-76.

Di Battista, G. and Nardelli, E. (1998) Hierarchies and planarity theory. IEEE Transactions on systems, man, and cybernetics, 18 (6) 1035-1046.

Even, S. (1979) Graph Algorihms. Computer Science Press, Potomac, Maryland.

Even, S. and Tarjan, R. E. (1976) Computing and st-numbering. Theoretical Computer Science, 2 339-344.

Heath, L. and Pemmaraju, S. (1996) Recognizing leveled-planar dags time. In: F. J. Brandenburg (ed.) Proc. Graph Drawing 95, volume 1027 of Lecture Notes in Computer Science, Springer Verlag, pp. 300-311.

Heath, L. and Pemmaraju, S. (1996) Stack and queue layouts of directed acyclic graphs: PartII. Technical report, Department of Computer Science, Virginia Polytechnic Institute & State University.

Jayakumar, R. and Thulasiraman, K. and Swamy, M. (1986) On maximal planarization of non-planar graphs. IEEE Transactions on Circuits Systems, 33 (8) 843-844.

Jayakumar, R. and Thulasiraman, K. and Swamy, M. (1989) On O(n²)algorithms for graph planarization. IEEE Transactions on Computer-Aided Design, 8 (3) 257-267.

Jünger, M. and Leipert, S. and Mutzel, P. (1996) On computing a maximal planar subgraph using PQ-trees. Technical Report 96.227, Institut für Informatik, Universität zu Köln.

Kant, G. (1992) An O(n²) maximal planarization algorithm based on PQ-trees. Technical Report RUU-CS-92-03, Department of Computer Science, Utrecht University.

Lempel, A. and Even, S. and Cederbaum, I. (1967) An algorithm for planarity testing of graphs. In Theory of Graphs: International Symposium: Rome, July 1966, pp. 215-232. Gordon and Breach, New York.

Ozawa, T. and Takahashi, H. (1981) A graph-planarization algorithm and its application to random graphs. In Graph Theory and Algorithms, volume 108 of Lecture Notes in Computer Science, pp. 95-107.