A Note on Computing a Maximal Planar Subgraph using PQ-Trees

Jünger, Michael and Leipert, Sebastian and Mutzel, Petra (1998) A Note on Computing a Maximal Planar Subgraph using PQ-Trees.
Published in: IEEE transactions on computer-aided design of integrated circuits and systems Vol. 17 (7). pp. 609-612.


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. (1989). 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 (1992). Our conclusions most likely suggest not to use PQ-trees at all for this specific problem.

Download: [img] Postscript - Preprinted Version
Download (572kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 25 (Google Scholar) | 10 (Web of Science)
Uncontrolled Keywords: maximal planar subgraphs planarization PQ-trees
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Related URLs:
Deposit Information:
ZAIK Number: zpr98-320
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 28 Apr 2003 00:00
Last Modified: 16 Jan 2012 15:47
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/320