В теории графов , то плоскостность тестирования проблемы является алгоритмической задачей проверки , является ли данный графом является плоским графом (то есть, может ли он быть обращен на плоскости без пересечений ребер). Это хорошо изученная проблема в информатике, для решения которой появилось много практических алгоритмов , многие из которых используют преимущества новых структур данных . Большинство этих методов работают за O ( n ) время (линейное время), где n - количество ребер (или вершин) в графе, что является асимптотически оптимальным.. Результатом алгоритма проверки планарности может быть не просто одно логическое значение, а вложение плоского графа , если граф плоский, или препятствие для планарности, такое как подграф Куратовского, если это не так.
Критерии планарности
Алгоритмы проверки планарности обычно используют преимущества теорем теории графов, которые характеризуют набор плоских графов в терминах, не зависящих от рисунков графов. Это включает
- Теорема Куратовская , что граф является планарным тогда и только тогда , когда он не содержит подграф , который является подразделением из K 5 (далее полный граф на пять вершин ) или K 3,3 (в полезность граф , A полного двудольного графом на шесть вершин, три из которых подключаются к каждой из трех других).
- Теорема Вагнера , что граф является планарным тогда и только тогда , когда он не содержит минор (подграф сжатия), которое изоморфно на K 5 или K 3,3 .
- Критерий плоскостности Fraysseix-Rosenstiehl , характеризующая планарные графы с точки зрения упорядочения лево-правой краев в глубину первого поиска дерева.
Критерий планарности Фрейссекса – Розенштиля может использоваться непосредственно как часть алгоритмов для проверки планарности, в то время как теоремы Куратовского и Вагнера имеют косвенное применение: если алгоритм может найти копию K 5 или K 3,3 внутри данного графа, он может быть убедитесь, что входной граф не плоский, и вернитесь без дополнительных вычислений.
Другие критерии планарности, которые математически характеризуют планарные графы, но менее важны для алгоритмов проверки планарности, включают:
- Критерий планарности Уитни, согласно которому граф является плоским тогда и только тогда, когда его графический матроид также является копографическим,
- Критерий планарности Мак Лейна, характеризующий плоские графы базисами их пространств циклов ,
- Теорема Шнайдера, характеризующая планарные графы порядковой размерностью ассоциированного частичного порядка , и
- Критерий планарности Колина де Вердьера с использованием спектральной теории графов .
Алгоритмы
Метод добавления пути
Классическое дополнение пути метод Hopcroft и Tarjan [1] был первым опубликован линейным алгоритм времени испытания плоскостности в 1974 г. Реализации Hopcroft и Тарьян алгоритма «ы предоставляется в библиотеке эффективных типов данных и алгоритмах с помощью Mehlhorn , Mutzel и Нэхер [2] [3] . [4] В 2012 году Тейлор [5] расширил этот алгоритм, чтобы сгенерировать все перестановки циклического порядка ребер для плоских вложений двусвязных компонентов.
Метод сложения вершин
Методы сложения вершин работают, поддерживая структуру данных, представляющую возможные вложения индуцированного подграфа данного графа, и добавляя вершины по одной в эту структуру данных. Эти методы стали с неэффективным O ( п 2 ) методом задуманного Лемпеля , Даже и Цедербаумом в 1967 году [6] Это было улучшен даже и Тарьян, которые нашли линейное время решения для х , т шаг -numbering, [ 7] и Бутом и Люкером , которые разработали структуру данных дерева PQ . Благодаря этим улучшениям он является линейным по времени и на практике превосходит метод сложения путей. [8] Этот метод был также расширен, чтобы позволить эффективно вычислять планарное вложение (рисование) для плоского графа. [9] В 1999 году Ши и Хсу упростили эти методы, используя дерево ПК (неуправляемый вариант дерева 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-связным. Поскольку такие графы имеют уникальное вложение (вплоть до переворачивания и выбора внешней грани), следующий более крупный граф, если он все еще плоский, должен быть уточнением предыдущего графа. Это позволяет сократить тест на плоскостность до простого тестирования для каждого шага, имеет ли следующее добавленное ребро оба конца на внешней грани текущего внедрения. Хотя это концептуально очень просто (и дает линейное время работы), сам метод страдает от сложности нахождения последовательности построения.
Рекомендации
- ^ Хопкрофт, Джон ; Тарьян, Роберт Е. (1974), "Эффективное тестирование плоскостности", журнал Ассоциации по вычислительной технике , 21 (4): 549-568, DOI : 10,1145 / 321850,321852 , ЛВП : 1813/6011.
- ^ Мельхорн, Курт; Mutzel, Петра (1996), "О вложении фазы в Hopcroft и Тарьян плоскостности тестирования алгоритма", Algorithmica , 16 (2): 233-242, DOI : 10.1007 / bf01940648 , ЛВП : 11858 / 00-001M-0000-0014 -B51D-B
- ^ Мельхорн, Курт; Муцель, Петра; Нэхер, Стефан (1993), Реализация теста планарности Хопкрофта и Тарьяна и алгоритма встраивания
- ^ Мельхорн, Курт; Naher, Стефан (1995), "ЛЕД: Библиотека эффективных типов данных и алгоритмов", коммуникации ACM , 38 (1): 96-102, CiteSeerX 10.1.1.54.9556 , DOI : 10,1145 / 204865,204889
- ^ Тейлор, Мартин Г. (2012). Проверка планарности путем сложения пути (доктор философии). Кентский университет. Архивировано 5 марта 2016 года. Альтернативный URL
- ^ Lempel, A .; Даже, S .; Седербаум, I. (1967), «Алгоритм для проверки планарности графов», в Rosenstiehl, P. (ed.), Theory of Graphs , New York: Gordon and Breach, pp. 215–232..
- ^ Даже, Шимон; Тарьян, Роберт Е. (1976), "вычисления ул -numbering", Теоретическая информатика , 2 (3): 339-344, DOI : 10,1016 / 0304-3975 (76) 90086-4.
- ↑ Boyer & Myrvold (2004) , стр. 243: «Его реализация в LEDA медленнее, чем реализация в LEDA многих другихалгоритмов планарности за времяO ( n )».
- ^ Chiba, N .; Нишизеки, Т .; Abe, A .; Одзава, Т. (1985), "Линейный алгоритм для встраивания плоских графов с использованием PQ-деревьев", журнал компьютерных и системных наук , 30 (1): 54-76, DOI : 10.1016 / 0022-0000 (85) 90004- 2.
- ^ Shih, WK; Хсу, WL (1999), "Новый тест плоскостность", Теоретическая информатика , 223 (1-2): 179-191, DOI : 10.1016 / S0304-3975 (98) 00120-0.
- ^ Boyer, John M .; Мирволд, Венди Дж. (2004), «На переднем крае: упрощенная планарность O ( n ) путем сложения ребер» (PDF) , Журнал алгоритмов и приложений графов , 8 (3): 241–273, doi : 10.7155 / jgaa .00091.
- ^ de Fraysseix, H .; Оссона де Мендес, П .; Розенштиль, П. (2006), «Деревья Тремо и планарность», Международный журнал основ компьютерных наук , 17 (5): 1017–1030, arXiv : math / 0610935 , doi : 10.1142 / S0129054106004248.
- ^ Брандес, Ульрик (2009), Тест лево-правой планарности (PDF).
- ^ Boyer, John M .; Кортезе, П.Ф .; Patrignani, M .; Battista, GD (2003), "Перестаньте думать о ваших P и Q: реализация быстрого и простого алгоритма проверки планарности и внедрения DFS", Proc. 11-е межд. Symp. Graph Drawing (GD '03) , Lecture Notes in Computer Science , 2912 , Springer-Verlag, стр. 25–36.
- ^ Chimani, M .; Mutzel, P .; Шмидт, JM (2008), "Эффективное извлечение нескольких подразделений Куратовски", Proc. 15-й Int. Symp. Graph Drawing (GD'07) , Lecture Notes in Computer Science, 4875 , Sydney, Australia: Springer-Verlag, стр. 159–170..
- ^ а б «OGDF - Open Graph Drawing Framework: Начало» .
- ^ "Библиотека графов ускорения: Тестирование / внедрение планарности Бойера-Мирвольда - 1.40.0" .
- ^ Williamson, SG (1984), "Глубина Первый поиск и Kuratowski подграфы", Журнал ACM , 31 (4): 681-693, DOI : 10,1145 / +1634,322451
- ^ Шмидт, Jens M. (2014), Автоматы Языки и программирование , Lecture Notes в области компьютерных наук, 8572 , стр 967-978,. DOI : 10.1007 / 978-3-662-43948-7_80 , ISBN 978-3-662-43947-0