  Let $G=(V,E)$ be a bipartite graph embedded in a plane (or $n$-holed torus).
Two subgraphs of $G$ differ by a {\it $Z$-transformation} if their symmetric
difference consists of the boundary edges of a single face---and if each
subgraph contains an alternating set of the edges of that face. For a given
$\phi: V \mapsto \mathbb Z^+$, $S_{\phi}$ is the set of subgraphs of $G$ in
which each $v\in V$ has degree $\phi(v)$. Two elements of $S_{\phi}$ are said
to be adjacent if they differ by a $Z$-transformation. We determine the
connected components of $S_{\phi}$ and assign a {\it height function} to each
of its elements.
  If $\phi$ is identically two, and $G$ is a grid graph, $S_{\phi}$ contains
the partitions of the vertices of $G$ into cycles. We prove that we can always
apply a series of $Z$-transformations to decrease the total number of cycles
provided there is enough ``slack'' in the corresponding height function. This
allows us to determine in polynomial time the minimal number of cycles into
which $G$ can be partitioned provided $G$ has a limited number of non-square
faces. In particular, we determine the Hamiltonicity of polyomino graphs in
$O(|V|^2)$ steps. The algorithm extends to $n$-holed-torus-embedded graphs that
have grid-like properties. We also provide Markov chains for sampling and
approximately counting the Hamiltonian cycles of $G$.
