  In this paper, we devise a scheme for kernelizing, in sublinear space and
polynomial time, various problems on planar graphs. The scheme exploits
planarity to ensure that the resulting algorithms run in polynomial time and
use O((sqrt(n) + k) log n) bits of space, where n is the number of vertices in
the input instance and k is the intended solution size. As examples, we apply
the scheme to Dominating Set and Vertex Cover. For Dominating Set, we also show
that a well-known kernelization algorithm due to Alber et al. (JACM 2004) can
be carried out in polynomial time and space O(k log n). Along the way, we
devise restricted-memory procedures for computing region decompositions and
approximating the aforementioned problems, which might be of independent
interest.

Data Structures and Algorithms