# Graphe de disques

En théorie des graphes géométriques (en), un graphe de disques unité est le graphe d'intersection d'une famille de disques unité dans le plan euclidien. Autrement dit, c'est un graphe avec un sommet pour chaque disque dans la famille, et avec une arête entre deux sommets lorsque les disques correspondants se trouvent à une distance d'au plus une unité l'un de l'autre.
Ils sont souvent générés par un processus ponctuel de Poisson, constituant ainsi un exemple simple de structure aléatoire.

## Définitions

Il existe plusieurs définitions possibles du graphe de disques unité, équivalentes entre elles à un facteur d'échelle près :
* Les graphes de disques unité sont des graphes formés à partir d'une collection de points dans le plan euclidien, avec un sommet pour chaque point et une arête reliant chaque paire de points dont la distance est inférieure à un seuil fixe.
* Les graphes de disques unité sont des graphes d'intersection de cercles ou disques de même rayon. Ces graphes possèdent un sommet pour chaque cercle ou disque, et une arête reliant chaque paire de cercles ou disques ayant une intersection non vide.
* Les graphes de disques unité peuvent également être formés d'une manière différente à partir d'une collection de cercles de même rayon, en reliant deux cercles par une arête chaque fois qu'un cercle contient le centre de l'autre cercle.

## Propriétés

Tout sous-graphe induit d'un graphe de disques unité est également un graphe de disques unité. Un exemple de graphe qui n'est pas un graphe de disques unité est l'étoile $K_{1,6}$ avec un nœud central connecté à six feuilles : si chacun des six disques unité touche un disque unité commun, certains des six disques doivent se toucher entre eux. Par conséquent, les graphes de disques unité ne peuvent pas contenir un sous-graphe induit de type $K_{1,6}$. De nombreux autres sous-graphes induits interdits sont également connus.
Le nombre de graphes de disques unité sur $n$ sommets étiquetés est compris dans un facteur exponentiel de $n^{2n}$. Cette croissance rapide implique que les graphes de disques unité n'ont pas de largeur jumelle (en) bornée.

## Applications

Depuis les travaux de Huson et Sen en 1995, les graphes de disques unité sont utilisés en informatique pour modéliser la topologie des réseaux de communication sans fil ad hoc (en). Dans cette application, les nœuds sont connectés via une connexion sans fil directe sans station de base. On suppose que tous les nœuds sont homogènes et équipés d'antennes omnidirectionnelles. Les emplacements des nœuds sont modélisés comme des points euclidiens, et la zone dans laquelle un signal provenant d'un nœud peut être reçu par un autre nœud est modélisée comme un cercle. Si tous les nœuds disposent d'émetteurs de même puissance, ces cercles sont tous égaux. Les graphes géométriques aléatoires (en), formés en tant que graphes de disques unité avec des centres de disques générés aléatoirement, ont également été utilisés comme modèle de percolation et pour divers autres phénomènes.

## Complexité algorithmique

Si l'on dispose d'une collection de disques unité (ou de leurs centres) dans un espace de dimension fixée, il est possible de construire le graphe de disques unité correspondant en temps linéaire, en arrondissant les centres aux points de grille entiers proches, en utilisant une table de hachage pour trouver toutes les paires de centres à distance constante, et en filtrant la liste des paires pour celles dont les cercles s'intersectent. Le rapport entre le nombre de paires considérées par cet algorithme et le nombre d'arêtes du graphe final est une constante, donnant ainsi la borne de temps linéaire. Cependant, cette constante croît de manière exponentielle en fonction de la dimension.
Il est NP-difficile (plus précisément, complet pour la théorie existentielle des réels) de déterminer si un graphe, donné sans géométrie, peut être représenté comme un graphe de disques unité$^,$. En outre, il est impossible, en temps polynomial, de produire des coordonnées explicites d'une représentation de graphe de disques unité : certains graphes de disques unité nécessitent un nombre exponentiel de bits de précision pour toute telle représentation.
Cependant, de nombreux problèmes d'optimisation de graphes importants et difficiles tels que l'ensemble indépendant maximum, la coloration de graphes, et l'ensemble dominant minimum peuvent être approximés efficacement en utilisant la structure géométrique de ces graphes, et le problème de la clique maximale peut être résolu exactement pour ces graphes en temps polynomial, si une représentation par disque est donnée. Même si une représentation par disque n'est pas connue et qu'un graphe abstrait est donné en entrée, il est possible en temps polynomial de produire soit une clique maximale, soit une preuve que le graphe n'est pas un graphe de disques unité, et de 3-approximativement colorier le graphe en utilisant un algorithme glouton de coloration.