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!