<p>I'm currently working on my thesis which deals with pathfinding over a Delaunay triangulated graph. I want to be able to partition my Delaunay triangulation into disjoint (regarding vertices) connected subgraphs of size at most k. The graph I am working with is planar and each vertex has degree at most 3.</p>

<p>I know that graph partitioning is in general NP-hard, but I was hoping that there is some polynomial time algorithm or approximation algorithm that could solve this problem. If anyone has a reference to some paper that deals with this problem or has a solution themselves, I'd love to hear from you.</p>

<p>EDIT: If you also have an algorithm that covers the graph, rather than partition, post that as well!</p>

CC BY-SA 3.0
2014-02-14T20:22:56.130Z
Do you have any other criteria in mind? A partition where each class is one single vertex meets your criteria. I believe this is not what you are really looking for.
Chao Xu
CC BY-SA 3.0
2014-02-14T22:23:36.893Z
We want the average size if each subgraph to be as close to k as possible
zaloo
<graph-theory><graph-algorithms><planar-graphs><partition-problem><delaunay-triangulation>
Partition planar graph of vertices with at most degree 3 into connected subgraphs
zaloo
# Partition planar graph of vertices with at most degree 3 into connected subgraphs

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

I'm currently working on my thesis which deals with pathfinding over a Delaunay triangulated graph. I want to be able to partition my Delaunay triangulation into disjoint (regarding vertices) connected subgraphs of size at most k. The graph I am working with is planar and each vertex has degree at most 3.

I know that graph partitioning is in general NP-hard, but I was hoping that there is some polynomial time algorithm or approximation algorithm that could solve this problem. If anyone has a reference to some paper that deals with this problem or has a solution themselves, I'd love to hear from you.

EDIT: If you also have an algorithm that covers the graph, rather than partition, post that as well!

**Tags:** graph-theory, graph-algorithms, planar-graphs, partition-problem, delaunay-triangulation
> **Comments:**
> **username_1**: Do you have any other criteria in mind? A partition where each class is one single vertex meets your criteria. I believe this is not what you are really looking for.  
> **username_0**: We want the average size if each subgraph to be as close to k as possible  

---

## 0 answers

