Gassner, Elisabeth and Percan, Merijam
(2006).
Maximum Planar Subgraph on Graphs not Contractive to K5 or K3,3.
Working Paper.
|
PDF
zaik2006-525.pdf Download (123kB) | Preview |
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.
| Item Type: | Preprints, Working Papers or Reports (Working Paper) | ||||||||||||
| Creators: |
|
||||||||||||
| URN: | urn:nbn:de:hbz:38-549012 | ||||||||||||
| Date: | 2006 | ||||||||||||
| 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/54901 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |