Gassner, Elisabeth and Percan, Merijam
(2006).
Maximum Planar Subgraph on Graphs not Contractive to K5 or K3,3.
Working Paper.
Preview |
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: | Monograph (Working Paper) |
| Creators: | Creators Email ORCID ORCID Put Code Gassner, Elisabeth UNSPECIFIED UNSPECIFIED UNSPECIFIED Percan, Merijam UNSPECIFIED UNSPECIFIED UNSPECIFIED |
| 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 |