2012 | OriginalPaper | Chapter
Obtaining Planarity by Contracting Few Edges
Authors : Petr A. Golovach, Pim van ’t Hof, Daniël Paulusma
Published in: Mathematical Foundations of Computer Science 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
.