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 (en), constituant ainsi un exemple simple de structure aléatoire.

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.

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}]]^[1]. De nombreux autres sous-graphes induits interdits sont également connus^[2].

Le nombre de graphes de disques unité sur ${\displaystyle n}$ sommets étiquetés est compris dans un facteur exponentiel de ${\displaystyle n^{2n}}$^[3]. Cette croissance rapide implique que les graphes de disques unité n'ont pas de largeur jumelle (en) bornée^[4].

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^[5].

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^[6].

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é^[7],[8]. 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^[9].

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^[10], 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^[11]. 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é^[10], et de 3-approximativement colorier le graphe en utilisant un algorithme glouton de coloration^[11].

• Résilience de barrière (en), un problème algorithmique de bris de cycles dans les graphes de disques unité
• Graphe d'indifférence, un analogue unidimensionnel des graphes de disques unité
• Graphe penny (en), un graphe de disques unité où les disques peuvent être tangents mais non chevauchants (graphe de contact (en))
• Graphe de pièce, le graphe de contact de disques (pas nécessairement de même taille)
• Complexe de Vietoris–Rips, une généralisation du graphe de disques unité construisant des espaces topologiques d'ordre supérieur à partir des distances unité dans un espace métrique
• Graphe de distance unité, un graphe formé en reliant des points à distance exactement une unité plutôt qu'au plus une unité

 : document utilisé comme source pour la rédaction de cet article.

• Aistis Atminas et Viktor Zamaraev, Sur les sous-graphes induits interdits pour les graphes de disques unité, vol. 60, 2018, 57–97 p. (DOI 10.1007/s00454-018-9968-1, MR 3807349, arXiv 1602.08148, S2CID 254025741), chap. 1. 

• Jon L. Bentley, Donald F. Stanat et E. Hollins Jr. Williams, La complexité de la recherche de voisins à distance fixe, vol. 6, 1977, 209–212 p. (DOI 10.1016/0020-0190(77)90070-9, MR 0489084), chap. 6. .

• Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé et Rémi Watrigant, Twin-width II : petites classes, vol. 2, 2022, P10:1–P10:42 (DOI 10.5070/C62257876, MR 4449818, arXiv 2006.09877), chap. 2. 

• Heinz Breu et David G. Kirkpatrick, La reconnaissance des graphes de disques unité est NP-difficile, vol. 9, 1998, 3–24 p. (DOI 10.1016/s0925-7721(97)00014-x ), chap. 1–2. .

• Brent N. Clark, Charles J. Colbourn et David S. Johnson, Graphes de disques unité, vol. 86, 1990, 165–177 p. (DOI 10.1016/0012-365X(90)90358-O ), chap. 1–3.

• Jesper Dall et Michael Christensen, Graphes géométriques aléatoires, vol. 66, 2002 (PMID 12241440, DOI 10.1103/PhysRevE.66.016121, Bibcode 2002PhRvE..66a6121D, arXiv cond-mat/0203026, S2CID 15193516), chap. 1, p. 016121.

• Michał Dębski, Konstanty Junosza-Szaniawski et Małgorzata Śleszyńska-Nowak, Indice chromatique fort des graphes sans ${\displaystyle K_{1,t}}$, vol. 284, 2020, 53–60 p. (DOI 10.1016/j.dam.2020.03.024, MR 4115456, S2CID 216369782). 

• A. Gräf, M. Stumpf et G. Weißenfels, Sur la coloration des graphes de disques unité, vol. 20, 1998, 277–293 p. (DOI 10.1007/PL00009196, MR 1489033, S2CID 36161020), chap. 3. .

• Mark L. Huson et Arunabha Sen, Conférence sur les communications militaires, IEEE MILCOM '95, vol. 2, 1995, 647–651 p. (ISBN 0-7803-2489-7, DOI 10.1109/MILCOM.1995.483546, S2CID 62039740).

• Ross J. Kang et Tobias Müller, Actes du vingt-septième Symposium sur la géométrie computationnelle (SoCG'11), 13–15 juin 2011, Paris, France, 2011, 308–314 p..

• Madhav V. Marathe, Heinz Breu, Harry B. Hunt III, S. S. Ravi et Daniel J. Rosenkrantz, Heuristiques géométriques pour les graphes de disques unité, 1994 (Bibcode 1994math......9226M, arXiv math.CO/9409226).

• Tomomi Matsui, Géométrie discrète et computationnelle, vol. 1763, 2000, 194–200 p. (ISBN 978-3-540-67181-7, DOI 10.1007/978-3-540-46515-7_16), « Algorithmes d'approximation pour les problèmes d'ensemble indépendant maximum et de coloration fractionnaire sur les graphes de disques unité ».

• Colin McDiarmid et Tobias Mueller, Réalisations entières des graphes de disques et de segments, vol. 103, 2013, 114–143 p. (DOI 10.1016/j.jctb.2012.09.004 , Bibcode 2011arXiv1111.2931M, arXiv 1111.2931), chap. 1. 

• Colin McDiarmid et Tobias Müller, Le nombre de graphes de disques, vol. 35, 2014, 413–431 p. (DOI 10.1016/j.ejc.2013.06.037 , MR 3090514). 

• Vijay Raghavan et Jeremy Spinrad, Algorithmes, 160–172 p. (DOI 10.1016/S0196-6774(03)00048-8, MR 2006100), chap. 1. 

• Portail des mathématiques
• Portail de l'informatique théorique