Donald Bren School of Information and Computer Sciences

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 noncomplex (i.e., nonfacial) triangles. We also show that any planar point set can be augmented with at most 2 extra points to admit a 4-connected triangulation. All our proofs are constructive, and the resulting triangulations can be constructed in 0(n log n) time. We conclude by stating several open problems.