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

Алгоритмическая проблема проверки того, является ли данный граф плоским графом

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

• 1 Критерии планарности
• 2 Алгоритмы
  • 2.1 Метод сложения путей
  • 2.2 Метод сложения вершин
  • 2.3 Метод сложения ребер
  • 2.4 Метод последовательности построения
• 3 Ссылки

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

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

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

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

• критерий планарности Уитни, согласно которому граф является плоским тогда и только тогда, когда его графический матроид также является кографическим,
• критерий планарности Мак Лейна, характеризующий планарные графы по основаниям их пространств циклов,
• Теорема Шнайдера, характеризующая планарные графы с помощью размерности порядка связанного частичного порядка и
• критерия планарности Колина де Вердьера с использованием теории спектральных графов.

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

Классический метод сложения путей Hopcroft и Tarjan был первым опубликованным алгоритмом линейно-временной планарности в 1974 году. Реализация Hopcroft и Tarjan Алгоритм представлен в Библиотеке эффективных типов данных и алгоритмов авторами Mehlhorn, Mutzel и. В 2012 году Тейлор расширил этот алгоритм, чтобы сгенерировать все перестановки циклического порядка ребер для планарных вложений двусвязных компонентов.

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

Методы сложения вершин работают, поддерживая структуру данных, представляющую возможные вложения индуцированного подграфа данного графа, и добавляя вершины по одной за раз в эту структуру данных. Эти методы начались с неэффективного метода O (n), разработанного Лемпелем, Эвеном и Седербаумом в 1967 году. Он был улучшен Эвеном и Тарьяном, которые нашли решение линейного времени для s, шаг t-нумерации, а также автор и, который разработал структуру данных PQ tree. Благодаря этим усовершенствованиям он является линейным по времени и на практике превосходит метод сложения путей. Этот метод также был расширен, чтобы позволить эффективно вычислять планарное вложение (рисование) для плоского графа. В 1999 году Ши и Хсу упростили эти методы, используя дерево ПК (некорневой вариант дерева PQ) и обход после порядка дерева поиска в глубину вершин.

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

В 2004 году Джон Бойер и Венди Мирволд разработали упрощенный алгоритм O (n), первоначально вдохновленный методом дерева PQ, который избавляется от PQ tree и, если возможно, использует добавление ребер для вычисления планарного вложения. В противном случае вычисляется подразделение по Куратовски (либо K 5, либо K 3,3). Это один из двух современных алгоритмов на сегодняшний день (другой - алгоритм проверки планарности де Фрейссе, де Мендеса и Розенштиля). См. Экспериментальное сравнение с предварительной версией теста планарности Бойера и Мирволда. Кроме того, тест Бойера – Мирвольда был расширен для извлечения нескольких подразделений Куратовски из неплоского входного графа за время выполнения, линейно зависящее от размера выходных данных. Исходный код для теста планарности и извлечения нескольких подразделений Куратовского находится в открытом доступе. Алгоритмы, которые определяют местонахождение подграфа Куратовского в линейном времени в вершинах, были разработаны Уильямсоном в 1980-х.

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

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