Enumerating graph embeddings and partial-duals by genus and Euler genus
Jonathan L. Gross, Thomas W. Tucker · Enumerative Combinatorics and Applications · 2020
We present an overview of an enumerative approach to topological graph theory, involving the derivation of generating functions for a set of graph embeddings, according to the topological types of their respective surfaces.We are mainly concerned with methods for calculating two kinds of polynomials: * × * G (z), which are taken over the partial-duals for all subsets of edges, for Poincaré duality ( * ), Petrie duality (×), and Wilson duality ( * × * ), respectively.We describe the methods used for the computation of recursions and closed formulas for genus polynomials and partial-dual polynomials.We also describe methods used to examine the polynomials pertaining to some special families of graphs or graph embeddings, for the possible properties of interpolation and log-concavity.