MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
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. – Joseph O'Rourke Sep 4 '10 at 23:07
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. – katsarola Sep 5 '10 at 19:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.