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)
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