Le théorème d'empilement de cercles (aussi connu sous le nom de théorème de Koebe–Andreev–Thurston, et démontré par Paul Koebe et William Thurston) décrit les relations de tangence possibles entre des cercles dans le plan. Un empilement de cercles est une collection de disques fermés dans le plan (ou plus généralement dans n'importe quelle surface de Riemann) dont la réunion est connexe et dont les intérieurs sont disjoints. Le graphe d'intersection d'un empilement de cercles est le graphe ayant un sommet pour chaque cercle, et une arête pour chaque paire de cercles qui sont tangents. Si l'empilement de cercles est dans le plan ou dans la sphère, son graphe d'intersection est appelé un graphe de pièces ; plus généralement, les graphes d'intersection d'objets géométriques connectés, d'intérieurs disjoints sont appelés graphes de tangence ou graphes de contact. Les graphes de pièces sont toujours connexes, simples et planaires. Le théorème d'empilement de cercles affirme que ce sont les seules exigences pour qu'un graphe soit un graphe de pièces : pour tout graphe planaire simple et connexe G, il existe un empilement de cercles dans le plan dont le graphe d'intersection est isomorphe à G.

Unicité Un graphe planaire maximal G est un graphe planaire simple fini auquel aucune arête ne peut être ajoutée tout en préservant la planarité. Un tel graphe a toujours un unique plongement planaire, dans lequel chaque face du plongement (y compris la face extérieure) est un triangle. En d'autres termes, chaque graphe planaire maximal G est le 1-squelette d'un complexe simplicial qui est homéomorphe à la sphère. Le théorème d'empilement de cercles garantit l'existence d'un empilement (fini) de cercles dont le graphe d'intersection est isomorphe à G. Comme l'affirme l‘énoncé suivant de manière plus formelle, chaque graphe planaire maximal ne peut correspondre qu'à un seul empilement.

Théorème de Koebe–Andreev–Thurston : Si G est un graphe planaire simple et connexe, alors il existe un empilement de cercles dont le graphe de tangence est isomorphe à G, et si G est maximal (fini) cet empilement est unique, à des transformations de Möbius et des réflexions près.

Thurston observe que cette unicité est une conséquence du . Pour voir cela, soit G un graphe représenté par un empilement de cercles. Alors le plan dans lequel les cercles sont empilés peut être vu comme la frontière d'un demi-espace de Poincaré modélisant l'espace hyperbolique tridimensionnel ; de ce point de vue, chaque cercle est la frontière (l'ensemble des points à l'infini) d'un plan de l'espace hyperbolique (modélisé par une demi-sphère). On peut définir un ensemble de plans disjoints (mais asymptotes) de cette manière à partir des cercles de l'empilement, et un second ensemble de plans disjoints défini par les cercles qui circonscrivent chaque triplet de cercles de l'empilement tangents deux à deux. Ces deux ensembles de plans se rencontrent à angle droit et forment les générateurs d'un groupe de réflexion dont le domaine fondamental peut être vu comme une variété hyperbolique. Par le théorème de Mostow, la structure hyperbolique de ce domaine est déterminée de manière unique à une isométrie de l'espace hyperbolique près ; les actions de ces isométries sur le plan euclidien frontière du demi-espace de Poincaré sont des transformations de Möbius.

Une preuve plus élémentaire de cette propriété d'unicité est basée sur l'existence d'une valeur maximale dans tout ensemble fini et sur l'observation que, dans le triangle reliant les centres de trois cercles mutuellement tangents, l'angle formé au centre de l'un des cercles diminue de manière monotone par rapport à son rayon et augmente de manière monotone par rapport aux deux autres rayons. Étant donné deux empilements ayant le même graphe , on peut appliquer des réflexions et des transformations de Möbius pour faire correspondre les cercles extérieurs de ces deux empilements et avoir les mêmes rayons. Ensuite, soit un sommet intérieur de pour lequel les cercles dans les deux empilements ont des tailles aussi éloignées que possible (autrement dit, on choisit pour maximiser le rapport des rayons de ces cercles dans les deux empilements). Pour chaque face triangulaire de contenant , il en résulte que l'angle au centre du cercle pour dans le premier empilement est inférieur ou égal à l'angle dans le deuxième empilement, avec égalité possible seulement lorsque les deux autres cercles formant le triangle ont le même rapport des rayons dans les deux empilements. Mais la somme des angles de tous ces triangles entourant le centre du triangle doit être dans les deux empilements, donc tous les sommets voisins de doivent avoir le même rapport que . En appliquant le même argument à ces autres cercles à leur tour, il en résulte que tous les cercles dans les deux empilements ont le même rapport de rayons. Mais les cercles extérieurs ont été transformés pour avoir le même rayon, donc et les deux empilements ont des rayons identiques pour tous les cercles.

Relations avec la théorie des transformations conformes

Une transformation conforme entre deux ensembles ouverts dans le plan ou dans un espace de dimension supérieure est une fonction continue d'un ensemble à l'autre qui préserve les angles entre deux courbes quelconques. Le théorème de l'application conforme, formulé par Bernhard Riemann en 1851, affirme que, pour deux ouverts quelconques du plan homéomorphes à des disques ouverts, il existe une application conforme de l'un à l'autre. Les transformations conformes ont de nombreuses applications pratiques, mais il n'est pas toujours facile de construire une transformation conforme entre deux domaines donnés de manière explicite..

Lors de la conférence de Bieberbach de 1985, William Thurston a conjecturé que les empilements de cercles pouvaient être utilisés pour approximer les transformations conformes. Plus précisément, Thurston a utilisé des empilements de cercles pour trouver une transformation conforme d'un disque ouvert arbitraire A à l'intérieur d'un cercle ; l'application d'un disque topologique A à un autre disque B pouvait alors être trouvée en composant l'application de A à un cercle avec l'inverse de l'application de B à un cercle.

L'idée de Thurston était de placer des cercles d'un petit rayon r dans un pavage hexagonal du plan, dans la région A, en laissant une région étroite près de la frontière de A, de largeur r, où aucun autre cercle de ce rayon ne peut s'insérer. Il construit alors un graphe planaire maximal G à partir du graphe d'intersection des cercles, avec un sommet supplémentaire adjacent à tous les cercles à la frontière de l'empilement. Selon le théorème d'empilement de cercles, ce graphe planaire peut être représenté par un empilement de cercles C dans lequel toutes les arêtes (y compris celles incidentes au sommet de la frontière) sont représentées par des tangences de cercles. Les cercles de l'empilement de A correspondent un à un aux cercles de C, à l'exception du cercle de la frontière de C qui correspond à la frontière de A. Cette correspondance des cercles peut être utilisée pour construire une fonction continue de A à C dans laquelle chaque cercle et chaque espace entre trois cercles est envoyé d'un empilement à l'autre par une transformation de Möbius. Thurston a conjecturé que, dans la limite où le rayon r tend vers zéro, les fonctions de A à C construites de cette manière se rapprocheraient de la transformation conforme donnée par le théorème de Riemann.

La conjecture de Thurston a été prouvée en 1987 par Rodin et Sullivan. Plus précisément, ils ont montré que, lorsque n tend vers l'infini, la fonction fn déterminée en utilisant la méthode de Thurston à partir des empilements hexagonaux de cercles de rayon 1/n converge uniformément sur les sous-ensembles compacts de A vers une transformation conforme de A vers C.

Malgré le succès de la conjecture de Thurston, les applications pratiques de cette méthode ont été freinées par la difficulté de calculer les empilements de cercles et par son taux de convergence relativement lent : "Les empilements de cercles ne peuvent certainement pas rivaliser avec les méthodes classiques du point de vue de la rapidité et de la précision.". Cependant, elle présente certains avantages lorsqu'elle est appliquée à des domaines non simplement connexes et dans le choix des approximations initiales pour les techniques numériques qui calculent les , une technique différente de détermination de transformations conformes entre domaines polygonaux.

Démonstrations Il existe de nombreuses démonstrations du théorème d'empilement de cercles. La preuve originale de Paul Koebe est basée sur son théorème d'uniformisation conforme disant qu'un ouvert planaire ayant un nombre fini de composantes connexes est conforme à un ensemble de disques. Plusieurs preuves topologiques différentes sont également connues. La preuve de Thurston est basée sur le théorème du point fixe de Brouwer. En tant qu'étudiant diplômé, Oded Schramm a été supervisé par Thurston à l'Université de Princeton. Comme le raconte , il y a une "description poétique" dans la thèse de Schramm sur la manière dont l'existence d'un empilement de cercles peut être déduite du théorème du point fixe : . Il existe également une preuve utilisant une variante discrète de la pour construire des solutions au problème de Dirichlet, . Yves Colin de Verdière a prouvé l'existence de l'empilement de cercles comme minimisant une fonction convexe sur un certain espace de configurations.

Applications Le théorème d'empilement de cercles est un outil utile pour étudier divers problèmes de géométrie planaire, de transformations conformes et de graphes planaires. Une autre preuve du théorème du séparateur planaire, initialement due à Lipton et Tarjan, a été obtenue de cette manière. Une autre application du théorème d'empilement de cercles est que les limites non biaisées des graphes planaires de degré borné sont presque sûrement récurrentes. D'autres applications incluent des estimations de la plus grande valeur propre des graphes de genre borné.

En tracé de graphes, l'empilement de cercles a été utilisé pour trouver des tracés de graphes planaires ayant une bornée. et avec un borné.. Le théorème de Fáry, selon lequel chaque graphe qui peut être dessiné sans croisements dans le plan en utilisant des arêtes courbes peut également être dessiné sans croisements en n'utilisant que des segments de droite, découle comme un simple corollaire du théorème d'empilement de cercles : en plaçant les sommets aux centres des cercles et en dessinant des arêtes droites entre eux, un plongement planaire en ligne droite est obtenu.

Une forme plus forte du théorème d'empilement de cercles affirme que tout graphe polyédrique et son graphe dual peuvent être représentés par deux empilements de cercles, de sorte que les deux cercles tangents représentant une arête du graphe primal et les deux cercles tangents représentant le dual de la même arête aient toujours leurs tangences à angle droit l'un par rapport à l'autre au même point du plan. Un empilement de ce type peut être utilisé pour construire un polyèdre convexe représentant le graphe donné et ayant une sphère médiane, tangente à toutes les arêtes du polyèdre. Inversement, si un polyèdre a une sphère médiane, alors les cercles formés par les intersections de la sphère avec les faces du polyèdre et les cercles formés par les horizons sur la sphère vus de chaque sommet du polyèdre (les cercles de tangence des cônes issus de ces sommets) forment deux empilements duaux de ce type.

Aspects algorithmiques