We have a triangular lattice, and we want to split it into two pieces so that one piece has at most twice the number of triangles as the other piece. Furthermore, the cut should contain the smallest number of vertices possible.

Well, I got something done. It works for a small test file I created, but I never procured a way to visualize a surface mesh, so I didn't test it on anything bigger. Here is the source code: MinTwoThirdsCut.tar.gz.