6
$\begingroup$

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

Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ @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. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 19, 2011 at 14:26
  • $\begingroup$ @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. $\endgroup$
    – Louis
    Commented Dec 19, 2011 at 14:56
  • $\begingroup$ @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. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 19, 2011 at 15:11
  • $\begingroup$ @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. $\endgroup$
    – Igor Rivin
    Commented Dec 19, 2011 at 16:21
  • $\begingroup$ 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". $\endgroup$
    – Ori Gurel-Gurevich
    Commented Dec 19, 2011 at 16:49
4
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ @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 $\endgroup$
    – user695652
    Commented Dec 19, 2011 at 0:43
  • $\begingroup$ and would end up with a solution of size 8. $\endgroup$
    – user695652
    Commented Dec 19, 2011 at 0:50
  • $\begingroup$ Hmmm... I will ponder... $\endgroup$
    – Igor Rivin
    Commented Dec 19, 2011 at 11:16
  • $\begingroup$ @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. $\endgroup$
    – Louis
    Commented Dec 19, 2011 at 15:48
  • $\begingroup$ @Louis: I am sure that is true, but that does not answer the question of how to fix the algorithm, alas. $\endgroup$
    – Igor Rivin
    Commented Dec 19, 2011 at 16:20
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Wouldn't you want one more vertex on that path? As it's drawn they both remove 6 edges. /nitpick $\endgroup$
    – Michael Biro
    Commented Dec 19, 2011 at 3:38
  • $\begingroup$ @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. $\endgroup$
    – user695652
    Commented Dec 19, 2011 at 6:21
  • $\begingroup$ @Michael & andy: Added a vertex on the vertical path---Thanks for the correction. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 19, 2011 at 10:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .