DocumentCode
1418820
Title
A note on computing a maximal planar subgraph using PQ-trees
Author
Junger, Michael ; Leipert, Sebastian ; Mutzel, Petra
Author_Institution
Inst. fur Inf., Koln Univ., Germany
Volume
17
Issue
7
fYear
1998
fDate
7/1/1998 12:00:00 AM
Firstpage
609
Lastpage
612
Abstract
The problem of computing a maximal planar subgraph of a nonplanar 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. 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. Our conclusions most likely suggest not to use PQ-trees at all for this specific problem
Keywords
trees (mathematics); PQ-tree; maximal planar subgraph; nonplanar graph; planarization algorithm; Design methodology; Integrated circuit interconnections; Planarization; Printed circuits; Sections; Testing; Very large scale integration;
fLanguage
English
Journal_Title
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher
ieee
ISSN
0278-0070
Type
jour
DOI
10.1109/43.709399
Filename
709399
Link To Document