График карты - Map graph

График карты (вверху), график коктейльной вечеринки K2,2,2,2, определяемый угловой смежностью восьми областей на плоскости (внизу слева), или как полуквадрат плоского двудольного графа (внизу справа, график ромбический додекаэдр )
В Четыре угла США. Несмотря на то, что эти четыре состояния встречаются в точке, а не разделяют границу ненулевой длины, они образуют смежные вершины в соответствующем графе карты.
В граф короля, карта-график квадратов шахматной доски. Шахматный король может перемещаться между любыми двумя соседними вершинами этого графа.

В теория графов, раздел математики, карта графика является неориентированный граф сформированный как граф пересечений конечного числа односвязных и внутренне непересекающихся областей Евклидова плоскость. Графики карты включают планарные графы, но более общие. В общем углу может встречаться любое количество регионов (как в Четыре угла Соединенных Штатов, где встречаются четыре штата), и когда они это сделают, граф карты будет содержать клика соединяющие соответствующие вершины, в отличие от плоских графов, в которых самые большие клики имеют только четыре вершины.[1] Другой пример графа карты - это граф короля, карту-график квадратов шахматная доска соединяющие пары квадратов, между которыми может перемещаться шахматный король.

Комбинаторное представление

Графы карт могут быть комбинаторно представлены как «полуквадраты плоских двудольных графов». То есть пусть грамм = (U,V,E) быть плоским двудольный граф, с двудольным (U,V). В квадрат из грамм - другой граф на том же множестве вершин, в котором две вершины смежны в квадрате, когда они находятся на расстоянии не более двух шагов в грамм. Полуквадрат или двудольная половина это индуцированный подграф одной стороны двудольного (скажем, V) в квадратном графе: множество его вершин V и у него есть ребро между каждыми двумя вершинами в V это два шага друг от друга в грамм. Полуквадрат - это карта-граф. Его можно представить геометрически, найдя планарное вложение из грамм, и расширяя каждую вершину V и его смежные края в звездообразную область, так что эти области соприкасаются в вершинах U. И наоборот, каждый граф карты таким образом может быть представлен как полуквадрат.[1]

Вычислительная сложность

В 1998 г. Миккель Торуп утверждал, что графы карт можно распознать в полиномиальное время.[2] Однако высокая экспонента алгоритма, который он набросал, делает его непрактичным, и Торруп не опубликовал подробностей своего метода и его доказательства.[3]

В максимальный независимый набор проблема имеет схема полиномиальной аппроксимации для графов карт, а хроматическое число можно аппроксимировать с точностью до двух раз за полиномиальное время.[4] Теория двумерность приводит ко многим другим алгоритмам аппроксимации и управляемый с фиксированными параметрами алгоритмы решения задач оптимизации на графах карт.[5][6][7]

Вариации и связанные концепции

А k-map graph - это граф карты, полученный из набора регионов, в которых не более k регионы встречаются в любой точке. Эквивалентно, это полуквадрат плоского двудольного графа, в котором множество вершин U (сторона двудольного разбиения, не использованная для создания полуквадрата) имеет максимум степень k. Граф с 3 отображениями - это планарный граф, и каждый планарный граф может быть представлен как граф с 3 картами. Каждый граф с четырьмя отображениями является 1-планарный граф, граф, который может быть нарисован не более чем с одним пересечением на ребро, и каждый оптимальный 1-планарный граф (граф, образованный из плоского четырехугольника путем добавления двух пересекающихся диагоналей к каждой четырехугольной грани) является графом с 4 картами. Однако некоторые другие 1-плоские графы не являются графами карт, потому что (в отличие от графов карт) они включают пересекающиеся ребра, которые не являются частью полного подграфа с четырьмя вершинами.[1]

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

  1. ^ а б c Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Карты-графики», Журнал ACM, 49 (2): 127–138, arXiv:cs / 9910013, Дои:10.1145/506147.506148, МИСТЕР  2147819.
  2. ^ Торуп, Миккель (1998), "Отображение графов за полиномиальное время", Материалы 39-го ежегодного симпозиума по основам информатики (FOCS 1998), стр. 396–405, Дои:10.1109 / SFCS.1998.743490, ISBN  978-0-8186-9172-0.
  3. ^ Бранденбург, Франц Дж. (Август 2018 г.), «Характеристика и распознавание четырехкарточных графов», Алгоритмика, Дои:10.1007 / s00453-018-0510-х
  4. ^ Чен, Чжи-Чжун (2001), "Алгоритмы приближения для независимых множеств в графах карт", Журнал алгоритмов, 41 (1): 20–40, Дои:10.1006 / jagm.2001.1178, МИСТЕР  1855346.
  5. ^ Демейн, Эрик Д.; Фомин, Федор В .; Хаджиагайи, Мохаммадтаги; Тиликос, Димитриос М. (2005), "Алгоритмы с фиксированными параметрами для (k,р)-центр в планарных графах и графах карт », ACM-транзакции на алгоритмах, 1 (1): 33–47, CiteSeerX  10.1.1.113.2070, Дои:10.1145/1077464.1077468, МИСТЕР  2163129.
  6. ^ Демейн, Эрик Д.; Хаджиагайи, Мохаммадтаги (2007), "Теория двумерности и ее алгоритмические приложения", Компьютерный журнал, 51 (3): 292–302, Дои:10.1093 / comjnl / bxm033, HDL:1721.1/33090.
  7. ^ Фомин, Федор В .; Локштанов Даниил; Саураб, Сакет (2012), «Двумерность и геометрические графы», Материалы двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA 2012), стр. 1563–1575, arXiv:1107.2221, Дои:10.1137/1.9781611973099.124, ISBN  978-1-61197-210-8, МИСТЕР  3205314.