Circle packing theorem
The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible patterns of tangent circles among non-overlapping circles in the plane. A circle packing is a collection of circles whose union is connected and whose interiors are disjoint. The intersection graph of a circle packing, called a coin graph, is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. 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: every finite connected simple planar graph has a circle packing in the plane whose intersection graph is isomorphic to .
A stronger form of the circle packing theorem applies to any polyhedral graph and its dual graph, and proves the existence of a primal–dual packing, circle packings for both graphs that cross at right angles. Circle packings and their tangencies, and the circle packing theorem, have been extended to arbitrary Riemannian surfaces including the sphere, the hyperbolic plane, and to surfaces of bounded genus. More generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. As a special case, the coin graphs of packings of unit circles are called penny graphs.
Circle packings have applications in conformal mapping, the construction of polyhedra, planar separator theorems, graph drawing, and the theory of random walks. The study of the tangencies of circle packings, for which the circle packing theorem is central, should be distinguished from the study of circle packings within fixed shapes but without specified tangencies, typically studied with respect to their density (the fraction of area covered by circles).