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 ?

Improve this question
$\endgroup$
2
  • 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, 2013 at 4:06
  • 1
    $\begingroup$ You're right. No multiple edges between two points in the interior of the disk. I'll edit. $\endgroup$
    – Anonymous
    Oct 15, 2013 at 12:38

1 Answer 1

Reset to default
2
$\begingroup$
  1. Not necessarily.
  2. See the famous paper of Sleator/Tarjan/Thurston (Journal of the AMS, vol 1, issue 1, I believe).
Improve this answer
$\endgroup$
1
  • 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$
    – Anonymous
    Oct 15, 2013 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.