  We show that Odd Cycle Transversal and Vertex Multiway Cut admit
deterministic polynomial kernels when restricted to planar graphs and
parameterized by the solution size. This answers a question of Saurabh. On the
way to these results, we provide an efficient sparsification routine in the
flavor of the sparsification routine used for the Steiner Tree problem in
planar graphs (FOCS 2014). It differs from the previous work because it
preserves the existence of low-cost subgraphs that are not necessarily Steiner
trees in the original plane graph, but structures that turn into (supergraphs
of) Steiner trees after adding all edges between pairs of vertices that lie on
a common face. We also show connections between Vertex Multiway Cut and the
Vertex Planarization problem, where the existence of a polynomial kernel
remains an important open problem.
