Any two-dimensional infinite regular lattice G can be produced by tiling the plane with a finite subgraph B of G; we call B a basis of G. We introduce a two-parameter graph polynomial P_B(q,v) that depends on B and its embedding in G. The algebraic curve P_B(q,v) = 0 is shown to provide an approximation to the critical manifold of the q-state Potts model, with coupling v = exp(K)-1, defined on G. This curve predicts the phase diagram both in the ferromagnetic (v>0) and antiferromagnetic (v<0) regions. For larger bases B the approximations become increasingly accurate, and we conjecture that P_B(q,v) = 0 provides the exact critical manifold in the limit of infinite B. Furthermore, for some lattices G, or for the Ising model (q=2) on any G, P_B(q,v) factorises for any choice of B: the zero set of the recurrent factor then provides the exact critical manifold. In this sense, the computation of P_B(q,v) can be used to detect exact solvability of the Potts model on G. We illustrate the method for the square lattice, where the Potts model has been exactly solved, and the kagome lattice, where it has not. For the square lattice we correctly reproduce the known phase diagram, including the antiferromagnetic transition and the singularities in the Berker-Kadanoff phase. For the kagome lattice, taking the smallest basis with six edges we recover a well-known (but now refuted) conjecture of F.Y. Wu. Larger bases provide successive improvements on this formula, giving a natural extension of Wus approach. The polynomial predictions are in excellent agreement with numerical computations. For v>0 the accuracy of the predicted critical coupling v_c is of the order 10^{-4} or 10^{-5} for the 6-edge basis, and improves to 10^{-6} or 10^{-7} for the largest basis studied (with 36 edges).