Jünger, Michael, Leipert, Sebastian and Mutzel, Petra ORCID: 0000-0001-7621-971X (1996). On Computing a Maximal Planar Subgraph using PQ-Trees. ["eprint_fieldopt_monograph_type_preprint" not defined].

[img]
Preview
PDF
zpr96-227.pdf

Download (256kB) | Preview

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, Thulasiraman and Swamy (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 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.

Item Type: Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:
CreatorsEmailORCIDORCID Put Code
Jünger, MichaelUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Leipert, SebastianUNSPECIFIEDUNSPECIFIEDUNSPECIFIED
Mutzel, PetraUNSPECIFIEDorcid.org/0000-0001-7621-971XUNSPECIFIED
URN: urn:nbn:de:hbz:38-547502
Date: 1996
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54750

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item