Abstrakt
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 give an FPT algorithm in time $\mathcal{O}(n^2 f(k))$ which solves a more general problem P-RestrictedContract in which S has to satisfy in addition a fixed inclusion-closed MSOL formula P. For different formulas P we get different problems.
As a specific example, we study the ℓ-subgraph contractability problem in which edges of a set S are required to form disjoint connected subgraphs of size at most ℓ. This problem can be solved in time $\mathcal{O}(n^2 f'(k,l))$ using the general algorithm.
We also show that for ℓ greater than 1 the problem is NP-complete. And it remains NP-complete when generalized for a fixed genus (instead of planar graphs).