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: |
Download (417kB) | Preview |
---|---|
Download: |
Download (123kB) | Preview |
Editorial actions: | ![]() |
Content information:
Item Type: | Paper (Technical Report) |
---|---|
Citations: | No citation data. |
Uncontrolled Keywords: | maximum planar subgraph problem complexity result |
Subjects: |
|
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 |