Golovach, P.A. and van 't Hog, P. and Paulusma, Daniel (2012) 'Obtaining planarity by contracting few edges.', in Mathematical foundations of computer science 2012 : 37th international symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings. Berlin ; Heidelberg: Springer, pp. 455-466. Lecture notes in computer science. (7464).
Abstract
The Planar Contraction problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when parameterized by k.
| Item Type: | Book chapter |
|---|---|
| Keywords: | Planar graphs, Edge contractions, FPT algorithms. |
| Full text: | Full text not available from this repository. |
| Publisher Web site: | http://dx.doi.org/10.1007/978-3-642-32589-2_41 |
| Date accepted: | No date available |
| Date deposited: | No date available |
| Date of first online publication: | 2012 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
