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!

  • $\begingroup$ 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. $\endgroup$ – Chao Xu Feb 14 '14 at 20:22
  • $\begingroup$ We want the average size if each subgraph to be as close to k as possible $\endgroup$ – zaloo Feb 14 '14 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.