Pitfalls of using PQ-trees in Automatic Graph Drawing
Jünger, Michael and Leipert, Sebastian and Mutzel, Petra
Pitfalls of using PQ-trees in Automatic Graph Drawing.
Published In: Graph drawing : 5th international symposium, GD '97, Rome, Italy, September 18 - 20, 1997 ; proceedings, Lecture notes in computer science. 1353 Springer 1997, pp. 193-204.
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:||Proceedings article|
|Citations:||27 (Google Scholar) ||
|Uncontrolled Keywords:||level-planar dags maximal planar subgraphs planarization PQ-trees|
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger|
|Depositing User:||Prof. Dr. Michael Jünger|
|Date Deposited:||24 Jun 2003 00:00|
|Last Modified:||19 Jan 2012 09:44|