9
$\begingroup$

Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior. Let T be a triangulation of the whole disk with vertices on the labelled points such that T contains no self-loops except the boundary of the disk, no multiple edges between two points in the interior of T, arcs of T can be curved.

1) Does T have an Hamiltonian circuit ?

2) If R is another triangulation of the same time, how many flips (as a function of $ n $ should one perform at most in order to get from R to T ?

$\endgroup$
  • 6
    $\begingroup$ I don't get it. The face inside and adjacent to the boundary can only be a triangle if its other two edges join the same pair of vertices. But you ruled out multiple edges.. $\endgroup$ – Brendan McKay Oct 15 '13 at 4:06
  • 1
    $\begingroup$ You're right. No multiple edges between two points in the interior of the disk. I'll edit. $\endgroup$ – yanglee Oct 15 '13 at 12:38
2
$\begingroup$
  1. Not necessarily.
  2. See the famous paper of Sleator/Tarjan/Thurston (Journal of the AMS, vol 1, issue 1, I believe).
$\endgroup$
  • 2
    $\begingroup$ I know that paper, it's about triangulations of a polygon. Labelled points are inside the disk in my case. Methods used are pure hyperbolic geometry (!) $\endgroup$ – yanglee Oct 15 '13 at 2:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.