Abstract
We study the computational complexity of graph planarization via edge contraction. The problem Contract asks whether there exists a set S of at most k edges that when contracted produces a planar graph. We work with a more general problem called P-RestrictedContract in which S, in addition, is required to satisfy a fixed MSOL formula P(S,G). We give an FPT algorithm in time O(n2f(k)) which solves P-RestrictedContract, where n is number of vertices of the graph and P(S,G) is (i) inclusion-closed and (ii) inert contraction-closed (where inert edges are the edges non-incident to any inclusion-minimal solution S).
As a specific example, we can solve the ℓ-subgraph contractibility problem in which the edges of the set S are required to form disjoint connected subgraphs of size at most ℓ. This problem can be solved in time O(n2f′(k,ℓ)) using the general algorithm. We also show that for ℓ≥2 the problem is NP-complete.