Circle packing theorem

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.

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.

Related publications (25)

Related people (1)

Related units (4)

Related concepts (8)

Related lectures (8)

From kirigami to hydrogels: a tutorial on designing conformally transformable surfaces

Tian Chen, Yingying Ren, Yue Wang

Elastic surfaces that morph between multiple geometrical configurations are of significant engineering value, with applications ranging from the deployment of space-based PV arrays, the erection of temporary shelters, and the realization of flexible displa ...

2022

Suppressing tip vortex cavitation by winglets

Mohamed Farhat, Ali Amini, Martino Reclari

Despite the numerous remedies prescribed so far, tip vortex cavitation (TVC) remains a major issue in design and operation of diverse applications. In this paper, we experimentally investigate the effectiveness of winglets in suppressing TVC. An elliptical ...

SPRINGER2019

Graph-Based Detection of Seams In 360-Degree Images

Pascal Frossard, Francesca De Simone, Sohyeong Kim, Roberto Gerson De Albuquerque Azevedo

In this paper, we propose an algorithm to detect a specific kind of distortions, referred to as seams, which commonly occur when a 360-degree image is represented in planar domain by projecting the sphere to a polyhedron, e.g, via the Cube Map (CM) project ...

2019

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.

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. Formally, an intersection graph G is an undirected graph formed from a family of sets by creating one vertex v_i for each set S_i, and connecting two vertices v_i and v_j by an edge whenever the corresponding two sets have a nonempty intersection, that is, Any undirected graph G may be represented as an intersection graph.

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, linguistics, and bioinformatics. A drawing of a graph or network diagram is a pictorial representation of the vertices and edges of a graph. This drawing should not be confused with the graph itself: very different layouts can correspond to the same graph.

Epidemics and Bootstrap Percolation in Square Lattice COM-512: Networks out of control

Explores epidemics spread models and Bootstrap Percolation in square lattice networks, focusing on the Kolmogorov equation and probability generating functions.

Biophysics: Polymer Folding and DNA Organization

Explores polymer folding, hydrophobic interactions, and DNA organization, highlighting their biological importance.

Partial Derivatives: Understanding Tangents

Explores partial derivatives and their role in determining tangents to graphs.