The Computational Complexity of Tutte Invariants for Planar Graphs
Dirk Vertigan · SIAM Journal on Computing · 2005
For each pair of algebraic numbers $(x,y)$, the complexity of computing the Tutte polynomial $T(G;x,y)$ of a planar graph G is determined. This computation is found to be $\overline{\rm#P}$-complete except when $(x-1)(y-1)=1,2$ or when $(x,y)$ is one of $(1,1)$, $(-1,-1)$, $(j,j^2)$, or $(j^2,j)$, where $j=e^{2\pi i/3}$, in which case it is polynomial time computable. A corollary gives the computational complexity of various enumeration problems for planar graphs.