English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Report

Pitfalls of using PQ-Trees in automatic graph drawing

MPS-Authors
/persons/resource/persons44906

Leipert,  Sebastian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45092

Mutzel,  Petra
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

MPI-I-97-1-015.pdf
(Any fulltext), 229KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Jünger, M., Leipert, S., & Mutzel, P.(1997). Pitfalls of using PQ-Trees in automatic graph drawing (MPI-I-97-1-015). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-9E13-A
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.