First of all, we show that $d$ should be at least $n$. The vertices of the polygon are on $n+1$ different vertical lines and between any two such lines the polynomial should intersect two edges of the polygon, one above and one below the $x$-axis. So by the intermediate value theorem the polynomial should have at least $n$ roots.

Now we want to say that $n$ is sufficient. Choose $n+1$ points on the vertical lines that passing through vertices like below. By the Lagrange Interpolation formula there is a polynomial of degree at most $n$ that cross these $n+1$ points. Again By the intermediate value theorem this polynomial should intersects all edges. So the polynomial is of degree $n$.