Types of embedded graphs and their Tutte polynomials

Abstract

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ás--Riordan, Krushkal, and Las Vergnas polynomials, and give state-sum formulations, duality relations, deleton-contraction relations, and quasi-tree expansions for each of them.

arXiv commentThis is the authors accepted manuscript / version of record with an unfortunate typo corrected on p24

References in corpus (5)

• Knot invariants and the Bollobas-Riordan polynomial of embedded graphs
• Non-orientable quasi-trees for the Bollobas-Riordan polynomial
• Partial duals of plane graphs, separability and the graphs of knots
• Quasi-tree expansion for the Bollobás-Riordan-Tutte polynomial
• Polynomial invariants of graphs on surfaces

Cited by in corpus (1)

• Irreducibility of the Tutte polynomial of an embedded graph