×

A variational principle for circle packings. (Un principe variationnel pour les empilements de cercles.) (French) Zbl 0745.52010

It was shown by P. Koebe [Ber. Verh. Sächs. Akad. Wiss., Math.- Phys. Kl. 88, 141–164 (1936; Zbl 0017.21701; JFM 62.1217.04)] and rediscovered by E. M. Andreev [Mat. Sb., Nov. Ser. 81 (123), 445–478 (1970; Zbl 0194.23202)]; ibid. 83 (125), 256–260 (1970; Zbl 0203.54904)] that any triangulated planar graph can be represented by nonoverlapping circular disks in the plane such that any two of them touch if and only if the corresponding vertices are adjacent. Furthermore, W. P. Thurston [The Geometry and Topology of Three-Manifolds, Princeton Notes (1985), Chapter 13] showed that this representation is essentially unique. In the present paper (and the author’s earlier paper in Forum Math. 1, No. 4, 395–402 (1989; Zbl 0685.52012)) the same problem, and some generalizations, are considered from an algorithmic point of view.

MSC:

52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
57M50 General geometric structures on low-dimensional manifolds
30F99 Riemann surfaces
51M16 Inequalities and extremum problems in real or complex geometry
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] [AL] Ahlfors, L.: Lectures on quasi-conformal mappings. Van Nostrand 1982
[2] [AN] Andreev, E.M.. On convex polyhedra in Loba?eskiî spaces. Mat. USSR Sbornik10, 413-440 (1970) · Zbl 0217.46801
[3] [BE] Berge, C.: Graphes et hypergraphes. Dunod 1973 · Zbl 0332.05101
[4] [BN] Beardon, A.: The geometry of discrete groups. Berlin Heidelberg New York: Springer 1983
[5] [CH] Choquet, G.: Sur un type de transformation analytique... défini au moyen de fonctions harmoniques. Bull. Sci. Math.,69, 156-165 (1945) · Zbl 0063.00851
[6] [CV 1] Colin de Verdière, Y.: Empilements de cercles: convergence d’une méthode de points fixe. Forum Math.1, 395-402 (1989) · Zbl 0685.52012
[7] [CV 2] Colin de Verdière, Y.: Déformations géodésiques des triangulations de surfaces, Prépublication de l’Institut Fourier n0 161 (1990)
[8] [FY] Fary, I.: On straight line representation of planar graphs. Acta Sci. Math. SzegedII, 229-233 (1948) · Zbl 0030.17902
[9] [OPS] Osgood, Phillips, Sarnak: Extremals of determinants of Laplacians. J. Funct. Anal.80, 148-212 (1988) · Zbl 0653.53022
[10] [RS] Rodin, B., Sullivan, D.: The convergence ofcircle packings to the Riemann mapping. J. Diff. Geom.26, 349-360 (1987) · Zbl 0694.30006
[11] [SM] Schramm, O.: Existence and uniqueness of packings with specified combinatorics. Preprint UCSD (a paraitre, 1990)
[12] [ST] Stephenson, K.: Circle packings in the approximations of conformal mappings. Bull. AMS123, 407-415 (1990) · Zbl 0714.30011
[13] [S-Y] Schoen, R., Yau, S.T.: On univalent harmonic maps between surfaces. Invent. Math.44, 265-278 (1978) · Zbl 0388.58005
[14] [TH] Thurston, W.: The geometry and topology of three-manifolds. Princeton Notes, chap. 13, 1978
[15] [TO 1] Thomassen, C.: Planarity and duality of finite and infinite graphs. J. Comb. TheoryB 29, 244-271 (1980) · Zbl 0441.05023
[16] [TO 2] Thomassen, C.: Plane representations of graphs. In: Progress in graph theory, pp. 43-69. Academic press 1984 · Zbl 0554.05021
[17] [TU] Tutte, W.: How to draw a graph. Proc. Lond. Math. Soc.13, 743-768 (1963) · Zbl 0115.40805
[18] [TV] Troyanov, M.: Les surfaces euclidiennes à singularités coniques. Ens. Math.32, 79-94 (1986) · Zbl 0611.53035
[19] [ZH] Zheng,-Xu He: An estimate for hexagonal circle packings, J. Diff. Geom. (à paraître 1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.