Проверка планарности - Planarity testing

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

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

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

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

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

Алгоритмы

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

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

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

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

Метод сложения кромок

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

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

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

Рекомендации

  1. ^ Хопкрофт, Джон; Тарджан, Роберт Э. (1974), «Эффективное тестирование планарности», Журнал Ассоциации вычислительной техники, 21 (4): 549–568, Дои:10.1145/321850.321852, HDL:1813/6011.
  2. ^ Мельхорн, Курт; Муцель, Петра (1996), "На этапе внедрения алгоритма проверки планарности Хопкрофта и Тарьяна", Алгоритмика, 16 (2): 233–242, Дои:10.1007 / bf01940648, HDL:11858 / 00-001M-0000-0014-B51D-B
  3. ^ Мельхорн, Курт; Муцель, Петра; Нэхер, Стефан (1993), Реализация теста планарности Хопкрофта и Тарьяна и алгоритма встраивания
  4. ^ Мельхорн, Курт; Нахер, Стефан (1995), «LEDA: библиотека эффективных типов данных и алгоритмов», Коммуникации ACM, 38 (1): 96–102, CiteSeerX  10.1.1.54.9556, Дои:10.1145/204865.204889
  5. ^ Тейлор, Мартин Г. (2012). Проверка планарности добавлением пути (Кандидат наук.). Кентский университет. В архиве из оригинала от 05.03.2016. Альтернативный URL
  6. ^ Lempel, A .; Даже, S .; Седербаум, I. (1967), "Алгоритм для проверки планарности графов", в Rosenstiehl, P. (ed.), Теория графов, New York: Gordon and Breach, pp. 215–232..
  7. ^ Даже, Шимон; Тарджан, Роберт Э. (1976), "Вычисление ул-нумерация ", Теоретическая информатика, 2 (3): 339–344, Дои:10.1016/0304-3975(76)90086-4.
  8. ^ Бойер и Мирвольд (2004), п. 243: «Его реализация в LEDA медленнее, чем в реализациях LEDA многих других O (п) -временной планарности ».
  9. ^ Chiba, N .; Нишизеки, Т.; Abe, A .; Одзава, Т. (1985), "Линейный алгоритм вложения плоских графов с использованием PQ-деревьев", Журнал компьютерных и системных наук, 30 (1): 54–76, Дои:10.1016/0022-0000(85)90004-2.
  10. ^ Shih, W. K .; Сюй, В. Л. (1999), «Новый тест планарности», Теоретическая информатика, 223 (1–2): 179–191, Дои:10.1016 / S0304-3975 (98) 00120-0.
  11. ^ Boyer, John M .; Мирволд, Венди Дж. (2004), "На переднем крае: упрощенный O (п) планарность добавлением ребер " (PDF), Журнал графических алгоритмов и приложений, 8 (3): 241–273, Дои:10.7155 / jgaa.00091.
  12. ^ de Fraysseix, H .; Оссона де Мендес, П.; Розенштиль, П. (2006), «Деревья Тремо и планарность», Международный журнал основ информатики, 17 (5): 1017–1030, arXiv:математика / 0610935, Дои:10.1142 / S0129054106004248.
  13. ^ Брандес, Ульрик (2009), Тест лево-правой планарности (PDF).
  14. ^ Boyer, John M .; Cortese, P. F .; Patrignani, M .; Баттиста, Г. Д. (2003), «Перестаньте думать о ваших P и Q: реализация быстрого и простого алгоритма проверки планарности и встраивания на основе DFS», Proc. 11-й Int. Symp. Графический рисунок (GD '03), Конспект лекций по информатике, 2912, Springer-Verlag, стр. 25–36.
  15. ^ Chimani, M .; Муцель, П.; Шмидт, Дж. М. (2008), "Эффективное извлечение нескольких подразделений Куратовского", Proc. 15-й Int. Symp. Графический рисунок (GD'07), Конспект лекций по информатике, 4875, Сидней, Австралия: Springer-Verlag, стр. 159–170..
  16. ^ а б «OGDF - Open Graph Drawing Framework: начало».
  17. ^ "Библиотека графов повышения: тестирование / внедрение планарности Бойера-Мирвольда - 1.40.0".
  18. ^ Уильямсон, С. Г. (1984), "Поиск в глубину и подграфы Куратовского", Журнал ACM, 31 (4): 681–693, Дои:10.1145/1634.322451
  19. ^ Шмидт, Йенс М. (2014), Автоматы, языки и программирование, Конспект лекций по информатике, 8572, стр. 967–978, Дои:10.1007/978-3-662-43948-7_80, ISBN  978-3-662-43947-0