Document Open Access Logo

On Primal-Dual Circle Representations

Authors Stefan Felsner, Günter Rote

PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.8.pdf
  • Filesize: 0.85 MB
  • 18 pages

Document Identifiers

Author Details

Stefan Felsner
Günter Rote

Cite As Get BibTex

Stefan Felsner and Günter Rote. On Primal-Dual Circle Representations. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.SOSA.2019.8

Abstract

The Koebe-Andreev-Thurston Circle Packing Theorem states that every triangulated planar graph has a contact representation by circles. The theorem has been generalized in various ways. The most prominent generalization assures the existence of a primal-dual circle representation for every 3-connected planar graph. We present a simple and elegant elementary proof of this result.

Subject Classification

Keywords
  • Disk packing
  • planar graphs
  • contact representation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nieke Aerts and Stefan Felsner. Straight Line Triangle Representations. Discr. and Comput. Geom., 57:257-280, 2017. URL: http://dx.doi.org/10.1007/s00454-016-9850-y.
  2. E. M. Andreev. Convex polyhedra in Lobačevskiĭspaces. Mat. Sb. (N.S.), 81 (123):445-478, 1970. English: Math. USSR, Sb. 10, 413-440 (1971). Google Scholar
  3. Giuseppe Di Battista and Luca Vismara. Angles of planar triangular graphs. SIAM J. Discrete Math., 9(3):349-359, August 1996. Google Scholar
  4. Marshall W. Bern and David Eppstein. Quadrilateral Meshing by Circle Packing. Int. J. Comput. Geometry Appl., 10:347-360, 2000. Google Scholar
  5. Alexander I. Bobenko and Boris A. Springborn. Variational principles for circle patterns and Koebe’s theorem. Trans. Amer. Math. Soc., 356:659-689, 2004. Google Scholar
  6. G. R. Brightwell and E. R. Scheinerman. Representations of Planar Graphs. SIAM J. Discr. Math., 6(2):214-229, 1993. Google Scholar
  7. Yves Colin de Verdière. Empilements de cercles: convergence d'une méthode de point fixe. Forum Math., 1:395-402, 1989. Google Scholar
  8. Yves Colin de Verdière. Un principe variationnel pour les empilements de cercles. Invent. Math., 104:655-669, 1991. Google Scholar
  9. Hubert de Fraysseix, Patrice Ossona de Mendez, and Pierre Rosenstiehl. On Triangle Contact Graphs. Comb., Probab. and Comput., 3(02):233-246, 1994. Google Scholar
  10. Olivier Devillers, Giuseppe Liotta, Franco P. Preparata, and Roberto Tamassia. Checking the convexity of polytopes and the planarity of subdivisions. Comput. Geom., 11(3-4):187-208, 1998. URL: http://dx.doi.org/10.1016/S0925-7721(98)00039-X.
  11. David Eppstein. Diamond-Kite Meshes: Adaptive Quadrilateral Meshing and Orthogonal Circle Packing. In Proc. Mesh. Roundtable, pages 261-277. Springer, 2012. Google Scholar
  12. David Eppstein. A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing. Discrete Comput. Geom., 52:515-550, 2014. Google Scholar
  13. Stefan Felsner. Rectangle and Square Representations of Planar Graphs. In J. Pach, editor, Thirty Essays in Geometric Graph Theory, pages 213-248. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4614-0110-0_12.
  14. Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze, and Manfred Scheucher. Strongly Monotone Drawings of Planar Graphs. In Proc. 32nd Intern. Symp. Comput. Geom. (SoCG 2016), volume 51 of LIPIcs, pages 37:1-15, 2016. Google Scholar
  15. Stefan Felsner, Hendrik Schrezenmaier, and Raphael Steiner. Equiangular polygon contact representations, 2017. http://page.math.tu-berlin.de/~felsner/Paper/kgons.pdf. Google Scholar
  16. Stefan Felsner, Hendrik Schrezenmaier, and Raphael Steiner. Pentagon Contact Representations. Electronic J. Combin., 25(3):article #P3.39, 38 pp., 2018. Google Scholar
  17. Daniel Gonçalves, Benjamin Lévêque, and Alexandre Pinlou. Triangle Contact Representations and Duality. Discr. and Comput. Geom., 48(1):239-254, 2012. Google Scholar
  18. S. Har-Peled. A Simple Proof of the Existence of a Planar Separator. arXiv:http://arxiv.org/abs/1105.0103, 2011.
  19. Nora Hartsfield and Gerhard Ringel. Pearls in Graph Theory: A Comprehensive Introduction. Academic Press, 1990. Google Scholar
  20. Brad Jackson and Gerhard Ringel. Colorings of circles. Amer. Math. Monthly, 91:42-49, 1984. Google Scholar
  21. Paul Koebe. Kontaktprobleme der konformen Abbildung. Ber. Verh. Sächs. Akad. Leipzig, Math.-Phys. Klasse, 88:141-164, 1936. Google Scholar
  22. László Lovász. Geometric Representations of Graphs. http://web.cs.elte.hu/~lovasz/geomrep.pdf, December 2009. Draft version. Google Scholar
  23. Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. ACM, 44(1):1-29, 1997. Google Scholar
  24. B. Mohar. Circle packings of maps in polynomial time. Europ. J. Comb., 18:785-805, 1997. Google Scholar
  25. Bojan Mohar. Circle packings of maps - the Euclidean case. Rend. Sem. Mat. Fis. Milano, 67:191-206, 2000. Google Scholar
  26. David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, and Walter Whiteley. Non-crossing frameworks with non-crossing reciprocals. Discrete and Computational Geometry, 32:567-600, 2004. URL: http://dx.doi.org/10.1007/s00454-004-1139-x.
  27. János Pach and Pankaj K. Agarwal. Combinatorial Geometry. John Wiley &Sons, 1995. Google Scholar
  28. Gerhard Ringel. 250 Jahre Graphentheorie. In Graphs in research and teaching, pages 136-152. Franzbecker, 1985. Google Scholar
  29. Burt Rodin and Dennis Sullivan. The convergence of circle packings to the Riemann mapping. J. Differential Geom., 26:349-360, 1987. Google Scholar
  30. Günter Rote, Francisco Santos, and Ileana Streinu. Pseudo-triangulations - a survey. In Jacob E. Goodman, János Pach, and Richard Pollack, editors, Surveys on Discrete and Computational Geometry - Twenty Years Later, volume 453 of Contemporary Mathematics, pages 343-410. American Mathematical Society, 2008. URL: http://arxiv.org/abs/math/0612672.
  31. H. Sachs. Coin Graphs, Polyhedra, and Conformal Mapping. Discr. Math., 134:133-138, 1994. Google Scholar
  32. Oded Schramm. How to Cage an Egg. Invent. Math., 107:534-560, 1992. Google Scholar
  33. Oded Schramm. Square tilings with prescribed combinatorics. Isr. J. Math., 84:97-118, 1993. Google Scholar
  34. Oded Schramm. Combinatorically Prescribed Packings and Applications to Conformal and Quasiconformal Maps. arXiv:http://arxiv.org/abs/0709.0710, 2007. Modified version of PhD thesis from 1990.
  35. Kenneth Stephenson. Circle packing: a mathematical tale. Notices Amer. Math. Soc., 50:1376-1388, 2003. Google Scholar
  36. Kenneth Stephenson. Introduction to Circle Packing: The Theory of Discrete Analytic Functions. Cambridge Univ. Press, 2005. Google Scholar
  37. William Thurston. Geometry and Topology of Three-Manifolds. Princeton Univ., 1980. Lecture Notes. Electronic edition: http://library.msri.org/books/gt3m/. Google Scholar
  38. W. T. Tutte. How to draw a graph. Proc. London Math. Soc. (Ser. 3), 13:743-767, 1963. Google Scholar
  39. G. Wegner. Problems in geometric convexity: Problem 86. In J. Tölke and J. M. Wills, editors, Contributions to Geometry. Proceedings of the Geometry Symposium in Siegen 1978, page 274. Birkhäuser, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact