The Martin polynomial of an oriented 4-regular graph was defined by Pierre Martin in 1977. He showed that if G is a plane graph and is its directed medial graph, then Algorithms Deletion–contraction The deletion–contraction recurrence for the Tutte polynomial, immediately yields a recursive algorithm for computing it for a given graph: as long as you can find an edge e that is not a loop or bridge, recursively compute the Tutte polynomial for when that edge is deleted, and when that edge is contracted. Then add the two sub-results together to get the overall Tutte polynomial for the graph. The base case is a monomial where m is the number of bridges, and n is the number of loops. Within a polynomial factor, the running time t of this algorithm can be expressed in terms of the number of vertices n and the number of edges m of the graph, a recurrence relation that scales as the Fibonacci numbers with solution The analysis can be improved to within a polynomial factor of the number of spanning trees of the input graph. For sparse graphs with this running time is . For regular graphs of degree k, the number of spanning trees can be bounded by where so the deletion–contraction algorithm runs within a polynomial factor of this bound. For example: In practice, graph isomorphism testing is used to avoid some recursive calls. This approach works well for graphs that are quite sparse and exhibit many symmetries; the performance of the algorithm depends on the heuristic used to pick the edge e. Gaussian elimination In some restricted instances, the Tutte polynomial can be computed in polynomial time, ultimately because Gaussian elimination efficiently computes the matrix operations determinant and Pfaffian. These algorithms are themselves important results from algebraic graph theory and statistical mechanics. equals the number of spanning trees of a connected graph. This is computable in polynomial time as the determinant of a maximal principal submatrix of the Laplacian matrix of G, an early result in algebraic graph theory known as Kirchhoff’s Matrix–Tree theorem. Likewise, the dimension of the bicycle space at can be computed in polynomial time by Gaussian elimination. For planar graphs, the partition function of the Ising model, i.e., the Tutte polynomial at the hyperbola , can be expressed as a Pfaffian and computed efficiently via the FKT algorithm. This idea was developed by Fisher, Kasteleyn, and