Алгоритм планаризации непланарного графа
Существует ли популярный алгоритм планаризации непланарного графа.
В настоящее время я планирую реализовать алгоритм ортогональной плоской компоновки для неориентированных графов в Boost ( Boost Graph Library). BGL имеет реализацию для проверки плоскостности неориентированного графа (тестирование плоскостности Бойера-Мирволда), и я планирую использовать плоское вложение, возвращаемое этим методом, для создания ортогонального макета.
Но я не уверен, что нужно делать, если входной граф непланарный. Должен ли я что-то сделать с подграфом Куратовского, возвращенным в таком сценарии, чтобы сделать граф плоским.
Поиск Google "Планаризация неплоских графиков" возвращает несколько научных работ. Я не уверен, с чего начать.
1 ответ
Существует экспоненциально много подграфов $K_5$ и $K_{3,3}$ в $K_n$, не говоря уже о несовершеннолетних, поэтому их непосредственное лечение не очень эффективно. Я предлагаю просмотреть упомянутые исследовательские работы, чтобы узнать, как другие люди подходят к проблеме. Вы должны обратить внимание на свойства, которые (а) дают разумные решения и (б) звучат как графики, которые вас интересуют.