Visualising the Tutte Polynomial Computation

Author(s). Bennett Thompson, David J. Pearce and Gary Haggard.

Venue. In New Zealand Conference on Software Engineering (SIENZ), 2007.

Abstract: The Tutte polynomial is an important concept in graph theory which captures many important properties of graphs (e.g. chromatic number, number of spanning trees etc). It also provides a normalised representation that can be used as an equivalence relation on graphs and has applications in diverse areas such micro-biology and physics. A highly efficient algorithm for computing Tutte polynomials has been elsewhere developed by Haggard and Pearce. This relies on various optimisations and heuristics to improve performance; however, understanding the effect of a particular heuristic remains challenging, since the computation trees involved are very large. Therefore, we have constructed a visualisation of the computation in order to study the effect of various heuristics on the algorithms’ operation.