  We study the problems of finding a minimum cycle basis (a minimum weight set
of cycles that form a basis for the cycle space) and a minimum homology basis
(a minimum weight set of cycles that generates the $1$-dimensional
($\mathbb{Z}_2$)-homology classes) of an undirected graph embedded on a
surface. The problems are closely related, because the minimum cycle basis of a
graph contains its minimum homology basis, and the minimum homology basis of
the $1$-skeleton of any graph is exactly its minimum cycle basis.
  For the minimum cycle basis problem, we give a deterministic
$O(n^\omega+2^{2g}n^2+m)$-time algorithm for graphs embedded on an orientable
surface of genus $g$. The best known existing algorithms for surface embedded
graphs are those for general graphs: an $O(m^\omega)$ time Monte Carlo
algorithm and a deterministic $O(nm^2/\log n + n^2 m)$ time algorithm. For the
minimum homology basis problem, we give a deterministic $O((g+b)^3 n \log n +
m)$-time algorithm for graphs embedded on an orientable or non-orientable
surface of genus $g$ with $b$ boundary components, assuming shortest paths are
unique, improving on existing algorithms for many values of $g$ and $n$. The
assumption of unique shortest paths can be avoided with high probability using
randomization or deterministically by increasing the running time of the
homology basis algorithm by a factor of $O(\log n)$.
