В математической области теории графов планаризация — это метод расширения методов рисования графов с планарных графов на графы, которые не являются планарными, путем встраивания непланарных графов в более крупный планарный граф. [1] [2]
Планаризация может быть выполнена с использованием любого метода для нахождения рисунка (с пересечениями) для данного графа, а затем замены каждой точки пересечения новой искусственной вершиной , в результате чего каждое пересеченное ребро будет подразделено на путь . Исходный граф будет представлен как минор погружения его планаризации.
В инкрементальной планаризации процесс планаризации делится на два этапа. Сначала в заданном графе находится большой планарный подграф . Затем оставшиеся ребра, которые еще не являются частью этого подграфа, добавляются обратно по одному и направляются через вложение планарного подграфа. Когда одно из этих ребер пересекает уже вложенное ребро, два пересекающихся ребра заменяются двухреберными путями с новой искусственной вершиной, которая представляет точку пересечения, помещенной в середину обоих путей. [1] [2] В некоторых случаях к процессу планаризации добавляется третий локальный этап оптимизации, в котором ребра со многими пересечениями удаляются и добавляются заново в попытке улучшить планаризацию. [1]
Использование инкрементальной планаризации для рисования графа наиболее эффективно, когда первый шаг процесса находит максимально большой планарный граф. К сожалению, нахождение планарного подграфа с максимально возможным числом ребер ( задача максимального планарного подграфа [3] ) является NP-трудной и MaxSNP-трудной , что подразумевает, что, вероятно, не существует алгоритма с полиномиальным временем , который решает задачу точно или аппроксимирует ее произвольно хорошо. [4]
В связном графе с n вершинами наибольший планарный подграф имеет не более 3 n − 6 ребер, а любое остовное дерево образует планарный подграф с n − 1 ребром. Таким образом, легко аппроксимировать максимальный планарный подграф с коэффициентом аппроксимации в одну треть, просто найдя остовное дерево. Известно лучшее коэффициент аппроксимации, 9/4, основанное на методе нахождения большого частичного 2-дерева как подграфа данного графа. [1] [4] В качестве альтернативы, если ожидается, что планарный подграф будет включать почти все ребра данного графа, оставляя только небольшое число k непланарных ребер для процесса инкрементальной планаризации, то можно решить задачу точно, используя фиксированный параметрический трактуемый алгоритм, время выполнения которого линейно зависит от размера графа, но не является полиномиальным от параметра k . [5] Задача также может быть решена точно с помощью алгоритма ветвления и разрезания , без гарантий на время выполнения, но с хорошей производительностью на практике. [1] [6] Этот параметр k известен как асимметрия графика. [3] [7]
Также были некоторые исследования связанной проблемы, поиска наибольшего планарного индуцированного подграфа заданного графа. Опять же, это NP-трудная, но решаемая с фиксированными параметрами задача, когда все, кроме нескольких вершин, принадлежат индуцированному подграфу. [8] Эдвардс и Фарр (2002) доказали точную границу 3 n /(Δ + 1) для размера наибольшего планарного индуцированного подграфа как функцию n , числа вершин в заданном графе, и Δ , его максимальной степени ; их доказательство приводит к полиномиальному алгоритму для поиска индуцированного подграфа этого размера. [9]
После того, как найден большой планарный подграф, процесс инкрементальной планаризации продолжается, рассматривая оставшиеся ребра по одному. По мере этого он поддерживает планаризацию подграфа, образованного уже рассмотренными ребрами. Он добавляет каждое новое ребро к планарному вложению этого подграфа, формируя рисунок с пересечениями, а затем заменяет каждую точку пересечения новой искусственной вершиной, разделяющей два пересекающихся ребра. [1] [2] В некоторых версиях этой процедуры порядок добавления ребер произволен, но также возможно выбрать порядок, чтобы он был случайной перестановкой , запуская один и тот же алгоритм несколько раз и возвращая лучшую найденную планаризацию. [1]
В простейшей форме этого процесса планарное вложение планарного подграфа не может изменяться при добавлении новых ребер. Чтобы добавить каждое новое ребро таким образом, чтобы минимизировать количество образуемых им пересечений, можно использовать алгоритм кратчайшего пути в двойственном графе текущего вложения, чтобы найти кратчайшую последовательность граней вложения и пересекаемых ребер, соединяющую конечные точки нового ребра друг с другом. Этот процесс занимает полиномиальное время на ребро. [2]
Фиксация вложения планарного подграфа не обязательно оптимальна с точки зрения количества пересечений, которые получаются. Фактически, существуют графы, которые формируются путем добавления одного ребра к планарному подграфу, где оптимальный рисунок имеет только два пересечения, но где фиксация планарного вложения подграфа заставляет создавать линейное количество пересечений. [1] В качестве компромисса между поиском оптимальной планаризации планарного подграфа плюс одно ребро и сохранением фиксированного вложения, можно выполнить поиск по всем вложениям планарного подграфа и найти то, которое минимизирует количество пересечений, образованных новым ребром. [1] [10]