Obtaining Planarity by Contracting Few Edges

The contraction of an edge uv in a graph G is the operation that deletes u and v from G, and replaces them by a new vertex that is made adjacent to precisely those vertices that were adjacent to either u or v in G. The Planar Contraction problem takes as input a graph G
and an integer k, and asks whether G 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. More precisely, we show that for every fixed \epsilon>0 and every
fixed integer k, it can be decided in O(n^{2+\epsilon}) time whether a graph can be made planar by contracting at most k edges.

Slides from the talk are available here: DOWNLOAD SLIDES!