Проверка на планарность
Ключевые слова и синонимы
Планарное вложение
Постановка задачи
Задача заключается в установлении факта, является ли входной граф G планарным. Определение, наиболее подходящее для алгоритмов проверки на планарность, звучит так: граф G является планарным, если существует его вложение в плоскость (вершины G отображаются на различные точки, ребра G отображаются на кривые, соединяющие соответствующие конечные точки), такое, что ребра графа не пересекаются. Алгоритмы, проводящие проверку графа на планарность, можно модифицировать для получения подобного вложения.
Основные результаты
Теорема 1. Существует алгоритм, который для данного графа с n вершинами определяет, является ли он планарным, за время O(n).
Первый алгоритм с линейным временем выполнения предложили Хопкрофт и Тарьян [5], проанализировав итеративную версию рекурсивного алгоритма, разработанного Ауслендером и Партером [1] и модифицированного Голдштейном [4]. Алгоритм основывается на следующем наблюдении: связный граф является планарным в том и только том случае, если все его двусвязные компоненты являются планарными. Рекурсивный алгоритм последовательно обрабатывает каждую двусвязную компоненту: найти разделяющий цикл (separating cycle) C и разбиение ребер G, не принадлежащих C; определить компоненту разбиения как состоящую из ребер, связанных путем в G, и не включающую ребер из C; рекурсивно рассмотреть каждую циклическую компоненту разбиения. Если каждая компонента разбиения является планарной, а все компоненты могут быть объединены с C в планарный граф, то граф G является планарным.
Другой метод определения планарности предложили Лемпел, Ивен и Седербаум [6]. Алгоритм начинает работу с вложения единичной вершины и ребер, смежных с этой вершиной; затем он рассматривает вершину, смежную с одним из этих ребер. Для корректности работы алгоритма вершины следует рассматривать в определенном порядке. Алгоритм был впервые реализован за время O(n) Бутом и Люкером [2], использовавшими эффективную реализацию структуры данных PQ-деревьев. Более простые реализации этого алгоритма предложили Бойер и Мирволд [3], а также Ши и Хсу [8].
Тутте предложил алгебраический метод прямолинейного вложения графа, который в случае, когда граф является трехсвязным и планарным, гарантирует построение планарного вложения. Основная идея заключается в следующем: вершины одной грани графа фиксируются, становясь углами выпуклого многогранника, а затем производится вложение всех остальных вершин как геометрического среднего их соседей.
Применение
Проверка на планарность применяется в таких областях, как автоматизированное проектирование и проектирование СБИС, позволяя определить, может ли данная сеть быть реализована на плоскости.
Ссылка на код
Библиотека LEDA предлагает эффективную реализацию алгоритма Хопкрофта и Тарьяна [7]: http://www.algorithmic-solutions.info/leda_guide/graph_algorithms/planar_kuratowski.html
== См. также
Литература
1. Auslander, L., Parter, S.V.: On imbedding graphs in the plane. J. Math. and Mech. 10, pp. 517-523 (1961)
2. Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comp. Syst. Sci. 13, pp. 335-379 (1976)
3. Boyer, J., Myrvold, W.: Stop minding your P's and Q's: A simplified O(n) planar embedding algorithm. In: SODA '99: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 140-146 (1999)
4. Goldstein, A.J.: An efficient and constructive algorithm for testing whether a graph can be embedded in the plane. In: Graph and Combinatorics Conf. (1963)
5. Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21, pp. 549-568(1974)
6. Lempel, A., Even, S., Cederbaum, I.: An algorithm for planarity testing of graphs. In: Rosentiehl, P. (ed.) Theory of Graphs: International Symposium. New York, Gordon and Breach, pp. 215-232(1967)
7. Mehlhorn, K., Mutzel, P., Naher, S.: An implementation of the hopcroft and tarjan planarity test. Tech. Rep. MPI-I-93-151, SaarbrCicken(1993)
8. Shih, W.-K., Hsu, W.-L.: A new planarity test. Theor. Comput. Sci. 223, pp. 179-191 (1999)