У меня неориентированный граф с фиксированными положениями узлов. Узлы нельзя перемещать, объединять, удалять или иным образом изменять. Края прикреплены к своим узлам, но не обязательно должны быть прямыми.
Мне нужно знать, можно ли «согнуть» или «нарисовать» ребра так, чтобы граф был плоским (т. е. ребра не пересекались).
Если такой алгоритм или реализация существует, или вы просто знаете, как это сделать, дайте мне знать!
На этот вопрос отвечает Дж. Пах и Р. Венгер. Встраивание плоских графов в фиксированные местоположения вершин . Graphs Combin., 17: 717–728, 2001 " как:
Каждый планарный граф на n вершинах допускает планарное вложение, которое отображает каждую вершину в заранее заданное отдельное место, а каждое ребро - в ломаную кривую с O (n) изгибами.
Такое вложение может быть построено за O (n ^ 2) времени .
Итак, ответ таков: вы можете построить такой граф тогда и только тогда, когда он плоский. Вы можете проверить, является ли график планарным за время O (n), согласно wikipedia.
