Partitioning graphs while minimizing inter-partition edges 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": 

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.
Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time seems possible. Recursive bisection, while not ideal, might be a feasible approach for your problem.

Satish Rao. Finding near optimal separators in planar graphs. 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 (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? 
In  SIAM Journal on Scientific Computing, Volume 18, Issue 5, pages 1436-1445, 1997.