We consider two operations on an edge of an embedded graph (or equivalently a ribbon graph): giving a half-twist to the edge, and taking the partial dual with respect to the edge. These two operations give rise to an action of <!-- MATH ${S_3}^{|E(G)|}$ --> , the ribbon group, on . The action of the ribbon group on embedded graphs extends the concepts of duality, partial duality, and Petrie duality. We show that this ribbon group action gives a complete characterization of duality in that if is any cellularly embedded graph with medial graph , then the orbit of under the group action is precisely the set of all graphs with medial graphs isomorphic (as abstract graphs) to . We provide characterizations of special sets of twisted duals (such as the partial duals) of embedded graphs in terms of medial graphs, and we show how different kinds of graph isomorphism give rise to these various notions of duality. The ribbon group action then leads to a deeper understanding of the properties of, and relationships among, various graph polynomials via the generalized transition polynomial which interacts naturally with the ribbon group action.
The vertex-nullity interlace polynomial of a graph, described by Arratia, Bollobás and Sorkin in [3] as evolving from questions of DNA sequencing, and extended to a two-variable interlace polynomial by the same authors in [5], evokes many open questions. These include relations between the interlace polynomial and the Tutte polynomial and the computational complexity of the vertex-nullity interlace polynomial. Here, using the medial graph of a planar graph, we relate the one-variable vertex-nullity interlace polynomial to the classical Tutte polynomial when x=y, and conclude that, like the Tutte polynomial, it is in general #P-hard to compute. We also show a relation between the two-variable interlace polynomial and the topological Tutte polynomial of Bollobás and Riordan in [13].We define the γ invariant as the coefficient of x1in the vertex-nullity interlace polynomial, analogously to the β invariant, which is the coefficientof x1in the Tutte polynomial. We then turn to distance hereditary graphs, characterized by Bandelt and Mulder in [9] as being constructed by a sequence ofadding pendant and twin vertices, and show that graphs in this class have γ invariant of 2n+1whenntrue twins are added intheir construction. We furthermore show that bipartite distance hereditary graphs are exactly the class of graphs with γ invariant 2, just as the series-parallel graphs are exactly the class of graphs with β invariant 1. In addition, we show that a bipartite distance hereditary graph arises precisely as the circle graph of an Euler circuitin the oriented medial graph of a series-parallel graph. From this we conclude that the vertex-nullity interlace polynomial is polynomial time to compute for bipartite distancehereditary graphs, just as the Tutte polynomial is polynomial time to compute for series-parallel graphs.
We find new properties of the topological transition polynomial of embedded graphs, Q(G). We use these properties to explain the striking similarities between certain evaluations of Bollobás and Riordan's ribbon graph polynomial, R(G), and the topological Penrose polynomial, P(G). The general framework provided by Q(G) also leads to several other combinatorial interpretations these polynomials. In particular, we express P(G), R(G), and the Tutte polynomial, T(G), as sums of chromatic polynomials of graphs derived from G, show that these polynomials count k-valuations of medial graphs, show that R(G) counts edge 3-colourings, and reformulate the Four Colour Theorem in terms of R(G). We conclude with a reduction formula for the transition polynomial of the tensor product of two embedded graphs, showing that it leads to additional relations among these polynomials and to further combinatorial interpretations of P(G) and R(G).