Introduction to Circle Packing

Last updated

Introduction to Circle Packing: The Theory of Discrete Analytic Functions is a mathematical monograph concerning systems of tangent circles and the circle packing theorem. It was written by Kenneth Stephenson and published in 2005 by the Cambridge University Press.

Contents

Topics

Circle packings, as studied in this book, are systems of circles that touch at tangent points but do not overlap, according to a combinatorial pattern of adjacencies specifying which pairs of circles should touch. The circle packing theorem states that a circle packing exists if and only if the pattern of adjacencies forms a planar graph; it was originally proved by Paul Koebe in the 1930s, and popularized by William Thurston, who rediscovered it in the 1970s and connected it with the theory of conformal maps and conformal geometry. [1] As a topic, this should be distinguished from sphere packing, which considers higher dimensions (here, everything is two dimensional) and is more focused on packing density than on combinatorial patterns of tangency. [2] [3]

The book is divided into four parts, in progressive levels of difficulty. [4] The first part introduces the subject visually, encouraging the reader to think about packings not just as static objects but as dynamic systems of circles that change in predictable ways when the conditions under which they are formed (their patterns of adjacency) change. The second part concerns the proof of the circle packing theorem itself, and of the associated rigidity theorem: every maximal planar graph can be associated with a circle packing that is unique up to Möbius transformations of the plane. [1] [3] More generally the same result holds for any triangulated manifold, with a circle packing on a topologically equivalent Riemann surface that is unique up to conformal equivalence. [5]

The third part of the book concerns the degrees of freedom that arise when the pattern of adjacencies is not fully triangulated (it is a planar graph, but not a maximal planar graph). In this case, different extensions of this pattern to larger maximal planar graphs will lead to different packings, which can be mapped to each other by corresponding circles. The book explores the connection between these mappings, which it calls discrete analytic functions, and the analytic functions of classical mathematical analysis. The final part of the book concerns a conjecture of William Thurston, proved by Burton Rodin and Dennis Sullivan, that makes this analogy concrete: conformal mappings from any topological disk to a circle can be approximated by filling the disk by a hexagonal packing of unit circles, finding a circle packing that adds to that pattern of adjacencies a single outer circle, and constructing the resulting discrete analytic function. This part also includes applications to number theory and the visualization of brain structure. [1] [3]

Stephenson has implemented algorithms for circle packing and used them to construct the many illustrations of the book, [5] giving to much of this work the flavor of experimental mathematics, although it is also mathematically rigorous. [4] Unsolved problems are listed throughout the book, which also includes nine appendices on related topics such as the ring lemma and Doyle spirals. [1] [3]

Audience and reception

The book presents research-level mathematics, and is aimed at professional mathematicians interested in this and related topics. Reviewer Frédéric Mathéus describes the level of the material in the book as "both mathematically rigorous and accessible to the novice mathematician", presented in an approachable style that conveys the author's love of the material. [6] However, although the preface to the book states that no background knowledge is necessary, and that the book can be read by non-mathematicians or used as an undergraduate textbook, reviewer Michele Intermont disagrees, noting that it has no exercises for students and writing that "non-mathematicians will be nothing other than frustrated with this book". [2] Similarly, reviewer David Mumford finds the first seven chapters (part I and much of part II) to be at an undergraduate level, but writes that "as a whole, the book is suitable for graduate students in math". [4]

Publication

Related Research Articles

<span class="mw-page-title-main">Discrete mathematics</span> Study of discrete mathematical structures

Discrete mathematics is the study of mathematical structures that can be considered "discrete" rather than "continuous". Objects studied in discrete mathematics include integers, graphs, and statements in logic. By contrast, discrete mathematics excludes topics in "continuous mathematics" such as real numbers, calculus or Euclidean geometry. Discrete objects can often be enumerated by integers; more formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics".

<span class="mw-page-title-main">Four color theorem</span> Statement in mathematics

In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. The proof has gained wide acceptance since then, although some doubters remain.

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Outerplanar graph</span> Non-crossing graph with vertices on outer face

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

<span class="mw-page-title-main">Midsphere</span> Sphere tangent to every edge of a polyhedron

In geometry, the midsphere or intersphere of a polyhedron is a sphere which is tangent to every edge of the polyhedron. That is to say, it touches any given edge at exactly one point. Not every polyhedron has a midsphere, but for every convex polyhedron there is a combinatorially equivalent polyhedron, the canonical polyhedron, that does have a midsphere. The radius of the midsphere is called the midradius.

In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Klaus Wagner (1936), Fáry (1948), and Sherman K. Stein (1951).

<span class="mw-page-title-main">Intersection graph</span> Graph representing intersections between given sets

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.

<span class="mw-page-title-main">Circle packing theorem</span> Describes the possible tangency relations between circles with disjoint interiors

The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles 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:

In inversive geometry, the inversive distance is a way of measuring the "distance" between two circles, regardless of whether the circles cross each other, are tangent to each other, or are disjoint from each other.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

<span class="mw-page-title-main">Imre Bárány</span> Hungarian mathematician

Imre Bárány is a Hungarian mathematician, working in combinatorics and discrete geometry. He works at the Rényi Mathematical Institute of the Hungarian Academy of Sciences, and has a part-time job at University College London.

<span class="mw-page-title-main">Pancyclic graph</span>

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

Pankaj Kumar Agarwal is an Indian computer scientist and mathematician researching algorithms in computational geometry and related areas. He is the RJR Nabisco Professor of Computer Science and Mathematics at Duke University, where he has been chair of the computer science department since 2004. He obtained his Doctor of Philosophy (Ph.D.) in computer science in 1989 from the Courant Institute of Mathematical Sciences, New York University, under the supervision of Micha Sharir.

<span class="mw-page-title-main">Apollonian network</span> Graph formed by subdivision of triangles

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

<span class="mw-page-title-main">Slope number</span> Number of edge slopes in graph drawing

In graph drawing and geometric graph theory, the slope number of a graph is the minimum possible number of distinct slopes of edges in a drawing of the graph in which vertices are represented as points in the Euclidean plane and edges are represented as line segments that do not pass through any non-incident vertex.

<span class="mw-page-title-main">Penny graph</span> Graph formed by touching unit circles

In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other, by creating a vertex for each circle and an edge for every pair of tangent circles. The circles can be represented physically by pennies, arranged without overlapping on a flat surface, with a vertex for each penny and an edge for each two pennies that touch.

Pearls in Graph Theory: A Comprehensive Introduction is an undergraduate-level textbook on graph theory, by Nora Hartsfield and Gerhard Ringel. It was published in 1990 by Academic Press, Inc., with a revised edition in 1994 and a paperback reprint of the revised edition by Dover Books in 2003. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

<span class="mw-page-title-main">Ring lemma</span>

In the geometry of circle packings in the Euclidean plane, the ring lemma gives a lower bound on the sizes of adjacent circles in a circle packing.

<span class="mw-page-title-main">Doyle spiral</span> Circle packing arranged in spirals

In the mathematics of circle packing, a Doyle spiral is a pattern of non-crossing circles in the plane in which each circle is surrounded by a ring of six tangent circles. These patterns contain spiral arms formed by circles linked through opposite points of tangency, with their centers on logarithmic spirals of three different shapes.

References

  1. 1 2 3 4 Pokas, Serguey M., "Review of Introduction to Circle Packing", zbMATH , Zbl   1074.52008
  2. 1 2 Intermont, Michele (December 2005), "Review of Introduction to Circle Packing", MAA Reviews, Mathematical Association of America
  3. 1 2 3 4 Lord, Nick (November 2006), "Review of Introduction to Circle Packing", The Mathematical Gazette , 90 (519): 554–556, doi:10.1017/S0025557200180726, JSTOR   40378239, S2CID   126249069
  4. 1 2 3 Mumford, David (January–February 2006), "Stuff it! (Review of Introduction to Circle Packing)", American Scientist , 94 (1): 84–86, doi:10.1511/2006.57.84, JSTOR   27858719
  5. 1 2 Cannon, J. W.; Floyd, W. J.; Parry, W. R. (June 2007), "Review of Introduction to Circle Packing", The Mathematical Intelligencer , 29 (3): 63–66, doi:10.1007/bf02985693, S2CID   123145356
  6. ↑ Mathéus, Frédéric (2006), "Review of Introduction to Circle Packing", Mathematical Reviews , MR   2131318
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.