Тестирование планарности
В теории графов — проверки планарности проблема это алгоритмическая проблема проверки того, является ли данный граф плоским (то есть можно ли его нарисовать на плоскости без пересечений ребер). Это хорошо изученная проблема в информатике множество практических алгоритмов , для решения которой появилось , многие из которых используют преимущества новых структур данных . Большинство этих методов работают за время O ( n ) (линейное время), где n — количество ребер (или вершин) в графе, что является асимптотически оптимальным . Вместо того, чтобы быть просто одним логическим значением, результатом алгоритма проверки планарности может быть встраивание плоского графа , если граф планарный, или препятствие для планарности, такое как подграф Куратовского, если это не так.
Критерии планарности
[ редактировать ]Алгоритмы проверки планарности обычно используют теоремы теории графов, которые характеризуют набор плоских графов в терминах, независимых от рисунков графов.К ним относятся
- Теорема Куратовского о том, что граф планарен тогда и только тогда, когда он не содержит подграфа , который является подразделением полный K 5 ( граф на пяти вершинах ) или K 3,3 ( граф полезности , полный двудольный граф на шести вершинах, три из которых соединяются друг с другом с тремя другими).
- Теорема Вагнера о том, что граф планарен тогда и только тогда, когда он не содержит минора ( подграфа сжатия) изоморфного , K 5 или K 3,3 .
- Критерий планарности Фрайссеха -Розенштиля , характеризующий плоские графы с точки зрения упорядочения ребер слева направо в дереве поиска в глубину .
Критерий планарности Фрайссейха-Розенштиля может использоваться непосредственно как часть алгоритмов проверки планарности, тогда как теоремы Куратовского и Вагнера имеют косвенное применение: если алгоритм может найти копию 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]
Ссылки
[ редактировать ]- ^ Хопкрофт, Джон ; Тарьян, Роберт Э. (1974), «Эффективное тестирование планарности», Журнал Ассоциации вычислительной техники , 21 (4): 549–568, doi : 10.1145/321850.321852 , hdl : 1813/6011 , S2CID 6279825 .
- ^ Мельхорн, Курт ; Мутцель, Петра (1996), «На этапе внедрения алгоритма проверки планарности Хопкрофта и Тарьяна» (PDF) , Algorithmica , 16 (2): 233–242, doi : 10.1007/bf01940648 , hdl : 11858/00-001M- 0000-0014-B51D-B , S2CID 10014462
- ^ Мельхорн, Курт ; Мюцель, Петра ; Нэхер, Стефан (1993), Реализация теста планарности Хопкрофта и Тарьяна и алгоритма встраивания
- ^ Мельхорн, Курт ; Нэхер, Стефан (1995), «LEDA: библиотека эффективных типов данных и алгоритмов», Communications of the ACM , 38 (1): 96–102, CiteSeerX 10.1.1.54.9556 , doi : 10.1145/204865.204889 , S2CID 2560175
- ^ Тейлор, Мартин Г. (2012). Тестирование планарности путем сложения путей (доктор философии). Кентский университет. Архивировано из оригинала 5 марта 2016 г. Альтернативный URL
- ^ Лемпель, А. ; Эвен, С .; Седербаум, И. (1967), «Алгоритм проверки планарности графов», в Розенстиле, П. (ред.), Теория графов , Нью-Йорк: Гордон и Брич, стр. 215–232 .
- ^ Даже Шимон ; Тарьян, Роберт Э. (1976), «Вычисление нумерации st », Theoretical Computer Science , 2 (3): 339–344, doi : 10.1016/0304-3975(76)90086-4 .
- ^ Бойер и Мирвольд (2004) , с. 243: «Его реализация в LEDA медленнее, чем реализации LEDA многих других алгоритмов планарности за O( n )-время».
- ^ Чиба, Н.; Нишизеки, Т. ; Абэ, А.; Озава, Т. (1985), «Линейный алгоритм внедрения плоских графов с использованием PQ-деревьев», Journal of Computer and System Sciences , 30 (1): 54–76, doi : 10.1016/0022-0000(85)90004- 2 .
- ^ Ши, ВК; Сюй, WL (1999), «Новый тест планарности», Theoretical Computer Science , 223 (1–2): 179–191, doi : 10.1016/S0304-3975(98)00120-0 .
- ^ Бойер, Джон М.; Мирволд, Венди Дж. (2004), «На острие: упрощенная планарность O( n ) путем сложения ребер» (PDF) , Journal of Graph Algorithms and Applications , 8 (3): 241–273, doi : 10.7155/jgaa .00091 .
- ^ де Фрейссе, Х.; Оссона де Мендес, П. ; Розенштиль, П. (2006), «Деревья Тремо и плоскостность», Международный журнал основ компьютерных наук , 17 (5): 1017–1030, arXiv : math/0610935 , Bibcode : 2006math.....10935D , doi : 10.1142/S0129054106004248 , S2CID 40107560 .
- ^ Брандес, Ульрик (2009), Тест на планарность слева направо (PDF) .
- ^ Бойер, Джон М.; Кортезе, ПФ; Патриньяни, М.; Баттиста, Г.Д. (2003), «Хватит думать о своих P и Q: реализация быстрого и простого алгоритма тестирования планарности и внедрения на основе DFS», Proc. 11-й Международный. Симп. Рисование графиков (GD '03) , Конспекты лекций по информатике , вып. 2912, Springer-Verlag, стр. 25–36.
- ^ Чимани, М.; Мутцель, П. ; Шмидт, Дж. М. (2008). «Эффективное извлечение нескольких подразделений Куратовского». Учеб. 15-й Международный. Симп. Рисование графика (GD'07) . Конспекты лекций по информатике. Том. 4875. Сидней, Австралия: Springer-Verlag. стр. 159–170. дои : 10.1007/978-3-540-77537-9_17 . ISBN 978-3-540-77536-2 . .
- ^ Jump up to: Перейти обратно: а б «OGDF — Открытая среда рисования графов: Начало» .
- ^ «Библиотека графов повышения: тестирование/встраивание планарности Бойера-Мирволда — 1.40.0» .
- ^ Уильямсон, С.Г. (1984), «Поиск в глубину и подграфы Куратовского», Журнал ACM , 31 (4): 681–693, doi : 10.1145/1634.322451 , S2CID 8348222
- ^ Шмидт, Йенс М. (2014), «Последовательность Мондшейна», автоматы, языки и программирование; Материалы 41-го Международного коллоквиума по автоматам, языкам и программированию (ICALP'14) , Конспекты лекций по информатике, том. 8572, стр. 967–978, номер домена : 10.1007/978-3-662-43948-7_80 , ISBN. 978-3-662-43947-0
- ^ Ла Путре, Йоханнес А. (1994), «Альфа-алгоритмы для пошагового тестирования планарности», Труды двадцать шестого ежегодного симпозиума ACM по теории вычислений (STOC) , стр. 706–715, doi : 10.1145/195058.195439 , S2CID 16799743
- ^ Ди Баттиста, Джузеппе; Тамассиа, Роберто (1996), «Онлайн-поддержание трехсвязных компонентов с помощью SPQR-деревьев», Algorithmica , 15 (4): 302–318, doi : 10.1007/BF01961541 , S2CID 7838334
- ^ Тамассиа, Роберто (1996), «Внедрение планарных графов в режиме онлайн», Journal of Algorithms , 21 (2): 201–239, doi : 10.1006/jagm.1996.0044
- ^ Уэстбрук, Джеффри (1992), «Быстрое инкрементное тестирование планарности», «Автоматы, языки и программирование», 19-й международный коллоквиум, ICALP92 , номер документа : 10.1007/3-540-55719-9_86
- ^ Патрашку, Михай ; Демейн, Эрик (2004), «Нижние границы динамической связности», Труды четырнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 546–553, doi : 10.1145/1007352.1007435 , ISBN 1581138520 , S2CID 2121130
- ^ Холм, Джейкоб; Ротенберг, Ева (2020). «Полностью динамическое тестирование планарности за полилогарифмическое время». У Макарычева Константина; Макарычев Юрий; Тулсиани, Мадхур; Камат, Гаутама; Чужой, Юлия (ред.). Материалы 52-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2020, Чикаго, Иллинойс, США, 22-26 июня 2020 г. Ассоциация вычислительной техники. стр. 167–180. arXiv : 1911.03449 . дои : 10.1145/3357713.3384249 .
- ^ Эппштейн, Дэвид; Галил, Цви; Итальяно, Джузеппе; Спенсер, Томас (1996), «Разреженность на основе сепаратора: I. проверка планарности и минимальные остовные деревья», Журнал компьютерных и системных наук , doi : 10.1006/jcss.1996.0002
- ^ Галил, Цви; Итальяно, Джузеппе; Сарнак, Нил (1999), «Полностью динамическое тестирование планарности с помощью приложений», Журнал ACM , 46 : 28–91, doi : 10.1145/300515.300517 , S2CID 7009330