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.