Triangulating with high connectivity

Abstract

We consider the problem of triangulating a given point set, using straight-line edges, so that the resulting graph is "highly connected". Since the resulting graph is planar, it can be at most 5-connected. Under the nondegeneracy assumption that no three points are collinear, we characterize the point sets with three vertices on the convex hull that admit 4-connected triangulations. More generally, we characterize the planar point sets that admit triangulations having neither chords nor complex (i.e., nonfacial) triangles. We also show that any planar point set can be augmented with at most two extra points to admit a 4-connected triangulation. All our proofs are constructive, and the resulting triangulations can be constructed in O(n log n) time. We conclude by stating several open problems. In particular, it is open whether a polynomial-time algorithm exists for determining whether a point set with no degeneracy restrictions and no restrictions on the number of extreme points admits a 4- or 5-connected triangulation.