Abstract
In an earlier work, the author extended the Andreev-Koebe-Thurston circle packing theorem. Additionally, a polynomial time algorithm for constructing primal-dual circle packings of arbitrary (essentially) 3-connected maps was found. In this note, additional details concerning surfaces of constant curvature 0 (with special emphasis on planar graphs where a slightly different treatment is necessary) are presented.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
ANDREEV E.M., “On convex polyhedra in Lobačevskiĩ spaces”, Mat. Sb. (N.S.)1 (1970) 445–478; Engl. transl. in Math. USSR Sb.10 (1970) 413–440.
ANDREEV E.M., “On convex polyhedra of finite volume, in Lobačevskiĩ space”, Mat. Sb. (N.S.)83 (1970) 256–260; Engl. tranl. in Math. USSR Sb.12 (1970) 255–259.
BRIGHTWELL G. R., SCHEINERMAN E. R., “Representations of planar graphs”, SIAM J. Disc. Math.6 (1993) 214–229.
Y. COLIN DE VERDIÈRE, “Empilements de cercles: Convergence d'une méthode de point fixe”, Forum Math.,1 (1989) 395–402.
Y. COLIN DE VERDIÈRE, “Un principe, variationnel pour les empilements des cercles”, Invent. Math.104 (1991) 655–669.
HODGSON C. D., RIVIN I., and SMITH W. D., “A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere”, Bull. Amer. Math. Soc.27 (1992) 246–251.
KOEBE P., “Kontaktprobleme auf der konformen Abbildung”, Ber. Verh. Saechs. Akad. Wiss. Leipzig, Math.-Phys. Kl.88 (1936) 141–164.
MALITZ S., PAPAKOSTAS A., “On the angular resolution of planar graphs”, SIAM J. Discrete Math.7 (1994) 172–183.
MILLER G. L., TENG S.-H., and VAVASIS S. A., “A unified geometric approach to graph separators”, Proc. 32nd Symp. on Found. of Comp. Sci. (1991) 538–547.
MOHAR B., “Circle packings of maps in polynomial time”, Europ. J. Combin.18 (1997) 785–805.
MOHAR B., THOMASSEN C., “Graphs on Surfaces”, Johns Hopkins University Press, to appear.
STEPHENSON K., “Cumulative bibliography on circle packings, electronic data base available at http://www.math.utk.edu/~kens/and a software package available through the same address.
THURSTON W. P., “The geometry and topology of 3-manifolds”, Princeton Univ. Lect. Notes, Princeton, NJ.
TUTTE W. T., “How to draw a graph”, Proc. London Math. Soc.13 (1963) 743–768.
Author information
Authors and Affiliations
Additional information
Conferenza tenuta il 24 novembre 1997
Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1-7036
This note is a supplement to the Colloquium talk of the author at the “Seminario Matematico e Fisico di Milano” in November 1997.
Rights and permissions
About this article
Cite this article
Mohar, B. Circle packings of maps —The Euclidean case. Seminario Mat. e. Fis. di Milano 67, 191–206 (1997). https://doi.org/10.1007/BF02930499
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02930499