Планарность графика с фиксированными позициями узлов

Question

У меня есть неориентированный граф с фиксированными позициями узлов. Узлы не могут быть перемещены, объединены, удалены или иным образом изменены. Края прикреплены к своим узлам, но не обязательно должны быть прямыми.

Мне нужно знать, можно ли "согнуть" или "нарисовать" ребра так, чтобы график был плоским (т.е. пересечения ребер нет).

Если такой алгоритм или реализация существует, или у вас есть идея, как это сделать, пожалуйста, дайте мне знать!

Answer 1

На этот вопрос отвечают "Дж. Пах и Р. Венгер. Вложение плоских графов в фиксированные местоположения вершин. Графики Комбин., 17:717–728, 2001" как:

Каждый планарный граф на n вершинах допускает плоское вложение, которое отображает каждую вершину в заранее определенное отдельное местоположение, а каждое ребро - в многоугольную кривую с O(n) изгибами.
Такое вложение может быть построено за O(n^2) времени.

Таким образом, ответ заключается в том, что вы можете построить такой граф тогда и только тогда, когда он плоский. Вы можете проверить, является ли график плоским за O(n) время согласно википедии.