Представление неплоских графов с перекрывающимися кругами

16

Мы знаем, что мы можем представить любой плоский граф набором окружностей на плоскости, известным как граф монет . Каждый круг представляет вершину, и между двумя вершинами есть грань, если и только если круги "целуются" на своей границе.

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

Джо
источник

Ответы:

19

Окончательной статьей является статья Хлинени и Кратохвиля от 2001 года. В ней они показывают, что проблема распознавания графа пересечения диска (ваш вопрос) сложна с точки зрения NP, что говорит о том, что будет трудно придумать чистую характеристику. Они также указывают, что нельзя представить как пересечение дисков, отвечая на другую часть вашего вопроса.K3,3

Суреш Венкат
источник
7
Точнее, должно быть верно, что проблема полна для экзистенциальной теории принятия решений. Это известно для графов пересечения единичных дисков - см. Homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf - но я не знаю ссылки на произвольные графы пересечений дисков.
Дэвид Эппштейн
7
Также, используя аргументы размерности VC, можно показать, что семейство любого графа пересечений, определяемого «простыми» формами, довольно ограничено и не может включать в себя много графов. В частности, существует граф постоянного размера, который они не могут вызвать.
Сариэль Хар-Пелед
9

В работе с McDiarmid мы показали, что число помеченных графов на вершинах, которые являются графами пересечений дисков, равно n 3 nΘ ( 1 ) n, что намного меньше 2 ( nnn3nΘ(1)n2(n2)nnnΘ(1)nn
Θ(1)ncnCnc,C>0

@ Дэвид: Спасибо за упоминание моей работы!
Я также не знаю ни одной статьи, в которой приведено бытие к экзистенциальной теории вещественных чисел (ERT) для произвольных графов дисков. Однако в другой статье с McDiarmid мы дали конструкцию для «встраивания» расположения линий в граф диска, которая может быть превращена в доказательство полноты для ERT с некоторой дополнительной работой в соответствии с тем, что мы делали в статье с Кангом.

Тобиас Мюллер

Тобиас Мюллер
источник