# Computing with Graphs in Surfaces

I asked this question yesterday on math.stackexchange, but the only response so far hasn't really addressed the question, so I thought I'd cross-post it.

I am currently working on a research project involving a polynomial defined for graphs in surfaces, similar to the Tutte polynomial, except with terms accounting for the embedding. At the moment, it would be very useful if we knew the value of the polynomial for larger graphs, but since the number of terms is exponential in the number of edges, we are running into the limits of hand computation.

For a graph $G$ embedded in a surface $\Sigma$, the polynomial is defined as a sum over spanning subgraphs $H$ of $G$ by

$$P_{G,\Sigma}(Y,A,B)=(−1)^{e(G)}\sum_{H\subset G}(−1)^{e(H)}Y^{n(H)}A^{s(H)}B^{s^\perp(H)}$$

where $e(H)$ is the number of edges of $H$, $n(H)$ is the nullity (rank of the first homology group) of $H$, and $s$ and $s^\perp$ have to do with how much of the genus of $\Sigma$ is "used up" by $H$. All of these can be calculated in terms of the number of edges, vertices and connected components of $H$, as well as the number of connected components of $\Sigma \backslash H$. The polynomial satisfies a contraction-deletion relation, again just like the Tutte polynomial.

Does anyone know of any computer methods for calculating things like this? At the moment, we are just looking at the one-holed torus, and the graph we'd like the polynomial of has eight edges (although being able to deal with more would certainly be nice). I know Mathematica has tools for dealing with abstract graphs, but this polynomial depends on the embedding of the graph.

-
Do you mean the connected components of $\Sigma \setminus H$ or $G \setminus H$? – Vidit Nanda Jul 21 '13 at 20:56
@ViditNanda I think $\Sigma \backslash H$. To find $s(H)$, you take a regular neighborhood of $H$ and glue discs to the boundary circles; then $s(H)$ is the genus of the resulting surface. You can also find the genus of this surface by comparing the nullity of $H$ and the number of components $\gamma$ of $\Sigma \backslash H$, since in the plane, for example, $\gamma = n(H) + 1$, but there can be fewer in higher-genus surfaces. – Calvin McPhail-Snyder Jul 22 '13 at 3:47