This paper is the second of a series of two about polynomial graphs.
Let $\Phi(x,y)\in\mathbb{C}[x,y]$ be a symmetric polynomial of partial
degree $d$ and let $I$ be the ideal generated by $\Phi(x,y)$. The
graph $G(\Phi)$ is defined by taking $\mathbb{C}$ as set of vertices
and the points of $\mathbb{V}(I)$ as edges. We study the following
problem: given a finite, connected, $d$regular graph $H$, find the
polynomials $\Phi(x,y)$ such that $G(\Phi)$ has some connected
component isomorphic to $H$ and, in this case, if $G(\Phi)$ has (almost)
all components isomorphic to $H$. The problem is solved by associating to
$H$ a characteristic ideal which offers a new perspective to the
conjecture formulated in the first paper, and allows to reduce its
scope. In the second part, we determine the characteristic ideal
for cycles of lengths $\le 5$ and for complete graphs of order $\le 6$.
This results provide new evidence for the conjecture.
