Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Circle packing theorem
Summary
The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in general, on any Riemann surface) 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:
Circle packing theorem: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G.
A maximal planar graph G is a finite simple planar graph to which no more edges can be added while preserving planarity. Such a graph always has a unique planar embedding, in which every face of the embedding (including the outer face) is a triangle. In other words, every maximal planar graph G is the 1-skeleton of a simplicial complex which is homeomorphic to the sphere. The circle packing theorem guarantees the existence of a circle packing with finitely many circles whose intersection graph is isomorphic to G. As the following theorem states more formally, every maximal planar graph can have at most one packing.
Koebe–Andreev–Thurston theorem: If G is a finite maximal planar graph, then the circle packing whose tangency graph is isomorphic to G is unique, up to Möbius transformations and reflections in lines.
Thurston observes that this uniqueness is a consequence of the Mostow rigidity theorem. To see this, let G be represented by a circle packing.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.