Partitioning connected graphs in the plane
This is not a full answer to your question, but at least you'll have something working.

Step 1. Calculate minimal bounding axis-aligned boxes for each connected component, and also a minimal "outer" bounding box for all the components.

Step 2. Try to split the outer bounding box by horizontal or vertical segment in such a way that this segment doesn't intersect with any bounding boxes for components - this can be done by analyzing coordinates of bounding boxes only. If that is not possible then split the outer box in halves horizontally or vertically. After splitting recalculate bounding boxes for components which were split as well.

Step 3. Repeat the Step 2 recursively for each box, which contains more than one component.

Step 4. After the Step 3 you'll have a partition of the original outer box into rectangles, each of which contain only one connected component (or part of it). Remove all the edges in this partition, for which both adjacent rectangles contain the same component. After this step you'll have a partition of the outer box, but it won't be a optimal one, and it'll consist of axis-aligned segments only.

Step 5. Amend the partition, replacing axis-aligned segments by arbitrary segments, trying to minimize the total number of segments - I don't know how to do that regularly for now.