  Graph Sparsification aims at compressing large graphs into smaller ones while
preserving important characteristics of the input graph. In this work we study
Vertex Sparsifiers, i.e., sparsifiers whose goal is to reduce the number of
vertices. We focus on the following notions:
  (1) Given a digraph $G=(V,E)$ and terminal vertices $K \subset V$ with $|K| =
k$, a (vertex) reachability sparsifier of $G$ is a digraph $H=(V_H,E_H)$, $K
\subset V_H$ that preserves all reachability information among terminal pairs.
In this work we introduce the notion of reachability-preserving minors (RPMs) ,
i.e., we require $H$ to be a minor of $G$. We show any directed graph $G$
admits a RPM $H$ of size $O(k^3)$, and if $G$ is planar, then the size of $H$
improves to $O(k^{2} \log k)$. We complement our upper-bound by showing that
there exists an infinite family of grids such that any RPM must have
$\Omega(k^{2})$ vertices.
  (2) Given a weighted undirected graph $G=(V,E)$ and terminal vertices $K$
with $|K|=k$, an exact (vertex) cut sparsifier of $G$ is a graph $H$ with $K
\subset V_H$ that preserves the value of minimum-cuts separating any
bipartition of $K$. We show that planar graphs with all the $k$ terminals lying
on the same face admit exact cut sparsifiers of size $O(k^{2})$ that are also
planar. Our result extends to flow and distance sparsifiers. It improves the
previous best-known bound of $O(k^22^{2k})$ for cut and flow sparsifiers by an
exponential factor, and matches an $\Omega(k^2)$ lower-bound for this class of
graphs.
