**R. Hainz, O. Aichholzer, and F. Aurenhammer**

Let be a simple polygon in the plane and let be a minimum-weight
triangulation of . We prove that the -skeleton of is a subset
of for all values >
provided is
convex or near-convex. This settles the question of tightness of this bound
for a special case and gives evidence for its validity in the general point
set case.

We further disprove the conjecture that the so-called -skeleton coincides with the intersection of all locally minimal triangulations, , even for convex polygons . We introduce an improved -skeleton algorithm which, for simple polygons , exactly computes , and thus a larger subgraph of . The algorithm achieves the same in the general point set case provided the connectedness of the improved -skeleton, which is given in allmost all practical instances.

We further disprove the conjecture that the so-called -skeleton coincides with the intersection of all locally minimal triangulations, , even for convex polygons . We introduce an improved -skeleton algorithm which, for simple polygons , exactly computes , and thus a larger subgraph of . The algorithm achieves the same in the general point set case provided the connectedness of the improved -skeleton, which is given in allmost all practical instances.