Hi

I was thinking about the following problem:

Given a planar Graph embedded in the plane and a set of points 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.

Thank you 

Andy