  The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that
encodes many interesting properties of the graph. We study the complexity of
the following problem, for rationals x and y: given as input a planar graph G,
determine T(G;x,y). Vertigan completely mapped the complexity of exactly
computing the Tutte polynomial of a planar graph. He showed that the problem
can be solved in polynomial time if (x,y) is on the hyperbola H_q given by
(x-1)(y-1)=q for q=1 or q=2 or if (x,y) is one of the two special points
(x,y)=(-1,-1) or (x,y)=(1,1). Otherwise, the problem is #P-hard. In this paper,
we consider the problem of approximating T(G;x,y), in the usual sense of "fully
polynomial randomised approximation scheme" or FPRAS. Roughly speaking, an
FPRAS is required to produce, in polynomial time and with high probability, an
answer that has small relative error. Assuming that NP is different from RP, we
show that there is no FPRAS for the Tutte polynomial in a large portion of the
(x,y) plane. In particular, there is no FPRAS if x>1, y<-1 or if y>1, x<-1 or
if x<0, y<0 and q>5. Also, there is no FPRAS if x<1, y<1 and q=3. For q>5, our
result is intriguing because it shows that there is no FPRAS at
(x,y)=(1-q/(1+epsilon),-epsilon) for any positive epsilon but it leaves open
the limit point epsilon=0, which corresponds to approximately counting
q-colourings of a planar graph.
