I just saw I was a bit short on the subject with my last post.
As it contained a link to the relevant paper “Optimal decomposition of polygonal models into triangle strips” (Regina Estkowski, Joseph S. B. Mitchell, Xinyu Xiang. Proceedings of Symposium on Computational Geometry 2002) it still seems to be awaiting moderator approval.
In the meantime I will try to clarify things.
Don’t get things wrong: Nobody claims dissecting a mesh into an arbitrary dissection of triangle strips is NP-complete.
Obviously calculating an arbitrary dissection is quite easy to do. Even a list containing every single triangle of a mesh with n triangles is a dissection into n triangle strips of length 1.
It is the problem of computing an optimal dissection into triangle strips that is NP-comlete.
Optimal in the sense, that it is made of a minimal number of triangle strips.
Given the fact that the k-STRIPABILITY problem is NP-complete, it is quite easy to see the problem of computing an optimal dissection into triangle strips is NP-complete by reduction:
If I were able to solve the optimal triangle strip dissection problem in polynomial time, I could solve the k-STRIPABILITY in polynomial time as well by just comparing the number of triangle strips in the optimal dissection to k.