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 



Minimum separating subdivision in Plane
Your question is equivalent to (a version of) [minimum $k$-cut](http://en.wikipedia.org/wiki/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](http://www.cs.brown.edu/people/claire/Publis/multiwaycut.pdf) give Polynomial time approximation schemes for the planar case.


