Universität zu Köln

Jünger, Michael, Leipert, Sebastian and Mutzel, Petra ORCID: 0000-0001-7621-971X (1997). Pitfalls of using PQ-trees in Automatic Graph Drawing. In: Graph drawing : 5th international symposium, GD '97, Rome, Italy, September 18 - 20, 1997 ; proceedings, pp. 193-204. Springer.

Preview

PDF zpr97-278.pdf - Submitted Version Download (535kB) | Preview

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:	Book Section, Proceedings Item or annotation in a legal commentary
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Leipert, Sebastian UNSPECIFIED UNSPECIFIED UNSPECIFIED Mutzel, Petra UNSPECIFIED orcid.org/0000-0001-7621-971X UNSPECIFIED
URN:	urn:nbn:de:hbz:38-547906
Title of Book:	Graph drawing : 5th international symposium, GD '97, Rome, Italy, September 18 - 20, 1997 ; proceedings
Series Name:	Lecture notes in computer science
Volume:	1353
Page Range:	pp. 193-204
Date:	1997
Publisher:	Springer
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/54790