The Existence of a Pseudo-triangulation in a given Geometric Graph
André Schulz · 2006
We show that the problem of deciding if a pseudotriangulation is contained inside a geometric graph is NP-complete. For this we investigate the Triangulation Existence Problem, which is known to be NP-complete. We present a new proof for its NPcompleteness and modify it in such a way that it can be applied for pseudo-triangulations.