On the interplay between embedded graphs and delta-matroids

Abstract

The mutually enriching relationship between graphs and matroids has motivated discoveries in both fields. In this paper, we exploit the similar relationship between embedded graphs and delta-matroids. There are well-known connections between geometric duals of plane graphs and duals of matroids. We obtain analogous connections for various types of duality in the literature for graphs in surfaces of higher genus and delta-matroids. Using this interplay, we establish a rough structure theorem for delta-matroids that are twists of matroids, we translate Petrie duality on ribbon graphs to loop complementation on delta-matroids, and we prove that ribbon graph polynomials, such as the Penrose polynomial, the characteristic polynomial, and the transition polynomial, are in fact delta-matroidal. We also express the Penrose polynomial as a sum of characteristic polynomials.

The content of this paper was previously part of arXiv:1403.0920v1, which we have split into two

References in corpus (10)

• Twisted duality for embedded graphs
• The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems
• Interlace Polynomials for Multimatroids and Delta-Matroids
• Separability and the genus of a partial dual
• Matroids, Delta-matroids and Embedded Graphs
• Bipartite partial duals and circuits in medial graphs
• A Penrose polynomial for embedded graphs
• Partial duals of plane graphs, separability and the graphs of knots
• Nullity and Loop Complementation for Delta-Matroids
• Quaternary Bicycle Matroids and the Penrose Polynomial for Delta-Matroids

Cited by in corpus (14)

• Handle slides for delta-matroids
• Delta-matroids as subsystems of sequences of Higgs lifts
• Partial-twuality polynomials of delta-matroids
• Skew characteristic polynomial of graphs and embedded graphs
• The Universal Valuation of Coxeter Matroids
• Hopf algebras and Tutte polynomials
• How many delta-matroids are there?
• Inductive tools for connected ribbon graphs, delta-matroids and multimatroids
• Irreducibility of the Tutte polynomial of an embedded graph
• New Dualities From Old: generating geometric, Petrie, and Wilson dualities and trialites of ribbon graphs
• The excluded 3-minors for vf-safe delta-matroids
• Characterizing matroids whose bases form graphic delta-matroids
• Eulerian and bipartite binary delta-matroids
• The structure of delta-matroids with width one twists