  We take an elementary and systematic approach to the problem of extending the
Tutte polynomial to the setting of embedded graphs. Four notions of embedded
graphs arise naturally when considering deletion and contraction operations on
graphs on surfaces. We give a description of each class in terms of coloured
ribbon graphs. We then identify a universal deletion-contraction invariant
(i.e., a `Tutte polynomial') for each class. We relate these to graph
polynomials in the literature, including the Bollob\'as--Riordan, Krushkal, and
Las Vergnas polynomials, and give state-sum formulations, duality relations,
deleton-contraction relations, and quasi-tree expansions for each of them.
