stringtranslate.com

Тестирование планарности

В теории графов задача проверки планарности — это алгоритмическая задача проверки того, является ли заданный граф планарным графом (то есть, можно ли его нарисовать на плоскости без пересечений ребер). Это хорошо изученная задача в информатике , для которой появилось много практических алгоритмов , многие из которых используют преимущества новых структур данных . Большинство этих методов работают за время O ( n ) (линейное время), где n — количество ребер (или вершин) в графе, что является асимптотически оптимальным . Вместо того чтобы быть просто одним булевым значением, вывод алгоритма проверки планарности может быть вложением планарного графа , если граф планарный, или препятствием к планарности, таким как подграф Куратовского, если он не планарный.

Критерии плоскостности

Алгоритмы проверки планарности обычно используют теоремы теории графов, которые характеризуют множество планарных графов в терминах, которые не зависят от рисунков графов. К ним относятся

Критерий планарности Фрейссейкса–Розенштиля можно использовать непосредственно как часть алгоритмов проверки планарности, в то время как теоремы Куратовского и Вагнера имеют косвенные применения: если алгоритм может найти копию K 5 или K 3,3 в заданном графе, он может быть уверен, что входной граф не является планарным, и вернуться без дополнительных вычислений.

Другие критерии планарности, которые математически характеризуют планарные графы, но играют менее важную роль в алгоритмах проверки планарности, включают:

Алгоритмы

Метод сложения путей

Классический метод сложения путей Хопкрофта и Тарьяна [1] был первым опубликованным алгоритмом проверки планарности за линейное время в 1974 году. Реализация алгоритма Хопкрофта и Тарьяна представлена ​​в Библиотеке эффективных типов данных и алгоритмов Мельхорна , Мутцеля и Нэхера. [2] [3] [4] В 2012 году Тейлор [5] расширил этот алгоритм для генерации всех перестановок циклического порядка ребер для планарных вложений двусвязных компонентов.

Метод сложения вершин

Методы добавления вершин работают, поддерживая структуру данных, представляющую возможные вложения индуцированного подграфа заданного графа, и добавляя вершины по одной за раз к этой структуре данных. Эти методы начались с неэффективного метода O( n 2 ), придуманного Лемпелем , Эвеном и Седербаумом в 1967 году. [6] Он был улучшен Эвеном и Тарьяном, которые нашли линейное решение для шага нумерации s , t , [7] и Бутом и Люкером, которые разработали структуру данных дерева PQ . С этими улучшениями он является линейным по времени и превосходит метод добавления путей на практике. [8] Этот метод также был расширен, чтобы позволить эффективно вычислять планарное вложение (рисование) для планарного графа. [9] В 1999 году Ши и Сю упростили эти методы, используя дерево PC (некорневой вариант дерева PQ) и обход в обратном порядке дерева поиска в глубину вершин. [10]

Метод добавления ребра

В 2004 году Джон Бойер и Венди Мирвольд [11] разработали упрощенный алгоритм O( n ), изначально вдохновленный методом PQ-дерева, который избавляется от PQ-дерева и использует добавления ребер для вычисления планарного вложения, если это возможно. В противном случае вычисляется подразделение Куратовского (либо K 5 , либо K 3,3 ). Это один из двух современных алгоритмов на сегодняшний день (другой — алгоритм проверки планарности де Фрейссейкса, Оссоны де Мендеса и Розенштиля [12] [13] ). Экспериментальное сравнение с предварительной версией теста планарности Бойера и Мирвольда см. в [14] . Кроме того, тест Бойера–Мирвольда был расширен для извлечения нескольких подразделений Куратовского непланарного входного графа за время выполнения, линейно зависящее от размера выходных данных. [15] Исходный код для теста планарности [16] [17] и извлечения множественных подразделений Куратовского [16] находится в открытом доступе. Алгоритмы, которые находят подграф Куратовского за линейное время в вершинах, были разработаны Уильямсоном в 1980-х годах. [18]

Метод последовательности строительства

Другой метод использует индуктивное построение 3-связных графов для постепенного построения планарных вложений каждого 3-связного компонента G (и, следовательно, планарного вложения самого G ). [19] Построение начинается с K 4 и определяется таким образом, что каждый промежуточный граф на пути к полному компоненту снова является 3-связным. Поскольку такие графы имеют уникальное вложение (с точностью до переворачивания и выбора внешней грани), следующий больший граф, если он все еще планарный, должен быть уточнением предыдущего графа. Это позволяет свести тест планарности к простой проверке на каждом шаге, имеет ли следующее добавленное ребро оба конца во внешней грани текущего вложения. Хотя это концептуально очень просто (и дает линейное время выполнения), сам метод страдает от сложности нахождения последовательности построения.

Динамические алгоритмы

Тестирование планарности изучалось в модели динамических алгоритмов , в которой сохраняется ответ на проблему (в данном случае планарность), поскольку граф подвергается локальным обновлениям, как правило, в форме вставки/удаления ребер. В случае появления ребер существует асимптотически плотный алгоритм обновления времени обратной функции Аккермана , разработанный Ла Путре [20], улучшающий алгоритмы Ди Баттисты, Тамассии и Уэстбрука. [21] [22] [23] В полностью динамическом случае, когда ребра как вставляются, так и удаляются, существует логарифмическая нижняя граница времени обновления, разработанная Патраску и Демейном [24], и полилогарифмический алгоритм обновления времени, разработанный Холмом и Ротенбергом [25], улучшающий сублинейные алгоритмы обновления времени, разработанные Эппштейном , Галилом , Итальяно , Сарнаком и Спенсером. [26] [27]

Ссылки

  1. ^ Хопкрофт, Джон ; Тарьян, Роберт Э. (1974), «Эффективное тестирование планарности», Журнал Ассоциации вычислительной техники , 21 (4): 549–568, doi : 10.1145/321850.321852, hdl : 1813/6011 , S2CID  6279825.
  2. ^ Мельхорн, Курт ; Мютцель, Петра (1996), «О фазе встраивания алгоритма проверки планарности Хопкрофта и Тарьяна» (PDF) , Algorithmica , 16 (2): 233–242, doi :10.1007/bf01940648, hdl : 11858/00-001M-0000-0014-B51D-B , S2CID  10014462
  3. ^ Мельхорн, Курт ; Мютцель, Петра ; Наэр, Стефан (1993), Реализация теста планарности Хопкрофта и Тарьяна и алгоритма встраивания
  4. ^ Мельхорн, Курт ; Наэр, Стефан (1995), «LEDA: библиотека эффективных типов данных и алгоритмов», Communications of the ACM , 38 (1): 96–102, CiteSeerX 10.1.1.54.9556 , doi :10.1145/204865.204889, S2CID  2560175 
  5. ^ Тейлор, Мартин Г. (2012). Тестирование планарности путем сложения путей (Ph.D.). Университет Кента. Архивировано из оригинала 2016-03-05.Альтернативный URL-адрес
  6. ^ Лемпель, А .; Эвен, С .; Седербаум, И. (1967), «Алгоритм для проверки планарности графов», в Розенштиль, П. (ред.), Теория графов , Нью-Йорк: Гордон и Брич, стр. 215–232.
  7. ^ Even, Shimon ; Tarjan, Robert E. (1976), "Вычисление st -нумерации", Theoretical Computer Science , 2 (3): 339–344, doi : 10.1016/0304-3975(76)90086-4.
  8. ^ Бойер и Мирволд (2004), стр. 243: «Его реализация в LEDA медленнее, чем реализации LEDA многих других алгоритмов планарности с временем O( n )».
  9. ^ Чиба, Н.; Нишизеки, Т .; Абэ, А.; Озава, Т. (1985), «Линейный алгоритм встраивания планарных графов с использованием PQ-деревьев», Журнал компьютерных и системных наук , 30 (1): 54–76, doi : 10.1016/0022-0000(85)90004-2.
  10. ^ Ши, ВК; Сю, ВЛ (1999), «Новый тест на планарность», Теоретическая информатика , 223 (1–2): 179–191, doi : 10.1016/S0304-3975(98)00120-0.
  11. ^ Бойер, Джон М.; Мирволд, Венди Дж. (2004), «На переднем крае: упрощенная O(n) планарность путем добавления ребер» (PDF) , Журнал алгоритмов графов и их приложений , 8 (3): 241–273, doi : 10.7155/jgaa.00091.
  12. ^ де Фрейссе, Х.; Оссона де Мендес, П .; Розенштиль, П. (2006), «Деревья Тремо и планарность», Международный журнал основ компьютерной науки , 17 (5): 1017–1030, arXiv : math/0610935 , Bibcode : 2006math.....10935D, doi : 10.1142/S0129054106004248, S2CID  40107560.
  13. ^ Брандес, Ульрик (2009), Тест на лево-правую планарность (PDF).
  14. ^ Бойер, Джон М.; Кортезе, П. Ф.; Патриньяни, М.; Баттиста, Г. Д. (2003), «Перестаньте думать о своих P и Q: реализация быстрого и простого алгоритма тестирования планарности и встраивания на основе DFS», Proc. 11th Int. Symp. Graph Drawing (GD '03) , Lecture Notes in Computer Science , т. 2912, Springer-Verlag, стр. 25–36
  15. ^ Chimani, M.; Mutzel, P .; Schmidt, JM (2008). "Эффективное извлечение множественных подразделений Куратовского". Proc. 15th Int. Symp. Graph Drawing (GD'07) . Lecture Notes in Computer Science. Vol. 4875. Sydney, Australia: Springer-Verlag. pp. 159–170. doi :10.1007/978-3-540-77537-9_17. ISBN 978-3-540-77536-2..
  16. ^ ab "OGDF - Open Graph Drawing Framework: Начало".
  17. ^ «Библиотека Boost Graph: Тестирование/встраивание планарности Бойера-Мирволда — 1.40.0».
  18. ^ Уильямсон, СГ (1984), «Поиск в глубину и подграфы Куратовского», Журнал ACM , 31 (4): 681–693, doi : 10.1145/1634.322451 , S2CID  8348222
  19. ^ Шмидт, Йенс М. (2014), «Последовательность Мондшейна», Автоматы, языки и программирование; Труды 41-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'14) , Конспект лекций по информатике, т. 8572, стр. 967–978, doi :10.1007/978-3-662-43948-7_80, ISBN 978-3-662-43947-0
  20. ^ La Poutré, Johannes A. (1994), «Альфа-алгоритмы для инкрементального тестирования планарности», Труды Двадцать шестого ежегодного симпозиума ACM по теории вычислений (STOC) , стр. 706–715, doi :10.1145/195058.195439, S2CID  16799743
  21. ^ Ди Баттиста, Джузеппе; Тамассиа, Роберто (1996), «онлайн-обслуживание трехсвязных компонентов с помощью SPQR-деревьев», Algorithmica , 15 (4): 302–318, doi :10.1007/BF01961541, S2CID  7838334
  22. ^ Тамассиа, Роберто (1996), «Онлайн-вложение планарных графов», Журнал алгоритмов , 21 (2): 201–239, doi :10.1006/jagm.1996.0044
  23. ^ Уэстбрук, Джеффри (1992), «Быстрое инкрементальное тестирование планарности», Автоматы, языки и программирование, 19-й Международный коллоквиум, ICALP92 , doi :10.1007/3-540-55719-9_86
  24. ^ Патраску, Михай ; Демейн, Эрик (2004), «Нижние границы для динамической связности», Труды четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 546–553, doi :10.1145/1007352.1007435, ISBN 1581138520, S2CID  2121130
  25. ^ Holm, Jacob; Rotenberg, Eva (2020). «Полностью динамическое тестирование планарности за полилогарифмическое время». В Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (ред.). Труды 52-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2020, Чикаго, Иллинойс, США, 22–26 июня 2020 г. Association for Computing Machinery. стр. 167–180. arXiv : 1911.03449 . doi :10.1145/3357713.3384249.
  26. ^ Эппштейн, Дэвид; Галил, Цви; Итальяно, Джузеппе; Спенсер, Томас (1996), «Разрежение на основе сепаратора: I. Проверка планарности и минимальные остовные деревья», Журнал компьютерных и системных наук , doi : 10.1006/jcss.1996.0002
  27. ^ Галил, Цви; Итальяно, Джузеппе; Сарнак, Нил (1999), «Полностью динамическое тестирование планарности с приложениями», Журнал ACM , 46 : 28–91, doi : 10.1145/300515.300517 , S2CID  7009330