Граф многоугольника и круга

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

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

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

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

Признание

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

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

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

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

Ссылки

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

[kp-1] Перейти обратно: ^а ^б ^с ^д Кратохвил, Ян ; Пергель, Мартин (2004), «Два результата по графам пересечений многоугольников», Рисование графиков: 11-й Международный симпозиум, GD 2003, Перуджа, Италия, 21–24 сентября 2003 г., Пересмотренные статьи , Конспекты лекций по информатике, том. 2912, Берлин: Springer, стр. 59–70, номер документа : 10.1007/978-3-540-24595-7_6 , MR 2177583 .

[2] Кёбе, Манфред (1992), «О новом классе графов пересечений», Четвертый чехословацкий симпозиум по комбинаторике, графам и сложности (Prachatice, 1990) , Ann. Дискретная математика., вып. 51, Северная Голландия, Амстердам, стр. 141–143, номер документа : 10.1016/S0167-5060(08)70618-6 , MR 1206256 .

[3] Спинрад, Джереми П. (2003), Эффективные представления графов , Монографии Института Филдса, том. 19, Американское математическое общество, Провиденс, Род-Айленд, с. 41, ISBN 0-8218-2815-0 , МР 1971502 .

[4] Пергель, Мартин (2007), «Распознавание многоугольных круговых графов и графов интервальных нитей является NP-полным», Теоретико-графовые концепции в информатике: 33-й международный семинар, WG 2007, Дорнбург, Германия, 21–23 июня 2007 г. , Переработанные статьи , Конспекты лекций по информатике, том. 4769, Берлин: Springer, стр. 238–247, doi : 10.1007/978-3-540-74839-7_23 , MR 2428581 .

[5] Графики-пауки , Информационная система по классам графов и их включениям, получено 11 июля 2016 г.

[6] Косточка, Александр; Кратохвил, Ян (1997), «Покрытие и раскраска многоугольных круговых графов», Discrete Mathematics , 163 (1–3): 299–305, doi : 10.1016/S0012-365X(96)00344-5 , MR 1428585 .

[1]

[2]

[3]

[4]

[5]

[6]