  In the F-minor-free deletion problem we want to find a minimum vertex set in
a given graph that intersects all minor models of graphs from the family F. The
Vertex planarization problem is a special case of F-minor-free deletion for the
family F = {K_5, K_{3,3}}. Whenever the family F contains at least one planar
graph, then F-minor-free deletion is known to admit a constant-factor
approximation algorithm and a polynomial kernelization [Fomin, Lokshtanov,
Misra, and Saurabh, FOCS'12]. The Vertex planarization problem is arguably the
simplest setting for which F does not contain a planar graph and the existence
of a constant-factor approximation or a polynomial kernelization remains a
major open problem.
  In this work we show that Vertex planarization admits an algorithm which is a
combination of both approaches. Namely, we present a polynomial A-approximate
kernelization, for some constant A > 1, based on the framework of lossy
kernelization [Lokshtanov, Panolan, Ramanujan, and Saurabh, STOC'17]. Simply
speaking, when given a graph G and integer k, we show how to compute a graph G'
on poly(k) vertices so that any B-approximate solution to G' can be lifted to
an (A*B)-approximate solution to G, as long as A*B*OPT(G) <= k. In order to
achieve this, we develop a framework for sparsification of planar graphs which
approximately preserves all separators and near-separators between subsets of
the given terminal set.
  Our result yields an improvement over the state-of-art approximation
algorithms for Vertex planarization. The problem admits a polynomial-time
O(n^eps)-approximation algorithm, for any eps > 0, and a quasi-polynomial-time
(log n)^O(1) approximation algorithm, both randomized [Kawarabayashi and
Sidiropoulos, FOCS'17]. By pipelining these algorithms with our approximate
kernelization, we improve the approximation factors to respectively O(OPT^eps)
and (log OPT)^O(1).
