A polynomial invariant of graphs on orientable surfaces (Q2766427)

The authors [Math. Ann. 323, 81-96 (2002; Zbl 1004.05021)] introduced a polynomial invariant, called the ribbon graph polynomial, of ribbon graphs (informally, neighborhoods of graphs imbedded in surfaces) on four variables, generalizing the Tutte polynomial. In the present paper, they construct a polynomial invariant, called the cyclic graph polynomial, of cyclic graphs (connected graphs with cyclic orderings of neighbors at vertices; that is, 2-cell imbeddings of graphs into closed oriented 2-manifolds) on three variables, also generalizing the Tutte polynomial. They introduce an algebraic notion of the rank of a chord diagram (informally, a one-vertex cyclic graph) needed to define the cyclic graph polynomial in terms of recurrence relations and a boundary condition. Their main result is that these relations have a unique solution. Various properties of the cyclic graph polynomial are established. For example, like both the Tutte polynomial and the ribbon graph polynomial, the cyclic graph polynomial has a spanning tree expansion. For the cyclic graph polynomial, the spanning tree expansion depends on the imbedding in an essential way.