Representando gráficos não planos com círculos sobrepostos

Sabemos que podemos representar qualquer gráfico plano por um conjunto de círculos no plano, conhecido como gráfico de moedas . Cada círculo representa um vértice e há uma aresta entre dois vértices se e somente se os círculos "beijarem" em seus limites.

Suponha que, em vez disso, permitamos que os círculos se sobreponham e representemos uma aresta por um par de círculos que se cruzam em seu interior? Que classe de gráficos podemos representar neste modelo? Claramente, podemos representar gráficos completos (cada círculo cruza todos os outros círculos). Podemos representar todos os gráficos como este?

O artigo definitivo é um artigo de Hlineny e Kratochvil, de 2001. Nele, eles mostram que o problema de reconhecer um gráfico de interseção de disco (sua pergunta) é NP-difícil, o que sugere que será difícil apresentar uma caracterização limpa. Eles também apontam que $K_{3,3}$ não pode ser representado como a interseção de discos, respondendo à outra parte da sua pergunta.

Num artigo com McDiarmid , mostramos que o número de gráficos rotulados em vértices que são gráficos de interseção de discos é n 3 n ⋅ Θ ( 1 ) n que é muito menor que 2 ($n$$n^{3n} \cdot \Theta(1)^n$ , o número total de gráficos rotulados emvértices e muito mais que, o número de gráficos planares (tocando em gráficos de discos) emvértices. (Aqui eu quero dizer comuma quantidade que é delimitada abaixo pore acima porpara algumas constantes ) $2^{{n\choose 2}}$$n$$n^n \Theta(1)^n$$n$
$\Theta(1)^n$$c^n$$C^n$$c,C > 0$

@ David: Obrigado por mencionar o meu trabalho!
Também não estou ciente de nenhum trabalho que faça a redução à teoria existencial dos reais (ERT) para gráficos de disco arbitrários. No entanto, em outro artigo com McDiarmid , demos uma construção para "incorporar" arranjos de linhas em um gráfico de disco que poderia ser transformado em uma prova de completude para a ERT com algum trabalho adicional ao longo das linhas do que fizemos no artigo com Kang.

Tobias Mueller