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

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

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

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