After some thought I think it works as-is if you just delete all edges between points which can't directly see each-other, as long as the visibility graphs are

After some thought I think it works as-is if you just delete all edges between points which can't directly see each-other, as long as the visibility graphs are still connected. The best cuts could then sometimes be edge->edge instead of always vertex->vertex. (e.g. each point at a random position in a little bump, where you want to slice off all the bumps in one go without going off at a random angle. I'm trying to think about the topology of cuts in the plane but its hard to visualize. I guess it must be related to Voronoi and Delaunay.