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.

Back to all abstracts