Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Pitfalls of using PQ--Trees in automatic graph drawing

Jünger, Michael and Leipert, Sebastian and Mutzel, Petra

MPI-I-97-1-015. July 1997, 12 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-015.ps490 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {J{\"u}nger, Michael and Leipert, Sebastian and Mutzel, Petra},
  TITLE = {Pitfalls of using PQ--Trees in automatic graph drawing},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-015},
  MONTH = {July},
  YEAR = {1997},
  ISSN = {0946-011X},