Максимум пересечений в графе

[denny]

Хорошо известна тема планарности графов.
А если поставить противоположную задачу?
Для данного графа, перемещая вершины по плоскости,
добиться наибольшего числа пересечений ребер.

Какие вообще могут быть идеи, алгоритмы?

-- 01.11.2022, 21:39 --

Тема нетривиальная. Вот, нашел нечто. Приветствуются еще идеи!
http://www2.cs.arizona.edu/~kobourov/ma ... ings17.pdf

Короче, доказано, что это NP-hard problem.
И все же интересно, если взять небольшой граф, можно как-то эвристически
подойти к максимуму?

[Aritaborian]

Расставим вершины графа в вершинах правильного многоугольника, посчитаем пересечения. Случайным образом выберем две вершины, поменяем их местами. Если этот шаг привёл к увеличению количества пересечений, повторим это действие с новой парой случайно выбранных вершин. Если не привёл, вернёмся к предыдущему состоянию и снова попытаемся сделать шаг. Повторяем до достижения удовлетворительного результата.
Вместо правильного многоугольника можно взять какое-то другое расположение.
На практике не проверял. Работы по ссылкам не читал.