Utilisateur:Dfeldmann/brouillon2

⇐ brouillon précédent Ceci est un brouillon de traduction ; prière de ne pas le modifier ⇒ brouillon

Un empilement de cercles correspondant à un graphe planaire à cinq sommets

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 connectée de disques du plan (ou plus généralement de n'importe quelle surface de Riemann) 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 sur le plan, ou, équivalemment, sur la sphère, alors son graphe d'intersection est appelé un graphe de pièces; plus généralement, les graphes d'intersection d'objets géométriques disjoints par leurs intérieurs sont appelés graphes de tangence ou graphe de contacts. Les graphes de pièces sont toujours connectés, simples et planaires. Le théorème d'empilement de cercles stipule que ce sont les seules exigences pour qu'un graphe soit un graphe de pièces :

Théorème d'empilement de cercles : 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 planéité. 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 le stipule le théorème 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 maximal fini, alors l'empilement de cercles dont le graphe de tangence est isomorphe à G est unique, à des transformations de Möbius et des réflexions près.

Thurston observe que cette unicité est une conséquence du théorème de rigidité de Mostow (en). 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 $G$, 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 $v$ un sommet intérieur de $G$ pour lequel les cercles dans les deux empilements ont des tailles aussi éloignées que possible (autrement dit, on choisit $v$ pour maximiser le rapport $r_{1}/r_{2}$ des rayons de ces cercles dans les deux empilements). Pour chaque face triangulaire de $G$ contenant $v$, il en résulte que l'angle au centre du cercle pour $v$ 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 $r_{1}/r_{2}$ des rayons dans les deux empilements. Mais la somme des angles de tous ces triangles entourant le centre du triangle doit être $2\pi$ dans les deux empilements, donc tous les sommets voisins de $v$ doivent avoir le même rapport $r_{1}/r_{2}$ que $v$. 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 $r_{1}/r_{2}=1$ et les deux empilements ont des rayons identiques pour tous les cercles.

Relations avec la théorie des transformations conformes

Les empilements de cercles peuvent être utilisés pour approximer les applications conformes entre des domaines spécifiés. Chaque cercle à gauche correspond à un cercle à droite.

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 transformations 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 f_n 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. 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 applications de Schwartz-Christoffel (en), 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 Modèle:Harvtxt, 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 : « On peut juste voir le terrible monstre agiter ses bras dans une rage pure, les tentacules provoquant un sifflement effrayant, en se frottant les uns contre les autres ». Il existe également une preuve utilisant une variante discrète de la méthode de Perron (en) 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 résolution angulaire (en) bornée et avec un nombre de pente (en) borné. Le théorème de Fáry (en), 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.

Un polyèdre et sa midsphère. Le théorème d'empilement de cercles implique que chaque graphe polyédrique peut être représenté comme le graphe d'un polyèdre ayant une midsphère.

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

Modèle:Harvtxt décrivent un algorithme de relaxation numérique pour trouver des empilements de cercles, basé sur les idées de William Thurston. La version du problème d'empilement de cercles qu'ils résolvent prend en entrée un graphe planaire, dans lequel toutes les faces internes sont des triangles et pour lequel les sommets externes ont été étiquetés par des nombres positifs. Il produit en sortie un empilement de cercles dont les tangences représentent le graphe donné, et pour lequel les cercles représentant les sommets externes ont les rayons spécifiés dans l'entrée. Comme ils le suggèrent, la clé du problème est d'abord de calculer les rayons des cercles dans l'empilement ; une fois les rayons connus, les positions géométriques des cercles ne sont pas difficiles à calculer. Ils commencent avec un ensemble de rayons provisoires qui ne correspondent pas à un empilement valide, puis effectuent à plusieurs reprises les étapes suivantes :

1. Choisir un sommet interne v du graphe d'entrée.
2. Calculer l'angle total θ que ses k cercles voisins couvriraient autour du cercle pour v, si les voisins étaient placés tangents les uns aux autres et au cercle central en utilisant leurs rayons provisoires.
3. Déterminer un rayon représentatif r pour les cercles voisins, de sorte que k cercles de rayon r donnent le même angle de couverture θ que les voisins de v donnent.
4. Définir le nouveau rayon pour v comme la valeur pour laquelle k cercles de rayon r donneraient un angle de couverture exactement égal à 2π.

Chacune de ces étapes peut être effectuée avec des calculs trigonométriques simples, et comme le soutiennent Collins et Stephenson, le système de rayons converge rapidement vers un point fixe unique pour lequel tous les angles de couverture sont exactement de 2π. Une fois que le système a convergé, les cercles peuvent être placés un à un, à chaque étape en utilisant les positions et les rayons de deux cercles voisins pour déterminer le centre de chaque cercle successif.

Modèle:Harvtxt décrit une technique itérative similaire pour trouver des empilements simultanés d'un graphe polyédrique et de son dual, dans lesquels les cercles du dual sont à angle droit par rapport aux cercles du primal. Il prouve que la méthode prend un temps polynomial dans le nombre de cercles et dans log 1/ε, où ε est une limite sur la distance des centres et des rayons de l'empilement calculé par rapport à ceux d'un empilement optimal.

Généralisations

Le théorème d'empilement de cercles se généralise aux graphes non planaires. Si G est un graphe qui peut être plongé sur une surface S, alors il existe une courbure métrique riemannienne d sur S et un empilement de cercles sur (S, d) dont le graphe de contacts est isomorphe à G. Si S est fermée (compacte et sans bord) et G est une triangulation de S, alors (S, d) et l'empilement sont uniques à une équivalence conforme près. Si S est la sphère, alors cette équivalence est à transformations de Möbius près ; si c'est un tore, alors l'équivalence est à homothétie près et à isométries près, tandis que si S a un genre d'au moins 2, alors l'équivalence est à isométries près.

Une autre généralisation du théorème d'empilement de cercles implique de remplacer la condition de tangence par un angle d'intersection spécifié entre les cercles correspondant aux sommets voisins. Une version particulièrement élégante est la suivante. Supposons que G soit un graphe planaire 3-connexe fini (c'est-à-dire un graphe polyédrique), alors il existe une paire d'empilements de cercles, l'un dont le graphe d'intersection est isomorphe à G, l'autre dont le graphe d'intersection est isomorphe au dual planaire de G, et pour chaque sommet de G et face adjacente à celui-ci, le cercle dans le premier empilement correspondant au sommet intersecte orthogonalement le cercle dans le second empilement correspondant à la face. Par exemple, en appliquant ce résultat au graphe du tétraèdre, on obtient, pour quatre cercles mutuellement tangents, un deuxième ensemble de quatre cercles mutuellement tangents, chacun étant orthogonal à trois des quatre premiers. Une autre généralisation, remplaçant l'angle d'intersection par la distance inversive, permet de spécifier des empilements dans lesquels certains cercles doivent être disjoints les uns des autres plutôt que de se croiser ou d'être tangents.

Encore une autre variété de généralisations permettent des formes qui ne sont pas des cercles. Supposons que G = (V, E) soit un graphe planaire fini, et qu'à chaque sommet v de G corresponde une forme $K_{v}\subset \mathbb {R} ^{2}$, qui est homéomorphe au disque unité fermé et dont la frontière est lisse. Alors il existe un empilement $P=(K'_{v}:v\in V)$ dans le plan tel que $K'_{v}\cap K'_{u}\neq \varnothing$ si et seulement si $[v,u]\in E$ et pour chaque $v\in V$, l'ensemble $K'_{v}$ est obtenu à partir de $K_{v}$ par translation et homothétie. (Notez que dans le théorème original d'empilement de cercles, il y a trois paramètres réels par sommet, dont deux décrivent le centre du cercle correspondant et un décrit le rayon, et il y a une équation par arête. Cela vaut aussi dans cette généralisation.) Une preuve de cette généralisation peut être obtenue en appliquant la preuve originale de Koebe et le théorème de Brandt et Harrington stipulant que tout domaine de connexité finie est conforme à un domaine planaire dont les composantes de la frontière ont des formes spécifiées, à translations et homothéties près.

Histoire

Les empilements de cercles ont été étudiés dès 1910, dans les travaux d'Arnold Emch sur les spirales de Doyle dans la phyllotaxie (les mathématiques de la croissance des plantes). Le théorème d'empilement de cercles a été prouvé pour la première fois par Paul Koebe. William Thurston a redécouvert le théorème d'empilement de cercles, et a noté qu'il découlait des travaux d'E. M. Andreev. Thurston a également proposé un schéma pour utiliser le théorème d'empilement de cercles pour obtenir un homéomorphisme d'un sous-ensemble simplement connexe du plan à l'intérieur du disque unité. La conjecture de Thurston pour les empilements de cercles est sa conjecture selon laquelle l'homéomorphisme convergera vers le mappage de Riemann à mesure que les rayons des cercles tendent vers zéro. La conjecture de Thurston a été plus tard prouvée par Burton Rodin et Dennis Sullivan. Cela a conduit à une effervescence de recherches sur les extensions du théorème d'empilement de cercles, les relations avec les mappages conformes et les applications.

Voir aussi

• Gasket d'Apollonius, un empilement infini formé en remplissant à plusieurs reprises des écarts triangulaires
• Empilement de cercles, des arrangements denses de cercles sans tangences spécifiées
• Spirales de Doyle, des empilements de cercles représentant des graphes planaires infinis 6-réguliers
• Cercle de Ford, un empilement de cercles le long de la ligne des nombres rationnels
• Graphe de pièces de monnaie, les graphes de pièces dont les cercles ont tous des rayons égaux
• Lemme de l'anneau, une borne sur les tailles des cercles adjacents dans un empilement

Références

• « {{{1}}} ».
• « {{{1}}} »
• « {{{1}}} »
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} »
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} »
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} »
• « {{{1}}} ».
• « {{{1}}} » *« {{{1}}} ». *« {{{1}}} ». *« {{{1}}} ».

Liens externes

• CirclePack (logiciel libre pour construire des empilements de cercles à partir de graphes) et Bibliographie sur les empilements de cercles par Kenneth Stephenson, Univ. of Tennessee

___________________________________________________

A circle packing for a five-vertex planar graph

The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in general, on any Riemann surface) whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. If the circle packing is on the plane, or, equivalently, on the sphere, then its intersection graph is called a coin graph; more generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. Coin graphs are always connected, simple, and planar. The circle packing theorem states that these are the only requirements for a graph to be a coin graph:

Circle packing theorem: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G.

Uniqueness

A maximal planar graph G is a finite simple planar graph to which no more edges can be added while preserving planarity. Such a graph always has a unique planar embedding, in which every face of the embedding (including the outer face) is a triangle. In other words, every maximal planar graph G is the 1-skeleton of a simplicial complex which is homeomorphic to the sphere. The circle packing theorem guarantees the existence of a circle packing with finitely many circles whose intersection graph is isomorphic to G. As the following theorem states more formally, every maximal planar graph can have at most one packing.

Koebe–Andreev–Thurston theorem: If G is a finite maximal planar graph, then the circle packing whose tangency graph is isomorphic to G is unique, up to Möbius transformations and reflections in lines.

Thurston observes that this uniqueness is a consequence of the Mostow rigidity theorem. To see this, let G be represented by a circle packing. Then the plane in which the circles are packed may be viewed as the boundary of a halfspace model for three-dimensional hyperbolic space; with this view, each circle is the boundary of a plane within the hyperbolic space. One can define a set of disjoint planes in this way from the circles of the packing, and a second set of disjoint planes defined by the circles that circumscribe each triangular gap between three of the circles in the packing. These two sets of planes meet at right angles, and form the generators of a reflection group whose fundamental domain can be viewed as a hyperbolic manifold. By Mostow rigidity, the hyperbolic structure of this domain is uniquely determined, up to isometry of the hyperbolic space; these isometries, when viewed in terms of their actions on the Euclidean plane on the boundary of the half-plane model, translate to Möbius transformations.

There is also a more elementary proof of the same uniqueness property, based on existence of a maximum value in any finite set and on the observation that, in the triangle connecting the centers of three mutually tangent circles, the angle formed at the center of one of the circles is monotone decreasing in its radius and monotone increasing in the two other radii. Given two packings for the same graph $G$, one may apply reflections and Möbius transformations to make the outer circles in these two packings correspond to each other and have the same radii. Then, let $v$ be an interior vertex of $G$ for which the circles in the two packings have sizes that are as far apart as possible: that is, choose $v$ to maximize the ratio $r_{1}/r_{2}$ of the radii of its circles in the two packings. For each triangular face of $G$ containing $v$, it follows that the angle at the center of the circle for $v$ in the first packing is less than or equal to the angle in the second packing, with equality possible only when the other two circles forming the triangle have the same ratio $r_{1}/r_{2}$ of radii in the two packings. But the sum of the angles of all of these triangles surrounding the center of the triangle must be $2\pi$ in both packings, so all neighboring vertices to $v$ must have the same ratio as $v$ itself. By applying the same argument to these other circles in turn, it follows that all circles in both packings have the same ratio. But the outer circles have been transformed to have ratio one, so $r_{1}/r_{2}=1$ and the two packings have identical radii for all circles.

Relations with conformal mapping theory

Circle packings can be used to approximate conformal mappings between specified domains. Each circle on the left corresponds to a circle on the right.

A conformal map between two open sets in the plane or in a higher-dimensional space is a continuous function from one set to the other that preserves the angles between any two curves. The Riemann mapping theorem, formulated by Bernhard Riemann in 1851, states that, for any two open topological disks in the plane, there is a conformal map from one disk to the other. Conformal mappings have applications in mesh generation, map projection, and other areas. However, it is not always easy to construct a conformal mapping between two given domains in an explicit way.

At the Bieberbach conference in 1985, William Thurston conjectured that circle packings could be used to approximate conformal mappings. More precisely, Thurston used circle packings to find a conformal mapping from an arbitrary open disk A to the interior of a circle; the mapping from one topological disk A to another disk B could then be found by composing the map from A to a circle with the inverse of the map from B to a circle.

Thurston's idea was to pack circles of some small radius r in a hexagonal tessellation of the plane, within region A, leaving a narrow region near the boundary of A, of width r, where no more circles of this radius can fit. He then constructs a maximal planar graph G from the intersection graph of the circles, together with one additional vertex adjacent to all the circles on the boundary of the packing. By the circle packing theorem, this planar graph can be represented by a circle packing C in which all the edges (including the ones incident to the boundary vertex) are represented by tangencies of circles. The circles from the packing of A correspond one-for-one with the circles from C, except for the boundary circle of C which corresponds to the boundary of A. This correspondence of circles can be used to construct a continuous function from A to C in which each circle and each gap between three circles is mapped from one packing to the other by a Möbius transformation. Thurston conjectured that, in the limit as the radius r approaches zero, the functions from A to C constructed in this way would approach the conformal function given by the Riemann mapping theorem.

Thurston's conjecture was proven by Modèle:Harvtxt. More precisely, they showed that, as n goes to infinity, the function f_n determined using Thurston's method from hexagonal packings of radius-1/n circles converges uniformly on compact subsets of A to a conformal map from A to C.

Despite the success of Thurston's conjecture, practical applications of this method have been hindered by the difficulty of computing circle packings and by its relatively slow convergence rate. However, it has some advantages when applied to non-simply-connected domains and in selecting initial approximations for numerical techniques that compute Schwarz–Christoffel mappings, a different technique for conformal mapping of polygonal domains.

Proofs

There are many known proofs of the circle packing theorem. Paul Koebe's original proof is based on his conformal uniformization theorem saying that a finitely connected planar domain is conformally equivalent to a circle domain. There are several different topological proofs that are known. Thurston's proof is based on Brouwer's fixed point theorem. As a graduate student, Oded Schramm was supervised by Thurston at Princeton University. As Modèle:Harvtxt recounts, there is a "poetic description" in Schramm's dissertation of how existence for circle packing can be deduced from the fixed point theorem: "One can just see the terrible monster swinging its arms in sheer rage, the tentacles causing a frightful hiss, as they rub against each other." There is also a proof using a discrete variant of Perron's method of constructing solutions to the Dirichlet problem. Yves Colin de Verdière proved the existence of the circle packing as a minimizer of a convex function on a certain configuration space.

Applications

The circle packing theorem is a useful tool to study various problems in planar geometry, conformal mappings and planar graphs. An alternative proof of the planar separator theorem, originally due to Lipton and Tarjan, has been obtained in this way. Another application of the circle packing theorem is that unbiased limits of bounded-degree planar graphs are almost surely recurrent. Other applications include implications for the cover time. and estimates for the largest eigenvalue of bounded-genus graphs.

In graph drawing, circle packing has been used to find drawings of planar graphs with bounded angular resolution and with bounded slope number. Fáry's theorem, that every graph that can be drawn without crossings in the plane using curved edges can also be drawn without crossings using straight line segment edges, follows as a simple corollary of the circle packing theorem: by placing vertices at the centers of the circles and drawing straight edges between them, a straight-line planar embedding is obtained.

A polyhedron and its midsphere. The circle packing theorem implies that every polyhedral graph can be represented as the graph of a polyhedron that has a midsphere.

A stronger form of the circle packing theorem asserts that any polyhedral graph and its dual graph can be represented by two circle packings, such that the two tangent circles representing a primal graph edge and the two tangent circles representing the dual of the same edge always have their tangencies at right angles to each other at the same point of the plane. A packing of this type can be used to construct a convex polyhedron that represents the given graph and that has a midsphere, a sphere tangent to all of the edges of the polyhedron. Conversely, if a polyhedron has a midsphere, then the circles formed by the intersections of the sphere with the polyhedron faces and the circles formed by the horizons on the sphere as viewed from each polyhedron vertex form a dual packing of this type.

Algorithmic aspects

Modèle:Harvtxt describe a numerical relaxation algorithm for finding circle packings, based on ideas of William Thurston. The version of the circle packing problem that they solve takes as input a planar graph, in which all the internal faces are triangles and for which the external vertices have been labeled by positive numbers. It produces as output a circle packing whose tangencies represent the given graph, and for which the circles representing the external vertices have the radii specified in the input. As they suggest, the key to the problem is to first calculate the radii of the circles in the packing; once the radii are known, the geometric positions of the circles are not difficult to calculate. They begin with a set of tentative radii that do not correspond to a valid packing, and then repeatedly perform the following steps:

1. Choose an internal vertex v of the input graph.
2. Calculate the total angle θ that its k neighboring circles would cover around the circle for v, if the neighbors were placed tangent to each other and to the central circle using their tentative radii.
3. Determine a representative radius r for the neighboring circles, such that k circles of radius r would give the same covering angle θ as the neighbors of v give.
4. Set the new radius for v to be the value for which k circles of radius r would give a covering angle of exactly 2π.

Each of these steps may be performed with simple trigonometric calculations, and as Collins and Stephenson argue, the system of radii converges rapidly to a unique fixed point for which all covering angles are exactly 2π. Once the system has converged, the circles may be placed one at a time, at each step using the positions and radii of two neighboring circles to determine the center of each successive circle.

Modèle:Harvtxt describes a similar iterative technique for finding simultaneous packings of a polyhedral graph and its dual, in which the dual circles are at right angles to the primal circles. He proves that the method takes time polynomial in the number of circles and in log 1/ε, where ε is a bound on the distance of the centers and radii of the computed packing from those in an optimal packing.

Generalizations

The circle packing theorem generalizes to graphs that are not planar. If G is a graph that can be embedded on a surface S, then there is a constant curvature Riemannian metric d on S and a circle packing on (S, d) whose contacts graph is isomorphic to G. If S is closed (compact and without boundary) and G is a triangulation of S, then (S, d) and the packing are unique up to conformal equivalence. If S is the sphere, then this equivalence is up to Möbius transformations; if it is a torus, then the equivalence is up to scaling by a constant and isometries, while if S has genus at least 2, then the equivalence is up to isometries.

Another generalization of the circle packing theorem involves replacing the condition of tangency with a specified intersection angle between circles corresponding to neighboring vertices. A particularly elegant version is as follows. Suppose that G is a finite 3-connected planar graph (that is, a polyhedral graph), then there is a pair of circle packings, one whose intersection graph is isomorphic to G, another whose intersection graph is isomorphic to the planar dual of G, and for every vertex in G and face adjacent to it, the circle in the first packing corresponding to the vertex intersects orthogonally with the circle in the second packing corresponding to the face. For instance, applying this result to the graph of the tetrahedron gives, for any four mutuall tangent circles, a second set of four mutually tangent circles each of which is orthogonal to three of the first four. A further generalization, replacing intersection angle with inversive distance, allows the specification of packings in which some circles are required to be disjoint from each other rather than crossing or being tangent.

Yet another variety of generalizations allow shapes that are not circles. Suppose that G = (V, E) is a finite planar graph, and to each vertex v of G corresponds a shape $K_{v}\subset \mathbb {R} ^{2}$, which is homeomorphic to the closed unit disk and whose boundary is smooth. Then there is a packing $P=(K'_{v}:v\in V)$ in the plane such that $K'_{v}\cap K'_{u}\neq \varnothing$ if and only if $[v,u]\in E$ and for each $v\in V$ the set $K'_{v}$ is obtained from $K_{v}$ by translating and scaling. (Note that in the original circle packing theorem, there are three real parameters per vertex, two of which describe the center of the corresponding circle and one of which describe the radius, and there is one equation per edge. This also holds in this generalization.) One proof of this generalization can be obtained by applying Koebe's original proof and the theorem of Brandt and Harrington stating that any finitely connected domain is conformally equivalent to a planar domain whose boundary components have specified shapes, up to translations and scaling.

History

Circle packings were studied as early as 1910, in the work of Arnold Emch on Doyle spirals in phyllotaxis (the mathematics of plant growth). The circle packing theorem was first proved by Paul Koebe. William Thurston rediscovered the circle packing theorem, and noted that it followed from the work of E. M. Andreev. Thurston also proposed a scheme for using the circle packing theorem to obtain a homeomorphism of a simply connected proper subset of the plane onto the interior of the unit disk. The Thurston Conjecture for Circle Packings is his conjecture that the homeomorphism will converge to the Riemann mapping as the radii of the circles tend to zero. The Thurston Conjecture was later proved by Burton Rodin and Dennis Sullivan. This led to a flurry of research on extensions of the circle packing theorem, relations to conformal mappings, and applications.

See also

• Apollonian gasket, an infinite packing formed by repeatedly filling triangular gaps
• Circle packing, dense arrangements of circles without specified tangencies
• Doyle spirals, circle packings representing infinite 6-regular planar graphs
• Ford circles, a packing of circles along the rational number line
• Penny graph, the coin graphs whose circles all have equal radii
• Ring lemma, a bound on the sizes of adjacent circles in a packing

References

• « {{{1}}} ».
• « {{{1}}} »
• « {{{1}}} »
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} »
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} »
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} »
• « {{{1}}} ».
• « {{{1}}} »
• « {{{1}}} ».
• « {{{1}}} ».
• « {{{1}}} ».

External links

• CirclePack (free software for constructing circle packings from graphs) and Circle packing bibliography by Kenneth Stephenson, Univ. of Tennessee