Triangulating with high connectivity

Dey, Tamal Krishna ; Dillencourt, Michael B. ; Ghosh, Subir K. ; Cahill, Jason M. (1997) Triangulating with high connectivity Computational Geometry, 8 (1). pp. 39-56. ISSN 0925-7721

Full text not available from this repository.

Official URL:

Related URL:


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.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Discrete Geometry; Triangulations; K-connectedness
ID Code:76278
Deposited On:31 Dec 2011 08:57
Last Modified:31 Dec 2011 08:57

Repository Staff Only: item control page