  Consider a weighted, undirected graph cellularly embedded on a topological
surface. The function assigning to each free homotopy class of closed curves
the length of a shortest cycle within this homotopy class is called the marked
length spectrum. The (unmarked) length spectrum is obtained by just listing the
length values of the marked length spectrum in increasing order.
  In this paper, we describe algorithms for computing the (un)marked length
spectra of graphs embedded on the torus. More specifically, we preprocess a
weighted graph of complexity $n$ in time $O(n^2 \log \log n)$ so that, given a
cycle with $\ell$ edges representing a free homotopy class, the length of a
shortest homotopic cycle can be computed in $O(\ell+\log n)$ time. Moreover,
given any positive integer $k$, the first $k$ values of its unmarked length
spectrum can be computed in time $O(k \log n)$.
  Our algorithms are based on a correspondence between weighted graphs on the
torus and polyhedral norms. In particular, we give a weight independent bound
on the complexity of the unit ball of such norms. As an immediate consequence
we can decide if two embedded weighted graphs have the same marked spectrum in
polynomial time. We also consider the problem of comparing the unmarked spectra
and provide a polynomial time algorithm in the unweighted case and a randomized
polynomial time algorithm otherwise.
