de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

A note on computing a maximal planar subgraph using PQ-trees

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44906

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45092

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

Locator
There are no locators available
Fulltext (public)

1998-1-008
(Any fulltext), 10KB

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

Jünger, M., Leipert, S., & Mutzel, P.(1998). A note on computing a maximal planar subgraph using PQ-trees (MPI-I-1998-1-008). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-7BDC-4
Abstract
The problem of computing a maximal planar subgraph of a non planar graph has been deeply investigated over the last 20 years. Several attempts have been tried to solve the problem with the help of PQ-trees. The latest attempt has been reported by Jayakumar et al. [10]. In this paper we show that the algorithm presented by Jayakumar et al. is not correct. We show that it does not necessarily compute a maximal planar subgraph and we note that the same holds for a modified version of the algorithm presented by Kant [12]. Our conclusions most likely suggest not to use PQ-trees at all for this specific problem.