Tight Degree Bounds for Pseudo-triangulations of Points. Lutz Kettner, David Kirkpatrick, Andrea Mantler, Jack Snoeyink, Bettina Speckmann, and Fumihiko Takeuchi. In: Computational Geometry - Theory and Applications 25(1-2), pp. 3-12, 2003.
We show that every set of n points in general position has a minimum pseudo-triangulation whose maximum vertex degree is five. In addition, we demonstrate that every point set in general position has a minimum pseudo-triangulation whose maximum face degree is four (i.e. each interior face of this pseudo-triangulation has at most four vertices). Both degree bounds are tight. Minimum pseudo-triangulations realizing these bounds (individually but not jointly) can be constructed in O(n log n) time.
[PDF Preprint] © Elsevier.