Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
@Ori: Could you please sketch the equivalence of the stated problem to min $k$-cut? I don't doubt you, but it is not obvious to me. Thanks. –  Joseph O'Rourke Dec 19 '11 at 14:26
    
@Joe: Here is a dual version of the question: we are given a planar graph with $k$ marked vertices and we want a minimum-sized set of edges that, when removed, disconnects the marked vertices from each other. I think this is what Ori had in mind. –  Louis Theran Dec 19 '11 at 14:56
    
@Louis: Thanks! What I didn't see is the marking, but now I understand that also separating marked vertices falls under the same umbrella as just separating into $k$ components. –  Joseph O'Rourke Dec 19 '11 at 15:11
    
@Louis+@Joe: I don't see how this is equivalent (since we have the $k$ marked vertices, we don't have the choice of what the connected components are, which should make the problem easier. –  Igor Rivin Dec 19 '11 at 16:21
    
I did write "(a version of) minimum $k$-cut". If you look at wikipedia it explicitly mention this version: "It is also NP-complete if we specify k vertices and ask for the minimum k-cut which separates these vertices among each of the sets". Also, the paper I linked deals with this version: "a multiway cut (also called a multi-terminal cut) problem asks for a subset of edges with minimum total length and whose removal disconnects each terminal from the others". –  Ori Gurel-Gurevich Dec 19 '11 at 16:49
show 1 more comment

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

share|improve this answer
4  
@Igor Rivin :Thank you for your answer. Your write: "Secondly, all edges connecting two blue vertices in H′ can be collapsed. So do it, and obtain a new graph H′′." Is this true? Because if i have a rectangle which is horizontaly divided into 3 parts l,m,r. The left division is made by a single vertical edge e, and the right one is done by a vertical path of come length c, and i have a point s in r and a point t outside of the rectangle, then the smallest separating arrangement would contain only 6 edges, but if i collapse any edge connecting two blue vertices i would thusby delete the edge e –  user695652 Dec 19 '11 at 0:43
    
and would end up with a solution of size 8. –  user695652 Dec 19 '11 at 0:50
    
Hmmm... I will ponder... –  Igor Rivin Dec 19 '11 at 11:16
    
@Igor: This is probably redundant, but we don't need to have a non-simple dual or any other such messiness to make examples where greedily discarding blue-blue edges is bad. Start with a triangulation with a marked triangle. Now take another such triangulation, and glue it in to the first one along a triangle not incident to either of the marked faces. Repeat this a bunch of times to get a kind of "generalized stacked polytope". The edges we want to keep are just the separating triangles in the graph we constructed, but those are all going to be blue-blue in the dual. –  Louis Theran Dec 19 '11 at 15:48
    
@Louis: I am sure that is true, but that does not answer the question of how to fix the algorithm, alas. –  Igor Rivin Dec 19 '11 at 16:20
show 1 more comment

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.
  Separating Arrangement
Removing $e$ would lead to a less efficient separator.

share|improve this answer
    
Wouldn't you want one more vertex on that path? As it's drawn they both remove 6 edges. /nitpick –  Michael Biro Dec 19 '11 at 3:38
    
@Joseph O'Rourke Yes this is exactly the example I was thinking about, thank you very much for the picture. Do you know anything about this problem? @Michael Biro Yes one more vertex on the path would make the counterexample even more clear. –  user695652 Dec 19 '11 at 6:21
    
@Michael & andy: Added a vertex on the vertical path---Thanks for the correction. –  Joseph O'Rourke Dec 19 '11 at 10:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.