График многоугольник-круг - Polygon-circle graph

«График-паук» перенаправляется сюда. Для диаграммы см. радарная карта. Для термина крикета см. Словарь терминов по крикету.
Слева - набор многоугольников, вписанных в круг; справа родственник График многоугольник-круг (граф пересечений многоугольников).
Внизу чередующаяся последовательность многоугольников по кругу.

в математический дисциплина теория графов, а многоугольник-круг граф является граф пересечений набора выпуклые многоугольники все чьи вершины лежать на общем круге. Эти графы также получили название паук-графики. Этот класс графов был впервые предложен Майкл Феллоуз в 1988 году, мотивируя это тем, что он закрыт под сжатие края и индуцированный подграф операции.[1]

Граф многоугольник-круг может быть представлен как «чередующаяся последовательность». Такая последовательность может быть получена путем возмущения многоугольников, представляющих граф (при необходимости), так, чтобы никакие два не имели общую вершину, а затем перечислить для каждой вершины (в круговом порядке, начиная с произвольной точки) многоугольник, присоединенный к этой вершине.

Закрытие под побуждением несовершеннолетних

Сужение края графа многоугольник-круг приводит к другому графу многоугольник-круг. Геометрическое представление нового графа может быть сформировано путем замены многоугольников, соответствующих двум конечным точкам сжатого ребра, их выпуклый корпус. Альтернативно, в чередующейся последовательности, представляющей исходный граф, объединение подпоследовательностей, представляющих конечные точки сжатого ребра, в единую подпоследовательность, дает альтернативное представление последовательности сжатого графа. Графы многоугольников также закрываются индуцированный подграф или, что эквивалентно, операции удаления вершины: для удаления вершины, удаления ее многоугольника из геометрического представления или удаления ее подпоследовательности точек из чередующейся последовательности.

Признание

М. Кебе анонсировал алгоритм распознавания с полиномиальным временем,[2] однако в его предварительной версии были «серьезные ошибки».[3] и окончательная версия так и не была опубликована.[1] Позже Мартин Пергель доказал, что проблема распознавания этих графов НП-полный.[4]Также NP-полный, чтобы определить, может ли данный граф быть представлен как граф многоугольник-круг с не более чем k вершин на многоугольник, для любого k ≥ 3.[1]

Связанные семейства графов

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

Графы многоугольник-круг, как правило, не идеальные графики, но они почти идеальны в том смысле, что их хроматические числа могут быть ограничены (экспоненциальной) функцией их числа клики.[6]

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

  1. ^ а б c d Кратохвил, Ян; Пергель, Мартин (2004), "Два результата о графах пересечений многоугольников", Графический рисунок: 11-й Международный симпозиум, GD 2003 г. Перуджа, Италия, 21-24 сентября 2003 г., исправленные документы, Конспект лекций по информатике, 2912, Берлин: Springer, стр. 59–70, Дои:10.1007/978-3-540-24595-7_6, МИСТЕР  2177583.
  2. ^ Кобе, Манфред (1992), "О новом классе графов пересечений", Четвертый чехословацкий симпозиум по комбинаторике, графам и сложности (Прахатице, 1990), Анна. Дискретная математика., 51, Северная Голландия, Амстердам, стр. 141–143, Дои:10.1016 / S0167-5060 (08) 70618-6, МИСТЕР  1206256.
  3. ^ Спинрад, Джереми П. (2003), Эффективные представления графов, Монографии Института Филдса, 19, Американское математическое общество, Провиденс, Род-Айленд, стр. 41, ISBN  0-8218-2815-0, МИСТЕР  1971502.
  4. ^ Пергель, Мартин (2007), «Распознавание графов многоугольник-круг и графов интервальных нитей является NP-полным», Теоретико-графические концепции в компьютерных науках: 33-й международный семинар, WG 2007, Дорнбург, Германия, 21-23 июня 2007 г., исправленные статьи, Конспект лекций по информатике, 4769, Берлин: Springer, стр. 238–247, Дои:10.1007/978-3-540-74839-7_23, МИСТЕР  2428581.
  5. ^ Графики-пауки, Информационная система по классам графов и их включениям, получено 11 июля 2016 г.
  6. ^ Косточка, Александр; Кратохвил, Ян (1997), «Покрытие и раскраска полигонально-окружных графов», Дискретная математика, 163 (1–3): 299–305, Дои:10.1016 / S0012-365X (96) 00344-5, МИСТЕР  1428585.