# Computing with graphs in surfaces

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.

[I'm not sure if all of the tags are appropriate, so feel free to let me know.]

## 1 Answer

I'm currently researching in graph polynomials using Maple; here's some simple code that works over spanning subgraphs and determines the values of $n$, $e$, and $c$ for starters:

   pgtor := proc (G)
local p, ss, n, H, e, c;
p := 0;
n := GraphTheory:-NumberOfVertices(G);
for ss in combinat:-powerset(GraphTheory:-Edges(G)) do
H := GraphTheory:-DeleteEdge(G, ss, inplace = false);
e := GraphTheory:-NumberOfEdges(H);
c := nops(GraphTheory:-ConnectedComponents(H));
p := p+(-1)^e*Y^(e-n+c)*A*B;
end do;
RETURN((-1)^GraphTheory:-NumberOfEdges(G)*sort(p))
end proc


For my polynomials Maple works for most graphs up to 15 or so vertices, more if some special substructures can be coded into the program...

If you can explain more about how the embedding of the graph on the surface comes into play that should be possible to build in too.