# Minimum separating subdivision in Plane

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

-

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.

-
@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

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

-
@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

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.

Removing $e$ would lead to a less efficient separator.

-
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