Visibility Graph Recognition

Given a graph $G=(V,E)$ together with a Hamiltonian cycle $C$ on $V$, decide whether there exists a simple polygon whose vertices occur in the cyclic order $C$ and whose vertex-visibility graph is exactly $G$. Determine the computational complexity of this decision problem.