# Calculating Genus Polynomials via String Operations and Matrices, Part~I

###
Jonathan Gross

Columbia University

####
Imran Khan

PUCIT, Pakistan

####
Toufik Mansour

University of Haifa, Israel

####
Thomas Tucker

Colgate University, New York, USA

PDF

**Minisymposium:**
GRAPH IMBEDDINGS AND MAP SYMMETRIES

**Content:**
In calculations of genus polynomials for a recursively specifiable sequence of graphs, the imbeddings of each of the graphs are partitioned into \textit{imbedding-types}. The effects of a recursively applied graph operation $\tau$ on each imbedding-type are represented by a \textit{production matrix}. We demonstrate herein how representing the operation $\tau$ by \textit{string operations} enables us to automate the calculation of the production matrices, a task requiring time proportional to the square of the number of imbedding-types. It also allows us to reduce the number of imbedding-types, which lets us calculate some genus polynomials that were heretofore computationally infeasible.