Tight degree bounds for pseudo-triangulations of points.
Lutz Kettner, David G. Kirkpatrick, Bettina Speckmann · Carolina Digital Repository (University of North Carolina at Chapel Hill) · 2001
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.