How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts? I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring nodes have. I would like to run this algorithm in parallel in the public cloud. Unfortunately, I cannot find a way to split my graph for maximum computation efficiency. All of my workers end up hitting the network to access neighbouring nodes. I need a way to split my graph to minimise network I/O between workers.

Ideally I want to split my graph into (approximately) balanced parts and minimize the number of edges crossing the parts.

I thought that ordering all nodes in some kind of 'locality-preserving' order is an option since I might not know upfront how many workers I have.
One natural thing would be to try a separator kind of trick. If the Voronoi cells are fat, and of similar size then a randomly shifted grid of the right side would do reasonably well. in particular, there is a paper by Miller and Thurston (and some other people - their names escape me) about finding a separator if you have fat regions covering space, and every point is covered only a constant number of times. It is essentially an extension of their proof of the existence of a planar separator to these more general settings.