Полностью динамическая проверка на планарность: различия между версиями

Граф является планарным, если он может быть уложен на плоскости без пересечения дуг. В динамической структуре планарный граф, связанный с конкретной укладкой, называется плоским; общий термин «планарный граф» используется только в случае, если разрешено изменение укладки. Вставка ребер, сохраняющая укладку, называется вставкой с сохранением укладки; если она сохраняет планарность графа, она называется сохраняющей планарность – укладка при этом, возможно, меняется; если же неизвестно, сохраняется ли при вставке ребра планарность, такая вставка называется произвольной. Обширные исследования динамических графовых алгоритмов применяли специализированные техники для решения множества задач – таких как нахождение минимальных остовных лесов, 2-реберная связность и проверка на планарность для плоских графов (с операциями вставки, сохраняющими укладку) [5, 6, 7, 9, 10, 11, 12]. В данном случае будут рассматриваться обновления более общего вида с сохранением планарности.

Галил и коллеги [], а также Эппстайн и коллеги [3] предложили общий метод решения динамических задач на планарных графах, включая вышеприведенные: во всех этих задачах могут иметь место как произвольные вставки, так и вставки с сохранением планарности, что означает допустимость изменений укладки.