4
$\begingroup$

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 ?

Improve this question
$\endgroup$
2
  • $\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
    Commented Sep 4, 2010 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
    Commented Sep 5, 2010 at 19:14

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .