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.

Thank you 

Andy