# Partitioning connected graphs in the plane

This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes.

How can we divide the plane using line segments in such a way that each subdivision contains exactly one connected component?

I was thinking of generating a voronoi diagram using the endpoints, but this presents some issues:

1. Long edges are not guaranteed to be in the correct partition.
2. The border becomes very complex (There is a separate line segment for most points)

Is there an algorithm that creates less complex borders?

The input would be a planar graph with multiple connected components, where each node has coordinates associated to it.

The output would be a subdivision for the bounding box given by the graph, which divides the plane using line segments.

Example solution using red lines I'm looking to minimize the amount of line segments required, but optimality is not required.

• Thanks for the helpful edits! It sounds like your problem can be reduced to: given two sets of points $A,B$, find a path with the minimum number of line segments that puts all of $A$ on one side and all of $B$ on the other side. If you can solve that, you can use that to solve your problem, by applying it $n-1$ times, where $n$ is the number of connected components. – D.W. Mar 15 at 23:18
• I think that's a good approach. Do you know of a specific algorithm? – b9s Mar 16 at 12:40