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

Постановка задачи

Здесь будет рассмотрена задача поддержки динамического планарного графа, в котором выполняются операции вставки и удаления ребер, сохраняющие планарность, но способные изменить укладку. Предварительные определения перед формальной формулировкой задачи.

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

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

Полностью динамическую задачу проверки на планарность можно определить следующим образом. Необходимо поддерживать (не обязательно планарный) граф, в котором выполняются произвольные операции вставки и удаления ребер, и выполнять запросы, проверяющие, является ли граф в текущее время планарным, а также не будет ли потенциальное новое ребро нарушать его планарность.

Основные результаты

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

Теорема 1. Поддержку планарного графа со вставками и удалениями ребер, сохраняющими планарность, и выполнением запросов на проверку, не нарушает ли новое ребро планарность графа, возможно выполнить за амортизированное время [math]\displaystyle{ O(n^{1/2}) \; }[/math] на один запрос или обновление.

Если допустить использование произвольных операций вставки и удаления, даже нарушающих планарность графа, то результат можно улучшить при помощи следующего подхода. Вышеприведенная структура данных может использоваться для поддержки планарного подграфа данного графа. При попытке вставки нового ребра, в случае, если полученный граф перестанет быть планарным, алгоритм не производит вставку на деле, а добавляет ребро к списку непланарных ребер. При выполнении запроса, в случае, если список непланарных ребер непуст, алгоритм вновь пытается добавить эти ребра к планарному подграфу, по одному за раз. Время, потраченное на каждое успешное обновление, может быть отнесено на счет операции вставки, во время которой ребро было добавлено к списку непланарных ребер. Как только алгоритм находит в списке ребро, которое невозможно добавить к графу, он прекращает попытки добавления других ребер списка. Время, потраченное на это неуспешное обновление, может быть отнесено на счет выполняемого в данный момент запроса. Таким образом, список непланарных ребер будет пустым в том и только том случае, если граф является планарным; этот алгоритм может проверять планарность даже для обновлений в непланарных графах.

Теорема 2. Поддержку графа с произвольными вставками и удалениями ребер и выполнением запросов на проверку, является ли граф в текущий момент планарным и не нарушит ли новое ребро планарность, возможно выполнить за амортизированное время [math]\displaystyle{ O(n^{1/2}) \; }[/math] на один запрос или обновление.

Применение

Планарные графы – возможно, один из самых важных и интересных подклассов графов, сочетающий красоту структуры с обширностью вариантов применения в приложениях. В частности, проверка на планарность – один из базовых компонентов многих приложений, включая проектирование СБИС, графику и автоматизированное проектирование. Во всех этих приложениях приходится иметь дело с динамическими обновлениями.

Открытые вопросы

Граница [math]\displaystyle{ O(n^{1/2}) \; }[/math] для проверки на планарность является амортизированной. Можно ли улучшить эту границу или сделать ее границей для наихудшего случая?

Сложность представленных алгоритмов и большие константные сомножители, входящие в некоторые асимптотические временные границы, делают некоторые результаты непригодными для практического применения. Можно ли упростить эти методы с сохранением сходных теоретических границ?

См. также

• Динамические деревья
• Полностью динамический алгоритм нахождения кратчайших путей между всеми парами
• Полностью динамическая связность
• Полностью динамическая связность высоких степеней
• Полностью динамическая связность высоких степеней в планарных графах
• Полностью динамические минимальные остовные деревья
• Полностью динамический алгоритм транзитивного замыкания

Литература

1. Cimikowski, R.: Branch-and-bound techniques for the maximum planar subgraph problem. Int. J. Computer Math. 53, 135-147(1994)

2. Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification - a technique for speeding up dynamic graph algorithms. J. Assoc. Comput. Mach. 44(5), 669-696 (1997)

3. Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T.H.: Separator-based sparsification I: planarity testing and minimum spanning trees. J. Comput. Syst. Sci. Special issue of STOC 93 52(1), 3-27(1996)

4. Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T.H.: Separator-based sparsification II: edge and vertex connectivity. SIAM J. Comput. 28,341-381 (1999)

5. Eppstein, D., Italiano, G.F., Tamassia, R.,Tarjan, R.E., Westbrook, J., Yung, M.: Maintenance of a minimum spanning forest in a dynamic planegraph. J. Algorithms 13, 33-54 (1992)

6. Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14, 781-798(1985)

7. Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput. 26(2), 484-538 (1997)

8. Galil, Z., Italiano, G.F., Sarnak, N.: Fully dynamic planarity testing with applications. J. ACM 48, 28-91 (1999)

9. Giammarresi, D., Italiano, G.F.: Decremental 2- and 3-connectivity on planar graphs. Algorithmica 16(3):263-287 (1996)

10. Hershberger, J., Suri,M.R., Suri,S.:Data structures for two-edge connectivity in planar graphs. Theor. Comput. Sci. 130(1), 139-161 (1994)

11. Italiano, G.F., La Poutre, J.A., Rauch, M.: Fully dynamic planarity testing in planar embedded graphs. 1 st Annual European Symposium on Algorithms, Bad Honnef, Germany, 30 September-2 October 1993

12. Tamassia, R.: A dynamic data structure for planar graph embedding. 15th Int.Colloq. Automata, Languages,and Programming. LNCS, vol. 317, pp. 576-590. Springer, Berlin (1988)