<p><a href="http://cse.iitkgp.ac.in/~pabitra/paper/barna-sdm07.pdf">http://cse.iitkgp.ac.in/~pabitra/paper/barna-sdm07.pdf</a></p>

<p>BAM, here's the answer. Incremental min cut graph partitions in $O(k^3)$ time for insertions and deletions. If you make $k = O(\log n)$ then it's poly logarithmic for insertions and deletions, which is damn good.</p>

CC BY-SA 3.0
2014-02-24T00:42:25.850Z
there were many constraints given on the problem. does this really satisfy all of them?
vzn
CC BY-SA 3.0
2014-02-24T01:24:09.030Z
Yes. We can choose any size k for any step. We guarantee minimized cut-edges (inter-partition edges). We also have the ability to add and remove vertices and edges in low time complexity. That satisfies everything.
zaloo
CC BY-SA 3.0
2014-02-23T21:16:17.830Z
2014-02-23T21:16:17.830Z
zaloo
<p>Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time <a href="http://www.sommer.jp/planarapxq.htm">seems possible</a>. Recursive bisection, while not ideal, might be a feasible approach for your problem.</p>

<p>Satish Rao. <a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.1987.26">Finding near optimal separators in planar graphs</a>. In 28th Symposium on Foundations of Computer Science (FOCS), pages 225-237, 1987.</p>

<p>Satish Rao. <a href="http://doi.acm.org/10.1145/129712.129735">Faster algorithms for finding small edge cuts in planar graphs</a> (extended abstract). In 24th ACM Symposium on Theory of Computing (STOC), pages 229-240, 1992.</p>

<p>Horst D. Simon and Shang-Hua Teng. <a href="http://dx.doi.org/10.1137/S1064827593255135">How Good is Recursive Bisection?</a> 
In  SIAM Journal on Scientific Computing, Volume 18, Issue 5, pages 1436-1445, 1997.</p>

CC BY-SA 3.0
2014-02-23T01:11:10.730Z
Awesome links, I'll check them out!
zaloo
CC BY-SA 3.0
2014-02-23T01:07:02.350Z
2014-02-23T01:07:02.350Z
Christian Sommer
<p>The following algorithm might help.</p>

<pre><code>1. Choose any vertex from the graph.

2. Do a BFS untill $O(K)$ vertices has been visited.

3. Create a cluster with the visited vertices. (Connectivity is ensured for the cluster).

4. Remover the visited vertices from the graph.

5. Repeat 1-4 untill all nodes are visited.
</code></pre>

<p>Every cluster contains $O(K)$ vertices and those vertices are found by BFS. Again the the degree of each vertex is constant. So the inter-cluster edges are also $O(K)$. I think it's a lower bound on the number of inter-cluster edges. The complexity of the algorithm is clearly linear in number of edges as only BFS is performed. The number of cluster is also $O(N/K)$.</p>

<p>Also modification of the graph by adding vertices would not affect the partition. Any one partition in which one of the neighbour of the new vertex lies, that can be the partition of the new vertex. So , may be no repartition is required untill the size of one of the cluster becomes too much.</p>

<p>Edit:</p>

<p>Here is a proof that it is not possible to do better than linear number of inter-partition edge for arbitary $k$. Let in some partition there are $m$ vertices and it is connected. At best, the corresponding triangles would construct a convex region $\mathscr{R}$. Now for arbitary $k$ the convex hull of $\mathscr{R}$ can contain $O(K)$ triangle corners. So in total you would have $O(K)$ edge going out from $\mathscr{R}$. 
However if $k$ is $O(log n)$ then may be the inter-partition edges can be reduced.</p>

CC BY-SA 3.0
2014-02-20T16:20:12.243Z
If you apply this to a complete graph, then there are $\Omega(N(N-K))$ inter-partition edges.  Why do you say "the inter-cluster edges are only $O(K)$"?
András Salamon
CC BY-SA 3.0
2014-02-20T16:43:48.723Z
I think the answer refers to planar graphs. But I still don't see why "each vertex has constant degree" ? this is true "on average" but not for any vertex.
Suresh Venkat
CC BY-SA 3.0
2014-02-20T17:07:01.380Z
The degree of each vertex in the graph is at most 3. It is less than 3 if it is on the boundary and no outerface is considered. Hence each vertex has constant degree. @SureshVenkat
Dibyayan
CC BY-SA 3.0
2014-02-20T17:08:52.950Z
Because of the above the inter-cluster edges is $O(K)$. @AndrásSalamon
Dibyayan
CC BY-SA 3.0
2014-02-20T17:18:53.720Z
Ah you mean in the dual graph ? not the primal planar graph.
Suresh Venkat
CC BY-SA 3.0
2014-02-20T17:22:40.763Z
This algorithm is almost identical to the $O(k^2p^2(v+e)) $ algorithm that I had initially developed. The problem with this is that you can still have O(n) inter-partition edges which is undesirable. If every vertex in the graph has degree 3 and you imagine taking "lines" of vertices as partitions (where each vertex in the partition has only degree 1 or 2), then there are guaranteed to be $n/3$ inter-partition edges.
zaloo
CC BY-SA 3.0
2014-02-20T17:29:59.073Z
There might be even more degenerate cases when each each partition has the form of a tree where the root node has 3 children and the rest have 2 children. In this case there are (k-1)/2 leaves that each have 2 inter partition edges. That means we have k-1 interpartition edges for each partition, which for a graph of vertices with degree 3 gives us $(n/k)(k-1) = n-1/k$ inter-partition edges. This is only a reduction of 1/3rd of the edges which isn't very nice. However I'm not even sure if there is a way to have less than O(n) inter-partition edges so I might be being too picky.
zaloo
CC BY-SA 3.0
2014-02-20T18:09:59.880Z
I think in that case you need a nicer defination for the value of $k$. Some arbitary value of $k$ certainly won't work. In planar graphs number of edges is linear in number of vertices. With proper denser partition and setting the value of $k$ appropriately we may get constant number of inter partition edges. Certainly, i shall think about it.
Dibyayan
CC BY-SA 3.0
2014-02-20T18:38:10.013Z
Not sure if the edit is notified to the author of the question. So, may be there is a proof for showing that $O(N)$ edges is unavoidable.Please see in the edit. @zaloo
Dibyayan
CC BY-SA 3.0
2014-02-20T21:29:11.143Z
I understand exactly what you're saying. I believe that I'll need to have the size of $k$ to be related to $n$. I modified my OP to reflect this and to have some additional constraints as well, so I hope that helps.
zaloo
CC BY-SA 3.0
2014-02-20T16:05:50.697Z
2014-02-20T18:43:06.940Z
2014-02-20T18:43:06.940Z
Dibyayan
<p>did some search on this but held off on posting immed to see what other answers would materialize &amp; am now posting this to not throw away some misc ideas/leads which could have some value (although the question author has already indicated hes now found an acceptable answer). </p>

<p>on inspection there are many constraints given on this problem and it could conceivably take an entire paper to create an algorithm &amp; prove that it satisfies all them (which of course is generally outside the scope of stackexchange format). nevertheless there are a few basic approaches to take on this type of problem</p>

<ol>
<li><p>empirical. generate random graphs that fit the constraints or use graphs from some dataset that match the conditions and try different algorithms on them, and look at performance. one may find that an algorithm empirically satisfies the conditions reqd. if one is more strict, one could attempt to create a proof out of the empirical observation if its 100% satisfied by large datasets. also for empirical research it often helps to know how the datasets are obtained/generated, what their nature/origination is.</p></li>
<li><p>the question has no related citations of literature/refs. so what are the nearest types of algorithms in the literature? for this type of problem multiple types of research areas might overlap. there is research on planar graphs, graph partitions, graph cuts, graph separators, partitioning triangular graphs, etc.; its not obvious to figure out the main theme of this question so far as its formulated or which particular (graph algorithm) research sub-area would most directly impinge on it.</p></li>
</ol>

<p>given those qualifications a basic theme of the question seems to be "partitioning planar graphs". here are some leading recent refs on that topic which might be helpful &amp; show additional themes/angles of current related research. there are some algorithms implemented &amp; they may be available on request from the authors. </p>

<p>the 3<sup>rd</sup> involves partitioning with weights, which will generalize to equal weights, but which gives an additional framework for consideration/investigation: could all the question conditions be fulfilled by some kind of weight assignment scheme? (this could also tie in with the requirement to have some kind of dynamic control or adjustment over solutions also referred to in the question.)</p>

<ul>
<li><p><a href="http://www.sciencedirect.com/science/article/pii/S0024379506003454" rel="nofollow">Spectral partitioning works: Planar graphs and finite element meshes</a> Spielman/Teng</p></li>
<li><p><a href="http://link.springer.com/chapter/10.1007%2F10692760_26" rel="nofollow">Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases</a> Wada, Chen</p></li>
<li><p><a href="http://people.scs.carleton.ca/~maheshwa/papers/acmjea.pdf" rel="nofollow">Partitioning planar graphs with costs and weights</a> Aleksandrov et al</p></li>
</ul>

CC BY-SA 3.0
2014-02-24T01:05:57.790Z
2014-02-24T01:20:40.733Z
2014-02-24T01:20:40.733Z
vzn
<p>I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been partitioned into 4 "clusters": <img src="https://i.sstatic.net/080uz.png" alt="Example Triangulation with Partitioning"></p>

<p>What I wanted originally was an algorithm that could create partitions of approximately k triangles (there could be some error as long it wasn't too large), and I managed to figure out a $O(k^2p^2(v+e))$ algorithm (where p is the total number of partitions) that could find such a partitioning. I then realized that having large numbers of inter-partition edges were detrimental for the application I needed this algorithm for.</p>

<p>Ideally, I'd like an algorithm that can keep each partition within some range of $k$, ideally have it be a constant factor like 2. Also, I'd like to be able to make the number of inter-edges have an upper bound that is "low". </p>

<p>Additionally, another problem I have is if I have a partition that has these properties, and I modify the graph by doing one of the following:</p>

<ul>
<li>Adding a set of edges connecting to existing vertices</li>
<li>Adding a vertex and a set of edges connecting to the added vertex</li>
<li>Removing a set of edges</li>
<li>Removing a vertex and all edges that connect to this vertex</li>
</ul>

<p>I want to be able to repartition the graph and still have each partition with size $k$ and number of cut edges minimized. (This is the solution I'm putting up a bounty for). This means that using this algorithm, we can construct any partition by starting with an empty graph and adding vertices and edges one by one and repartitioning.</p>

<p>Here's some additional constraints to the problem:</p>

<ul>
<li>The graph is planar</li>
<li>Each "triangle" is a vertex that has undirected edges to triangles it shares an edge with</li>
<li>From the above statement, it is obvious that each vertex in this graph has degree at most 3</li>
<li>The graph is connected</li>
<li>Each subgraph from the partition is connected</li>
<li>Each subgraph has approximately k vertices</li>
<li>There are at most $\sqrt n$ inter-partition edges (edges that contain a vertices from different partitions). If you can find a similar bound for inter-partition edges like $2\sqrt n$ or $O(\log n)$ then that could work too. I'm not entirely sure the upper bound for inter-partition edges can be less than $O(n)$ so if you can prove that its impossible to do better, that is satisfying as well.</li>
</ul>

<p>I'm at a point where I'm stuck, so any help with this problem would be lovely. If you can flat out solve this problem, you're the bees knees. Otherwise, if you know of any papers or textbooks or algorithms you could point me to, I'd appreciate it very much.</p>

<p>Let me know if I need to clarify anything!</p>

<p>EDIT: Here are some additional constraints if it makes the problem easier.</p>

<ul>
<li>We are dealing with constrained delaunay triangulations</li>
<li>Constraints will NEVER be a single vertex</li>
<li>The graph created from the triangulation is constructed as follows: each triangle is represented as a vertex. Each edge in the graph corresponds to an unconstrained edge in the triangulation. This means that a constrained edge between two triangles will not show up in the graph representation of the triangulation.</li>
</ul>

<p>Another thing I realized is that we may need to modify $k$ to grow as $n$ grows, otherwise there can be no sub $O(n)$ guarantees on the number of inter-partition edges.</p>

CC BY-SA 3.0
2014-02-17T07:41:02.607Z
It's not entirely clear what you want. Do you want a partition where each set is of roughly equal size, or one with a fixed number of sets ? I understand that in either case, you want to minimize the number of inter-set edges.
Suresh Venkat
CC BY-SA 3.0
2014-02-17T17:04:54.640Z
We only want the partitions to be sets of roughly equal size and within some range of k, we don't care about the total number of sets.
zaloo
CC BY-SA 3.0
2014-02-17T20:25:54.013Z
I see. so each partition should have roughly $k$ elements in it.
Suresh Venkat
CC BY-SA 3.0
2014-02-18T06:42:07.417Z
I don't have a guarantee for this heuristic, but since your graph is planar, something like a Miller hierarchy of rings might do the trick. In brief, use the planar separator theorem to split the graph into two roughly equal parts with a small number of edges between them, and recurse till all pieces are roughly of size $k$. You'll end up with a cut size close to $\sqrt{n}$.
Suresh Venkat
CC BY-SA 3.0
2014-02-18T17:12:07.257Z
Doesn't a planar separator not guarantee anything about the connectedness of the sets of vertices that are formed?
zaloo
CC BY-SA 3.0
2014-02-18T17:17:48.647Z
Also, how do you know that the cut size is close to $n^{1/2}$?
zaloo
CC BY-SA 3.0
2014-02-18T18:16:12.510Z
Do you care about connectedness of the sets formed ? that wasn't in the question. As for the cute size being close to $\sqrt{n}$, that follows from the planar separator theorem applied recursively.
Suresh Venkat
CC BY-SA 3.0
2014-02-18T20:19:35.117Z
The first line states that I want connected subgraphs. Sorry if I wasn't clear but this is a very important part of the problem
zaloo
<graph-theory><graph-algorithms><planar-graphs><partition-problem><delaunay-triangulation>
Partitioning graphs while minimizing inter-partition edges
zaloo
# Partitioning graphs while minimizing inter-partition edges

(Asked by: username_0 on 2014-02-17)

I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been partitioned into 4 "clusters": ![Example Triangulation with Partitioning](https://i.sstatic.net/080uz.png)

What I wanted originally was an algorithm that could create partitions of approximately k triangles (there could be some error as long it wasn't too large), and I managed to figure out a $O(k^2p^2(v+e))$ algorithm (where p is the total number of partitions) that could find such a partitioning. I then realized that having large numbers of inter-partition edges were detrimental for the application I needed this algorithm for.

Ideally, I'd like an algorithm that can keep each partition within some range of $k$, ideally have it be a constant factor like 2. Also, I'd like to be able to make the number of inter-edges have an upper bound that is "low".

Additionally, another problem I have is if I have a partition that has these properties, and I modify the graph by doing one of the following:

* Adding a set of edges connecting to existing vertices
* Adding a vertex and a set of edges connecting to the added vertex
* Removing a set of edges
* Removing a vertex and all edges that connect to this vertex

I want to be able to repartition the graph and still have each partition with size $k$ and number of cut edges minimized. (This is the solution I'm putting up a bounty for). This means that using this algorithm, we can construct any partition by starting with an empty graph and adding vertices and edges one by one and repartitioning.

Here's some additional constraints to the problem:

* The graph is planar
* Each "triangle" is a vertex that has undirected edges to triangles it shares an edge with
* From the above statement, it is obvious that each vertex in this graph has degree at most 3
* The graph is connected
* Each subgraph from the partition is connected
* Each subgraph has approximately k vertices
* There are at most $\sqrt n$ inter-partition edges (edges that contain a vertices from different partitions). If you can find a similar bound for inter-partition edges like $2\sqrt n$ or $O(\log n)$ then that could work too. I'm not entirely sure the upper bound for inter-partition edges can be less than $O(n)$ so if you can prove that its impossible to do better, that is satisfying as well.

I'm at a point where I'm stuck, so any help with this problem would be lovely. If you can flat out solve this problem, you're the bees knees. Otherwise, if you know of any papers or textbooks or algorithms you could point me to, I'd appreciate it very much.

Let me know if I need to clarify anything!

EDIT: Here are some additional constraints if it makes the problem easier.

* We are dealing with constrained delaunay triangulations
* Constraints will NEVER be a single vertex
* The graph created from the triangulation is constructed as follows: each triangle is represented as a vertex. Each edge in the graph corresponds to an unconstrained edge in the triangulation. This means that a constrained edge between two triangles will not show up in the graph representation of the triangulation.

Another thing I realized is that we may need to modify $k$ to grow as $n$ grows, otherwise there can be no sub $O(n)$ guarantees on the number of inter-partition edges.

**Tags:** graph-theory, graph-algorithms, planar-graphs, partition-problem, delaunay-triangulation
> **Comments:**
> **username_1**: It's not entirely clear what you want. Do you want a partition where each set is of roughly equal size, or one with a fixed number of sets ? I understand that in either case, you want to minimize the number of inter-set edges.  
> **username_0**: We only want the partitions to be sets of roughly equal size and within some range of k, we don't care about the total number of sets.  
> **username_1**: I see. so each partition should have roughly $k$ elements in it.  
> **username_1**: I don't have a guarantee for this heuristic, but since your graph is planar, something like a Miller hierarchy of rings might do the trick. In brief, use the planar separator theorem to split the graph into two roughly equal parts with a small number of edges between them, and recurse till all pieces are roughly of size $k$. You'll end up with a cut size close to $\sqrt{n}$.  
> **username_0**: Doesn't a planar separator not guarantee anything about the connectedness of the sets of vertices that are formed?  
> **username_0**: Also, how do you know that the cut size is close to $n^{1/2}$?  
> **username_1**: Do you care about connectedness of the sets formed ? that wasn't in the question. As for the cute size being close to $\sqrt{n}$, that follows from the planar separator theorem applied recursively.  
> **username_0**: The first line states that I want connected subgraphs. Sorry if I wasn't clear but this is a very important part of the problem  

---

## 4 answers

### Answer by username_0 on 2014-02-23. Score: 8 | Accepted answer

<http://cse.iitkgp.ac.in/~pabitra/paper/barna-sdm07.pdf>

BAM, here's the answer. Incremental min cut graph partitions in $O(k^3)$ time for insertions and deletions. If you make $k = O(\log n)$ then it's poly logarithmic for insertions and deletions, which is damn good.

> **Comments:**
> **username_2**: there were many constraints given on the problem. does this really satisfy all of them?  
> **username_0**: Yes. We can choose any size k for any step. We guarantee minimized cut-edges (inter-partition edges). We also have the ability to add and remove vertices and edges in low time complexity. That satisfies everything.  

---

### Answer by username_3 on 2014-02-23. Score: 11

Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time [seems possible](http://www.sommer.jp/planarapxq.htm). Recursive bisection, while not ideal, might be a feasible approach for your problem.

Satish Rao. [Finding near optimal separators in planar graphs](http://doi.ieeecomputersociety.org/10.1109/SFCS.1987.26). In 28th Symposium on Foundations of Computer Science (FOCS), pages 225-237, 1987.

Satish Rao. [Faster algorithms for finding small edge cuts in planar graphs](http://doi.acm.org/10.1145/129712.129735) (extended abstract). In 24th ACM Symposium on Theory of Computing (STOC), pages 229-240, 1992.

Horst D. Simon and Shang-Hua Teng. [How Good is Recursive Bisection?](http://dx.doi.org/10.1137/S1064827593255135)
In SIAM Journal on Scientific Computing, Volume 18, Issue 5, pages 1436-1445, 1997.

> **Comments:**
> **username_0**: Awesome links, I'll check them out!  

---

### Answer by username_4 on 2014-02-20. Score: 2

The following algorithm might help.
1. Choose any vertex from the graph.

2. Do a BFS untill $O(K)$ vertices has been visited.

3. Create a cluster with the visited vertices. (Connectivity is ensured for the cluster).

4. Remover the visited vertices from the graph.

5. Repeat 1-4 untill all nodes are visited.

Every cluster contains $O(K)$ vertices and those vertices are found by BFS. Again the the degree of each vertex is constant. So the inter-cluster edges are also $O(K)$. I think it's a lower bound on the number of inter-cluster edges. The complexity of the algorithm is clearly linear in number of edges as only BFS is performed. The number of cluster is also $O(N/K)$.
Also modification of the graph by adding vertices would not affect the partition. Any one partition in which one of the neighbour of the new vertex lies, that can be the partition of the new vertex. So , may be no repartition is required untill the size of one of the cluster becomes too much.
Edit:
Here is a proof that it is not possible to do better than linear number of inter-partition edge for arbitary $k$. Let in some partition there are $m$ vertices and it is connected. At best, the corresponding triangles would construct a convex region $\mathscr{R}$. Now for arbitary $k$ the convex hull of $\mathscr{R}$ can contain $O(K)$ triangle corners. So in total you would have $O(K)$ edge going out from $\mathscr{R}$. 
However if $k$ is $O(log n)$ then may be the inter-partition edges can be reduced.

> **Comments:**
> **username_5**: If you apply this to a complete graph, then there are $\Omega(N(N-K))$ inter-partition edges.  Why do you say "the inter-cluster edges are only $O(K)$"?  
> **username_1**: I think the answer refers to planar graphs. But I still don't see why "each vertex has constant degree" ? this is true "on average" but not for any vertex.  
> **username_4**: The degree of each vertex in the graph is at most 3. It is less than 3 if it is on the boundary and no outerface is considered. Hence each vertex has constant degree. @SureshVenkat  
> **username_4**: Because of the above the inter-cluster edges is $O(K)$. @AndrásSalamon  
> **username_1**: Ah you mean in the dual graph ? not the primal planar graph.  
> **username_0**: This algorithm is almost identical to the $O(k^2p^2(v+e)) $ algorithm that I had initially developed. The problem with this is that you can still have O(n) inter-partition edges which is undesirable. If every vertex in the graph has degree 3 and you imagine taking "lines" of vertices as partitions (where each vertex in the partition has only degree 1 or 2), then there are guaranteed to be $n/3$ inter-partition edges.  
> **username_0**: There might be even more degenerate cases when each each partition has the form of a tree where the root node has 3 children and the rest have 2 children. In this case there are (k-1)/2 leaves that each have 2 inter partition edges. That means we have k-1 interpartition edges for each partition, which for a graph of vertices with degree 3 gives us $(n/k)(k-1) = n-1/k$ inter-partition edges. This is only a reduction of 1/3rd of the edges which isn't very nice. However I'm not even sure if there is a way to have less than O(n) inter-partition edges so I might be being too picky.  
> **username_4**: I think in that case you need a nicer defination for the value of $k$. Some arbitary value of $k$ certainly won't work. In planar graphs number of edges is linear in number of vertices. With proper denser partition and setting the value of $k$ appropriately we may get constant number of inter partition edges. Certainly, i shall think about it.  
> **username_4**: Not sure if the edit is notified to the author of the question. So, may be there is a proof for showing that $O(N)$ edges is unavoidable.Please see in the edit. @zaloo  
> **username_0**: I understand exactly what you're saying. I believe that I'll need to have the size of $k$ to be related to $n$. I modified my OP to reflect this and to have some additional constraints as well, so I hope that helps.  

---

### Answer by username_2 on 2014-02-24. Score: -1

did some search on this but held off on posting immed to see what other answers would materialize & am now posting this to not throw away some misc ideas/leads which could have some value (although the question author has already indicated hes now found an acceptable answer).

on inspection there are many constraints given on this problem and it could conceivably take an entire paper to create an algorithm & prove that it satisfies all them (which of course is generally outside the scope of stackexchange format). nevertheless there are a few basic approaches to take on this type of problem

1. empirical. generate random graphs that fit the constraints or use graphs from some dataset that match the conditions and try different algorithms on them, and look at performance. one may find that an algorithm empirically satisfies the conditions reqd. if one is more strict, one could attempt to create a proof out of the empirical observation if its 100% satisfied by large datasets. also for empirical research it often helps to know how the datasets are obtained/generated, what their nature/origination is.
2. the question has no related citations of literature/refs. so what are the nearest types of algorithms in the literature? for this type of problem multiple types of research areas might overlap. there is research on planar graphs, graph partitions, graph cuts, graph separators, partitioning triangular graphs, etc.; its not obvious to figure out the main theme of this question so far as its formulated or which particular (graph algorithm) research sub-area would most directly impinge on it.

given those qualifications a basic theme of the question seems to be "partitioning planar graphs". here are some leading recent refs on that topic which might be helpful & show additional themes/angles of current related research. there are some algorithms implemented & they may be available on request from the authors.

the 3rd involves partitioning with weights, which will generalize to equal weights, but which gives an additional framework for consideration/investigation: could all the question conditions be fulfilled by some kind of weight assignment scheme? (this could also tie in with the requirement to have some kind of dynamic control or adjustment over solutions also referred to in the question.)

* [Spectral partitioning works: Planar graphs and finite element meshes](http://www.sciencedirect.com/science/article/pii/S0024379506003454) Spielman/Teng
* [Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases](http://link.springer.com/chapter/10.1007%2F10692760_26) Wada, Chen
* [Partitioning planar graphs with costs and weights](http://people.scs.carleton.ca/~maheshwa/papers/acmjea.pdf) Aleksandrov et al


---

