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
Download (111kB)

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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/20

Available Versions of this Item

Actions (login required)

View Item View Item