декомпозиция графа

Добрый день!

необходимо решить задачу декомпозиции графа

Есть плоскость и множество точек на ней. Заданы координаты вершин, тип для каждой вершины, связи между вершинами(ребра). Необходимо разбить эту плоскость на k (вводит пользователь, + проверка, что k меньше количества исходных вершин) непересекающихся областей (подграфов) таким образом, чтобы было минимальное сечение "сжатого" графа (то есть количество внешних связей (ребер) между k подграфами должно быть как можно меньше(если представить, что подграф - это вершина)). + условие, что есть несколько типов вершин и в каждый подграф должно входить хотя бы по одной вершине каждого вида

Пример декомпозиции на два подграфа в приложении (как выглядит граф до и после для наглядности). В сжатом графе G2 - E1 и E2 - внешние связи - количество таких связей должно стремиться к минимуму при декомпозиции.

Можно использовать какой то эвристический алгоритм, генетический или итерационный. Может что то иное - предложения рассмотрю

Желательна визуализация.

Спасибо!