Планаризация
В математической области графов теории планаризация — это метод расширения методов рисования графов с плоских графов на неплоские графы путем встраивания неплоских графов в более крупный планарный граф. [1] [2]
Планаризацию можно выполнить, используя любой метод поиска рисунка (с пересечениями) для данного графа, а затем заменив каждую точку пересечения новой искусственной вершиной , в результате чего каждое пересекаемое ребро будет подразделяться на путь . Исходный граф будет представлен как минор погружения его планаризации.
При инкрементной планаризации процесс планаризации делится на два этапа. большой планарный подграф Сначала внутри данного графа находится . Затем оставшиеся ребра, которые еще не являются частью этого подграфа, добавляются обратно по одному и направляются через встраивание плоского подграфа. Когда одно из этих ребер пересекает уже встроенное ребро, два пересекающихся ребра заменяются путями с двумя ребрами с новой искусственной вершиной, которая представляет точку пересечения, расположенную в середине обоих путей. [1] [2] В некоторых случаях к процессу планаризации добавляется третий этап локальной оптимизации , на котором ребра со многими пересечениями удаляются и добавляются заново в попытке улучшить планаризацию. [1]
Нахождение самого большого планарного подграфа
[ редактировать ]Использование инкрементальной планаризации для рисования графов наиболее эффективно, когда на первом этапе процесса находится как можно больший планарный граф. К сожалению, нахождение плоского подграфа с максимально возможным числом ребер ( о максимальном плоском подграфе задача [3] ) является NP-hard и MaxSNP-hard , подразумевая, что, вероятно, не существует алгоритма с полиномиальным временем , который точно решает задачу или аппроксимирует ее сколь угодно хорошо. [4]
В с n -вершинами связном графе наибольший планарный подграф имеет не более 3n -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]
Ссылки
[ редактировать ]- ^ Jump up to: а б с д и ж г час я Буххайм, Кристоф; Чимани, Маркус; Гутвенгер, Карстен; Юнгер, Майкл; Мутцель, Петра (2014), «Пересечения и планаризация», Тамассия, Роберто (ред.), Справочник по рисованию и визуализации графиков , Дискретная математика и ее приложения (Бока-Ратон), CRC Press, Бока-Ратон, Флорида .
- ^ Jump up to: а б с д Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберт ; Толлис, Иоаннис Г. (1998), Рисование графиков: алгоритмы визуализации графиков (1-е изд.), Prentice Hall, стр. стр. 215–218, ISBN. 0133016153 .
- ^ Jump up to: а б Чимани, Маркус (2008), Вычисление чисел пересечений (PDF) , доктор философии. диссертация, Технический университет Дортмунда , раздел 4.3.1, заархивировано из оригинала (PDF) 16 ноября 2015 г.
- ^ Jump up to: а б Кэлинеску, Груя; Фернандес, Кристина Г.; Финклер, Ульрих; Карлофф, Ховард (1998), «Алгоритм лучшего приближения для поиска плоских подграфов», Journal of Algorithms , 27 (2): 269–302, CiteSeerX 10.1.1.37.4317 , doi : 10.1006/jagm.1997.0920 , MR 1622397 , S2CID 8329680 .
- ^ Каварабаяси, Кеничи ; Рид, Брюс (2007), «Вычисление числа пересечений в линейном времени», Труды тридцать девятого ежегодного симпозиума ACM по теории вычислений (STOC '07) , стр. 382–390, doi : 10.1145/1250790.1250848 , MR 2402463 , S2CID 13000831 .
- ^ Юнгер, М.; Мутцель, П. (1996), «Максимально плоские подграфы и хорошие вложения: практические инструменты компоновки» (PDF) , Algorithmica , 16 (1): 33–59, doi : 10.1007/s004539900036 , MR 1394493 .
- ^ Вайсштейн, Эрик В. «Асимметрия графика» . Математический мир .
- ^ Каварабаяши, Кен-ичи (2009), «Планарность, допускающая небольшое количество ошибочных вершин в линейном времени», 50-й ежегодный симпозиум IEEE по основам информатики (FOCS '09) (PDF) , стр. 639–648, doi : 10.1109/FOCS. 2009.45 , МР 2648441 , S2CID 11647021 .
- ^ Эдвардс, Кейт; Фарр, Грэм (2002), «Алгоритм поиска больших индуцированных плоских подграфов», Рисование графиков: 9-й Международный симпозиум, GD 2001, Вена, Австрия, 23–26 сентября 2001 г., Пересмотренные статьи , Конспекты лекций в Comp. наук., вып. 2265, Springer, стр. 75–80, номер документа : 10.1007/3-540-45848-4_6 , MR 1962420 .
- ^ Гутвенгер, Карстен; Мюцель, Петра ; Вейскирхер, Рене (2005), «Вставка ребра в плоский граф», Algorithmica , 41 (4): 289–308, doi : 10.1007/s00453-004-1128-8 , MR 2122529 , S2CID 6441726 .