Reprezentowanie wykresów niepłaskich z nakładającymi się okręgami

Wiemy, że możemy przedstawić dowolny wykres płaski za pomocą zestawu kół w płaszczyźnie, znanego jako wykres monety . Każde koło reprezentuje wierzchołek, a pomiędzy dwoma wierzchołkami znajduje się krawędź wtedy i tylko wtedy, gdy koła „pocałują się” na swojej granicy.

Załóżmy, że zamiast tego zezwalamy na nakładanie się kół i reprezentujemy krawędź przez parę kół, które przecinają się w ich wnętrzu? Jaką klasę wykresów możemy przedstawić w tym modelu? Oczywiście możemy przedstawić pełne wykresy (każde koło przecina każde inne koło). Czy możemy przedstawić wszystkie takie wykresy?

Ostatecznym artykułem jest artykuł Hlineny i Kratochvil z 2001 roku. Pokazują one, że problem rozpoznania wykresu przecięcia dysku (twoje pytanie) jest trudny do NP, co sugeruje, że trudno będzie uzyskać czystą charakterystykę. Wskazują również, że $K_{3,3}$ nie może być reprezentowane jako przecięcie dysków, odpowiadając na drugą część pytania.

$n$$n^{3n} \cdot \Theta(1)^n$ nnnΘ(1)nnΘ(1)ncnCnc,C>$2^{{n\choose 2}}$$n$$n^n \Theta(1)^n$$n$
$\Theta(1)^n$$c^n$$C^n$$c,C > 0$.)

@ David: Dziękujemy za wzmiankę o mojej pracy!
Nie znam też żadnej pracy, która by redukowała egzystencjalną teorię rzeczywistości (ERT) dla dowolnych grafów dyskowych. Jednak w innym artykule z McDiarmid przedstawiliśmy konstrukcję „osadzania” aranżacji linii na wykresie dyskowym, którą można przekształcić w dowód kompletności dla ERT przy dodatkowej pracy zgodnej z tym, co zrobiliśmy w pracy z Kangiem.

Tobias Mueller