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

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

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

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

В работе с McDiarmid мы показали, что число помеченных графов на вершинах, которые являются графами пересечений дисков, равно n 3 n ⋅ Θ ( 1 ) n, что намного меньше 2 ($n$$n^{3n} \cdot \Theta(1)^n$$2^{{n\choose 2}}$$n$$n^n \Theta(1)^n$$n$
$\Theta(1)^n$$c^n$$C^n$$c,C > 0$

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

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