Я пишу алгоритм, который пытается построить планарный граф.
Я начинаю с плоского графа и должен добавить ребра между n узлами, чтобы построить n-цикл, но не нарушить планарность. Я знаю, что это можно сделать.
Моя идея состоит в том, чтобы случайным образом добавлять ребра, пока не нарушится планарность, а затем начать все сначала, пока я не найду правильный набор ребер. Для этого мне нужно было бы провести много тестов на плоскостность.
Я знаю, что лучшие алгоритмы - это O (n), поэтому мне было интересно, есть ли алгоритм, который не нужно запускать заново каждый раз, когда я добавляю ребро. Я имею в виду, если бы я просто запустил алгоритм на том же графике с одним ребром меньше, я мог бы как-то не повторить все шаги?
Я понимаю, что алгоритмы тестирования плоскостности сложно реализовать, поэтому в идеале я бы предпочел не реализовывать все это самостоятельно.