  In this paper, we will show dichotomy theorems for the computation of
polynomials corresponding to evaluation of graph homomorphisms in Valiant's
model. We are given a fixed graph $H$ and want to find all graphs, from some
graph class, homomorphic to this $H$. These graphs will be encoded by a family
of polynomials.
  We give dichotomies for the polynomials for cycles, cliques, trees,
outerplanar graphs, planar graphs and graphs of bounded genus.
