Maximum Planar Subgraph on Graphs not Contractive to K5 or K3,3

Gassner, Elisabeth and Percan, Merijam (2006) Maximum Planar Subgraph on Graphs not Contractive to K5 or K3,3.
Technical Report , 6 p.

Abstract

The maximum planar subgraph problem is well studied. Recently, it has been shown that the maximum planar subgraph problem is NP-complete for cubic graphs. In this paper we prove shortly that the maximum planar subgraph problem remains NP-complete even for graphs without a minor isomorphic to K5 or K3,3 , respectively.


Actions:
Download: [img] Postscript
Download (417kB) | Preview
Download: [img] PDF
Download (123kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: No citation data.
Uncontrolled Keywords: maximum planar subgraph problem complexity result
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C10 Planar graphs; geometric and topological aspects of graph theory

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C62 Graph representations (geometric and intersection representations, etc.)

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Related URLs:
    Deposit Information:
    ZAIK Number: zaik2006-525
    Depositing User: Merijam Percan
    Date Deposited: 10 Aug 2006 00:00
    Last Modified: 19 Dec 2011 09:44
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/525