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 points or the induced trees of size k on 3-connected cubic planar graph ?

  • $\begingroup$ This is a tangential remark: Tutte proved that every 4-connected planar graph has a Hamiltonian circuit. So if you could ensure 4-connectivity, you would have that guarantee. $\endgroup$ – Joseph O'Rourke Sep 4 '10 at 23:07
  • $\begingroup$ Thank you for the comment. There are 3-connected triangulations which are also hamiltonian, so by checking 4-connectivity I might miss possible solutions. Also I would like to avoid to triangulate under the 4-connectivity constraint for the same reason. $\endgroup$ – katsarola Sep 5 '10 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.