Планаризация - Planarization - Wikipedia

В рисунок графика, планаризация это метод расширения методов рисования из планарные графы в графы, которые не являются планарными, путем вложения неплоских графов в более крупный планарный граф.[1][2]

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

В добавочная планаризация, процесс планаризации разбивается на два этапа. Во-первых, большой плоский подграф находится внутри данного графа. Затем оставшиеся ребра, которые еще не являются частью этого подграфа, добавляются по одному и маршрутизируются через вложение плоского подграфа. Когда одно из этих ребер пересекает уже внедренное ребро, два пересекающихся ребра заменяются двухреберными путями с новой искусственной вершиной, которая представляет точку пересечения, размещенную в середине обоих путей.[1][2] В некоторых случаях третий локальная оптимизация этап добавляется к процессу выравнивания, в котором ребра с множеством пересечений удаляются и добавляются повторно в попытке улучшить выравнивание.[1]

Нахождение наибольшего плоского подграфа

Использование инкрементальной планаризации для рисования графиков наиболее эффективно, когда на первом этапе процесса обнаруживается как можно больший планарный граф. К сожалению, нахождение плоского подграфа с максимально возможным количеством ребер ( максимальный плоский подграф проблема[3]) является NP-жесткий, и MaxSNP-жесткий, подразумевая, что вероятно не существует полиномиальное время алгоритм, который точно решает проблему или произвольно хорошо ее приближает.[4]

В п-вертекс связный граф, самый большой плоский подграф имеет не более 3п - 6 граней и любые остовное дерево образует плоский подграф с п - 1 ребро. Таким образом, можно легко аппроксимировать максимальный плоский подграф в пределах коэффициент аппроксимации одной трети, просто найдя остовное дерево. Известен лучший коэффициент аппроксимации 9/4, основанный на методе нахождения большого частичное 2-дерево как подграф данного графа.[1][4] В качестве альтернативы, если ожидается, что плоский подграф будет включать почти все ребра данного графа, оставив лишь небольшое количество k неплоских кромок для процесса постепенной планаризации, то можно решить проблему точно, используя управляемый с фиксированными параметрами алгоритм, время работы которого линейно по размеру графа, но неполиномиально по параметруk.[5] Проблема также может быть решена точно разделить и разрезать алгоритм, без гарантии времени работы, но с хорошей производительностью на практике.[1][6] Этот параметр k известен как перекос графа.[3][7]

Также было проведено некоторое исследование связанной с этим проблемы: нахождение самого большого плоского индуцированный подграф данного графа. Опять же, это NP-сложный, но управляемый с фиксированным параметром, когда все вершины, кроме нескольких, принадлежат индуцированному подграфу.[8] Эдвардс и Фарр (2002) оказалась точной оценкой 3п/ (Δ + 1) от размера наибольшего планарного индуцированного подграфа как функция п, количество вершин в данном графе, и ∆, его максимальная степень; их доказательство приводит к полиномиальному алгоритму поиска индуцированного подграфа такого размера.[9]

Добавление ребер в планаризацию

После обнаружения большого плоского подграфа процесс инкрементальной планаризации продолжается, рассматривая оставшиеся ребра одно за другим. При этом он поддерживает планаризацию подграфа, образованного ребрами, которые уже были рассмотрены. Он добавляет каждое новое ребро к плоскому вложению этого подграфа, образуя рисунок с пересечениями, а затем заменяет каждую точку пересечения новой искусственной вершиной, разделяющей два пересекающихся ребра.[1][2] В некоторых версиях этой процедуры порядок добавления ребер является произвольным, но также можно выбрать порядок добавления ребер. случайная перестановка, запустив один и тот же алгоритм несколько раз и вернув лучшую планаризацию, которую он нашел.[1]

В простейшей форме этого процесса планарное вложение планаризованного подграфа не может изменяться при добавлении новых ребер. Чтобы добавить каждое новое ребро таким образом, чтобы минимизировать количество переходов, которые оно образует, можно использовать алгоритм кратчайшего пути в двойственный граф текущего вложения, чтобы найти кратчайшую последовательность граней вложения и пересекаемых ребер, которая соединяет концы нового ребра друг с другом. Этот процесс занимает полиномиальное время на ребро.[2]

Фиксация вложения планаризованного подграфа не обязательно оптимальна с точки зрения количества результирующих пересечений. Фактически, существуют графы, которые формируются путем добавления одного ребра к плоскому подграфу, где оптимальный чертеж имеет только два пересечения, но где фиксация плоского встраивания подграфа вынуждает создать линейное количество пересечений.[1] В качестве компромисса между поиском оптимальной планаризации плоского подграфа плюс одно ребро и сохранением фиксированного вложения можно перебрать все вложения планаризованного подграфа и найти то, которое минимизирует количество пересечений, образованных новым ребром.[1][10]

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

  1. ^ а б c d е ж грамм час я Буххайм, Кристоф; Чимани, Маркус; Гутвенгер, Карстен; Юнгер, Михаэль; Муцель, Петра (2014), «Пересечения и планаризация», в Тамассия, Роберто (ред.), Справочник по рисованию и визуализации графиков, Дискретная математика и ее приложения (Бока-Ратон), CRC Press, Бока-Ратон, Флорида.
  2. ^ а б c d Ди Баттиста, Джузеппе; Идс, Питер; Тамассия, Роберто; Толлис, Иоаннис Г. (1998), Рисование графиков: алгоритмы визуализации графиков (1-е изд.), Прентис Холл, стр. 215–218, ISBN  0133016153.
  3. ^ а б Чимани, Маркус (2008), Вычисление пересекающихся чисел (PDF), Кандидат наук. диссертация, Технический университет Дортмунда, Раздел 4.3.1, заархивировано из оригинал (PDF) на 2015-11-16.
  4. ^ а б Кэлинеску, Груя; Fernandes, Cristina G .; Финклер, Ульрих; Карлофф, Ховард (1998), "Алгоритм лучшего приближения для поиска плоских подграфов", Журнал алгоритмов, 27 (2): 269–302, Дои:10.1006 / jagm.1997.0920, МИСТЕР  1622397.
  5. ^ Каварабаяси, Кен-ичи; Рид, Брюс (2007), «Вычисление числа пересечений за линейное время», Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений (STOC '07), стр. 382–390, Дои:10.1145/1250790.1250848, МИСТЕР  2402463.
  6. ^ Юнгер, М .; Муцель, П. (1996), "Максимально плоские подграфы и красивые вложения: практические инструменты компоновки", Алгоритмика, 16 (1): 33–59, Дои:10.1007 / s004539900036, МИСТЕР  1394493.
  7. ^ Вайсштейн, Эрик В. «Асимметрия графика». MathWorld.
  8. ^ Каварабаяси, Кен-ичи (2009), «Планарность, допускающая несколько ошибок за линейное время», 50-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS '09) (PDF), стр. 639–648, Дои:10.1109 / FOCS.2009.45, МИСТЕР  2648441.
  9. ^ Эдвардс, Кейт; Фарр, Грэм (2002), "Алгоритм для поиска больших индуцированных плоских подграфов", Графический рисунок: 9-й Международный симпозиум, GD 2001 Вена, Австрия, 23–26 сентября 2001 г., Исправленные статьи, Конспекты лекций в комп. Наук, 2265, Springer, стр. 75–80, Дои:10.1007/3-540-45848-4_6, МИСТЕР  1962420.
  10. ^ Гутвенгер, Карстен; Муцель, Петра; Вайскирхер, Рене (2005), "Вставка ребра в плоский граф", Алгоритмика, 41 (4): 289–308, Дои:10.1007 / s00453-004-1128-8, МИСТЕР  2122529.