New results on Pseudo-triangulations with low vertex degree.
André Schulz · Canadian Conference on Computational Geometry · 2005
We show that it is NP-hard to decide if a geometric graph can be extended to a pseudo-triangulation by adding lines and not violating a given degree bound. The equivalent problem for triangulations is known to be NP-hard if we ask for a triangulation with maximum vertex degree 7 [3]. We show that finding a pseudotriangulations is already NP-complete if we forbid vertex degrees greater than 5. The problem stays NPcomplete for pointed pseudo-triangulations. As a second result we show that point sets with uniformly distributed convex layers allow a pseudo-triangulation with low degree and face bound.