Représentation de graphiques non plans avec des cercles qui se chevauchent

16

Nous savons que nous pouvons représenter n'importe quel graphe planaire par un ensemble de cercles dans le plan, connu sous le nom de graphe de pièces . Chaque cercle représente un sommet et il y a un bord entre deux sommets si et seulement si les cercles "s'embrassent" à leur frontière.

Supposons qu'au lieu de cela, nous permettions aux cercles de se chevaucher et de représenter un bord par une paire de cercles qui se croisent à l'intérieur? Quelle classe de graphiques pouvons-nous représenter dans ce modèle? Il est clair que nous pouvons représenter des graphiques complets (chaque cercle coupe chaque autre cercle). Pouvons-nous représenter tous les graphiques comme celui-ci?

Joe
la source

Réponses:

19

L'article définitif est un article de Hlineny et Kratochvil de 2001. Ils montrent que le problème de la reconnaissance d'un graphique d'intersection de disque (votre question) est NP-difficile, ce qui suggère qu'il sera difficile de trouver une caractérisation propre. Ils soulignent également que ne peut pas être représenté comme l'intersection de disques, répondant à l'autre partie de votre question.K3,3

Suresh Venkat
la source
7
Plus précisément, il devrait être vrai que le problème est complet pour la théorie de la décision existentielle des réels. Ceci est connu pour les graphiques d'intersection de disques unitaires - voir homepages.cwi.nl/~mueller/Papers/SphericityDotproduct.pdf - mais je ne connais pas de référence pour les graphiques d'intersection de disques arbitraires.
David Eppstein
7
De plus, on peut montrer en utilisant des arguments de dimension VC que la famille de tout graphe d'intersection défini par des formes "simples" est assez limitée et ne peut pas inclure de nombreux graphes. En particulier, il existe un graphique de taille constante qu'ils ne peuvent pas induire.
Sariel Har-Peled
9

nn3nΘ(1)n2(n2)nnnΘ(1)nn
Θ(1)ncnCnc,C>0

@ David: Merci d'avoir mentionné mon travail!
Je ne connais pas non plus de papier qui fasse la réduction à la théorie existentielle des réels (ERT) pour les graphes de disque arbitraires. Cependant, dans un autre article avec McDiarmid , nous avons donné une construction pour "incorporer" des arrangements de lignes dans un graphique de disque qui pourrait être transformé en une preuve d'exhaustivité pour ERT avec quelques travaux supplémentaires dans le sens de ce que nous avons fait dans l'article avec Kang.

Tobias Mueller

Tobias Mueller
la source