Deleting nodes from graph so that they can be separated by a straight line
Try the following (inefficient) approach. Assume there are $N$ points in total. Now with each of the $N$ points try to find a line segment that passes through it with the least number of mis-classifications (number of points that were not correctly separated) by the line segment. The important point to note here is that, you would not have more than $N-1$ such line segments to check for. At the end of the procedure simply choose the point and its best corresponding line segment. The overall complexity is $O(N^3)$ under ideal conditions. Some perturbation of point may be required in the process, if not ideal. 

A slightly more efficient procedure is as follows, let the convex hull of the points in type 1 be $P_1$ and those of type 2 be $P_2$. Then I suspect, in the previous procedure, instead of computing the best line segment for every point, just do the procedure for those in $P_1 \cap P_2$.