Given a *triangulation* $T$ of a planar set point $S$, we would like to randomly generate a *polygon* (hamiltonian cycle) $P$.

However, it has been proved that **Hamiltonian Circuit Problem** on maximal planar graphs is **NP-complete**.

So, I suppose that uniformly random generation of such polygons is hard.

A polygon on $n$ points can be decomposed in $n-2$ triangles. So, the dual graph of a polygon is a tree of $n-2$ nodes.

That implies that if we could count the induced trees of size $k=n-2$ (where $n$ is the size of $S$) on the dual graph of a triangulation (which is a 3-connected cubic planar graph), we could count the hamiltonian cycles of a maximal planar graph (planar point set triangulation). So counting the induced trees of size k on 3-connected cubic planar graph is also NP-complete.

So my question is. Is there any approximation algorithm (e.g. Markov Chain Monte Carlo) which deals with the counting of

hamiltonian cycles of maximal planar set pointsorthe induced trees of size k on 3-connected cubic planar graph?