Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable.

For a finite collection of graphs F, the F -TM-Deletion problem has as input an n-vertex graph G and an integer k and asks whether there exists a set S = V (G) with | S | = k such that G \ S does not contain any of the graphs in F as a topological minor. We prove that for every such F, F -TM-Deletion is fixed parameter tractable on planar graphs. Our algorithm runs in a 2 O(k 2) · n² time, or, alternatively, in 2 ^O(k) · n⁴ time. Our techniques can easily be extended to graphs that are embeddable on any fixed surface. [ABSTRACT FROM AUTHOR]