Для решения задачи необходимо двигать вершины графа так, чтобы рёбра не пересекались. Это можно выполнить, разместив вершины двух групп графа по разные стороны, например, одну группу слева, а другую справа. В этом случае каждое ребро соединит вершину одной группы с вершиной другой, и пересечений не возникнет.