Graphe de disques
Un article de Wikipédia, l'encyclopédie libre.
En théorie des graphes, un graphe de disques est le graphe d'intersection d'une collection de disques. C'est une extension du concept de graphe d'intervalle à la dimension 2.
Formellement, G est un graphe de disques s'il existe une collection de disques dans le plan dont les centres sont en bijection avec les sommets de G et telle que deux disques s'intersectent si et seulement si les sommets correspondants sont reliés par une arête dans G.
Quand tous les disques ont le même diamètre, le graphe est qualifié de graphe de disque-unité. Tout sous-graphe induit d'un graphe de disque-unité est également un graphe de disque-unité.
