We consider cyclic graphs, that is, graphs with cyclic orders at the vertices, corresponding to 2-cell embeddings of graphs into orientable surfaces, or combinatorial maps. We construct a three variable polynomial invariant of these objects, the cyclic graph polynomial, which has many of the useful properties of the Tutte polynomial. Although the cyclic graph polynomial generalizes the Tutte polynomial, its definition is very different, and it depends on the embedding in an essential way. 2000 Mathematical Subject Classification: 05C10.
