  We introduce a polynomial invariant of graphs on surfaces, $P_G$,
generalizing the classical Tutte polynomial. Topological duality on surfaces
gives rise to a natural duality result for $P_G$, analogous to the duality for
the Tutte polynomial of planar graphs. This property is important from the
perspective of statistical mechanics, where the Tutte polynomial is known as
the partition function of the Potts model. For ribbon graphs, $P_G$ specializes
to the well-known Bollobas-Riordan polynomial, and in fact the two polynomials
carry equivalent information in this context. Duality is also established for a
multivariate version of the polynomial $P_G$. We then consider a 2-variable
version of the Jones polynomial for links in thickened surfaces, taking into
account homological information on the surface. An analogue of Thistlethwaite's
theorem is established for these generalized Jones and Tutte polynomials for
virtual links.
