Minimum separating subdivision in Plane Hi
I was thinking about the following problem:
Given a planar Graph embedded in the plane and a set of points $P$ contained in the faces (no face contains more than one point) I want to determine the maximum number of edges I can remove such that in the reduced graph no two points are contained in the same face.
Although I didn't find any publications considering this problem, I guess this must have been studied before. 
Any pointers would be helpful to me.
If $P$ only consists of two points $p,q$ it is easy since, we can just compute the shortest cycle containing either $p$ or $q$ but not both in its face.
Thank you 
Andy 
 A: Your question is equivalent to (a version of) minimum $k$-cut AKA multiway cut. It seems that the general problem is solvable is polynomial time for any fixed $k$, but NP-complete for arbitrary $k$, even restricted to planar graphs. However, Mohammadhossein Bateni, MohammadTaghi Hajiaghayi, Philip Klein, Claire Mathieu give Polynomial time approximation schemes for the planar case.
A: Well, since your graph is planar, your question is really about the dual graph $H=G^*$ (whose vertices are the faces of your graph). Some vertices of $H$ (corresponding to faces with points in them) are marked red, the others blue, and you are asking how many edges of $H$ you can collapse without identifying two red vertices. 
Firstly, no edge joining two red edges can be collapsed. So remove all such edges to get a new graph $H^\prime.$ 
Secondly, all edges connecting two blue vertices in $H^\prime$ can be collapsed. So do it, and obtain a new graph $H^{\prime \prime}.$
Now, you are asking how many edges in $H^{\prime \prime}$ can be collapsed. Such a collection is a maximal matching between the blue and the red sets in $H^{\prime \prime}.$ Finding such is well understood, see:
http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs
A: This is my interpretation of andy's example in his comment to Igor's answer.
$s$ and $t$ are the green points.
Imagine the outer face red because it contains a (green) point.
$L$ and $M$ are blue because they contain no points.
 


Removing $e$ would lead to a less efficient separator.
