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](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdf) 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 points* or *the induced trees of size k on 3-connected cubic planar graph* ?