On Computing a Maximal Planar Subgraph using PQ-Trees

Jünger, Michael and Leipert, Sebastian and Mutzel, Petra (1996) On Computing a Maximal Planar Subgraph using PQ-Trees.
Technical Report , 12 p.

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.


Actions:
Download: [img] Postscript
Download (592kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: No citation data.
Uncontrolled Keywords: maximal planar subgraphs planarization PQ-trees
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C35 Programming involving graphs or networks

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Related URLs:
    Deposit Information:
    ZAIK Number: zpr96-227
    Depositing User: Prof. Dr. Michael Jünger
    Date Deposited: 02 Apr 2001 00:00
    Last Modified: 19 Jan 2012 10:26
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/227