Teorema de empaquetamiento de círculos

El teorema del empaquetamiento de círculos (también conocido como teorema de Koebe-Andreev-Thurston ) describe los posibles patrones de círculos tangentes entre círculos que no se superponen en el plano. Un empaquetamiento de círculos es una colección de círculos cuya unión es conexa y cuyos interiores son disjuntos. El grafo de intersección de un empaquetamiento de círculos, llamado grafo moneda , ^{[ 1 ]} es el grafo que tiene un vértice por cada círculo y una arista por cada par de círculos que son tangentes . Los grafos moneda son siempre conexos, simples y planares . El teorema del empaquetamiento de círculos establece que estos son los únicos requisitos para que un grafo sea un grafo moneda: todo grafo finito, conexo, simple y planar.${\displaystyle G}$tiene un empaquetamiento circular en el plano cuyo grafo de intersección es isomorfo a${\displaystyle G}$.

Una forma más fuerte del teorema de empaquetamiento de círculos se aplica a cualquier grafo poliédrico y su grafo dual , y prueba la existencia de un empaquetamiento primal-dual , empaquetamientos de círculos para ambos grafos que se cruzan en ángulo recto. Los empaquetamientos de círculos y sus tangencias, y el teorema de empaquetamiento de círculos, se han extendido a superficies riemannianas arbitrarias , incluyendo la esfera, el plano hiperbólico y a superficies de género acotado . De manera más general, los grafos de intersección de objetos geométricos disjuntos en el interior se denominan grafos de tangencia ^{[ 2 ]} o grafos de contacto . ^{[ 3 ]} Como caso especial, los grafos de monedas de empaquetamientos de círculos unitarios se denominan grafos de peniques . ^{[ 4 ]}

Los empaquetamientos de círculos tienen aplicaciones en el mapeo conforme , la construcción de poliedros , los teoremas de separación planar , el dibujo de grafos y la teoría de caminatas aleatorias . El estudio de las tangencias de los empaquetamientos de círculos, para el cual el teorema de empaquetamiento de círculos es fundamental, debe distinguirse del estudio de los empaquetamientos de círculos dentro de formas fijas pero sin tangencias especificadas, que generalmente se estudian con respecto a su densidad (la fracción del área cubierta por círculos).

Un grafo planar maximal${\displaystyle G}$es un grafo planar simple finito al que no se pueden agregar más aristas sin preservar la planaridad. Puede estar incrustado en el plano con diferentes elecciones de la cara exterior, pero todas esas incrustaciones comparten el mismo conjunto de caras (incluida la cara exterior) que deben ser todas triángulos. El teorema del empaquetamiento de círculos garantiza la existencia de un empaquetamiento de círculos con un número finito de círculos cuyo grafo de intersección es isomorfo a${\displaystyle G}$Como lo establece más formalmente el siguiente teorema, todo grafo planar maximal puede tener como máximo un empaquetamiento. ^{[ 5 ]}

Las transformaciones geométricas en la parte de unicidad del teorema, reflexiones y transformación de Möbius, preservan los círculos y, por lo tanto, el grafo de tangencia de cualquier sistema de círculos. ^{[ 7 ]} Unicidad significa que, para cualesquiera dos empaquetamientos del mismo grafo planar maximal, existe una transformación de estos tipos que transforma un empaquetamiento en el otro. Para cada grafo planar finito${\displaystyle G}$, es posible agregar vértices a${\displaystyle G}$construir un grafo planar maximal más grande en el que${\displaystyle G}$es un subgrafo inducido . Construir un empaquetamiento de círculos a partir de este grafo más grande y luego eliminar los círculos de los vértices añadidos produce un empaquetamiento de círculos para${\displaystyle G}$Esto permite derivar la existencia de empaquetamientos circulares para grafos planares arbitrarios a partir del caso especial de grafos planares maximales. ^{[ 8 ]}

Generalizaciones

Empaquetamiento circular localmente finito periódico infinito

Una espiral de Doyle , no localmente finita en el centro de la espiral.

Una versión del empaquetamiento de círculos se aplica a algunos grafos infinitos . En particular, una triangulación planar infinita de un disco abierto tiene un empaquetamiento localmente finito en el plano euclidiano o en el plano hiperbólico (pero no en ambos). Aquí, localmente finito significa que cada punto del plano tiene un entorno que interseca solo un número finito de círculos. En el caso euclidiano, el empaquetamiento es único salvo similitud ; en el caso hiperbólico, es único salvo isometría . ^{[ 18 ]}

El teorema del empaquetamiento de círculos se generaliza a grafos que no son planares. Si${\displaystyle G}$es un gráfico que se puede incrustar en una superficie${\displaystyle S}$(más precisamente, una 2-variedad orientable ), entonces existe una métrica riemanniana de curvatura constante.${\displaystyle d}$en${\displaystyle S}$y un empaquetamiento circular en${\displaystyle (S,d)}$cuyo grafo de contacto es isomorfo a${\displaystyle G}$. Si${\displaystyle S}$es cerrado ( compacto y sin frontera ) y${\displaystyle G}$es una triangulación de${\displaystyle S}$, entonces${\displaystyle (S,d)}$y el empaquetado es único salvo equivalencia conforme. Si${\displaystyle S}$Si es una esfera, entonces su geometría es esférica y la equivalencia se da salvo transformaciones de Möbius. Si es un toro, la geometría es localmente euclidiana (como un toro plano ), y la equivalencia se da salvo escalamiento por una constante e isometrías. Si${\displaystyle S}$tiene género al menos 2, entonces la geometría es localmente hiperbólica y la equivalencia es salvo isometrías. ^{[ 19 ]}

Otra generalización del teorema de empaquetamiento de círculos implica reemplazar la condición de tangencia con un ángulo de intersección especificado entre círculos correspondientes a vértices vecinos. Una versión es la siguiente. Supongamos que${\displaystyle G}$es un grafo planar finito 3-conexo (es decir, un grafo poliédrico ), entonces hay un par de empaquetamientos circulares primal-dual : un empaquetamiento cuyo grafo de intersección es isomorfo a${\displaystyle G}$y otro cuyo grafo de intersección es isomorfo al dual planar de${\displaystyle G}$, de tal manera que para cada vértice en${\displaystyle G}$y cara adyacente a él, el círculo en el primer empaquetamiento correspondiente al vértice interseca ortogonalmente con el círculo en el segundo empaquetamiento correspondiente a la cara. ^{[ 20 ]} Por ejemplo, al aplicar este resultado al grafo del tetraedro se obtiene, para cualesquiera cuatro círculos mutuamente tangentes, un segundo conjunto de cuatro círculos mutuamente tangentes, cada uno de los cuales es ortogonal a tres de los cuatro primeros. ^{[ 21 ]} El empaquetamiento de círculos para un grafo planar maximal es automáticamente parte de un par de empaquetamientos de círculos primal-dual, porque cada triplete de círculos tangentes en el empaquetamiento primal tiene un círculo dual que pasa en ángulo recto por sus tres puntos de tangencia. Al igual que el empaquetamiento de círculos para un grafo planar maximal, los empaquetamientos de círculos primal-dual son únicos salvo reflexiones y transformaciones de Möbius. ^{[ 22 ]} Una generalización adicional, reemplazando el ángulo de intersección por la distancia inversa , permite la especificación de empaquetamientos en los que se requiere que algunos círculos sean disjuntos entre sí en lugar de cruzarse o ser tangentes. ^{[ 23 ]}

Otra variedad de generalizaciones permite formas distintas a los círculos. ^{[ 3 ]} Supongamos que cada vértice${\displaystyle v}$de un grafo planar finito${\displaystyle G}$corresponde a un conjunto convexo suave${\displaystyle K_{v}\subset \mathbb {R} ^{2}}$Luego viene el embalaje.${\displaystyle P=(K'_{v}:v\in V)}$en el plano cuyas tangencias se corresponden uno a uno con los bordes de${\displaystyle G}$donde cada conjunto${\displaystyle K'_{v}}$se obtiene de${\displaystyle K_{v}}$mediante traslación y escalado . Este resultado es un caso especial del "teorema de empaquetamiento de monstruos" de Schramm. ^{[ 24 ]} El "monstruo" del teorema es un árbol de expansión del grafo dado, con una función para cada vértice que especifica cómo la forma con la que debe empaquetarse depende de las posiciones relativas de las tangencias alrededor de todas las formas, satisfaciendo ciertas condiciones de consistencia. Para demostrar que los monstruos siempre pueden empaquetarse, Schramm siguió la demostración de Thurston del teorema de empaquetamiento de círculos, utilizando el teorema del punto fijo de Brouwer. Escribió que "Uno puede ver al terrible monstruo agitando sus brazos con pura rabia, los tentáculos causando un silbido espantoso, al frotarse entre sí". ^{[ 25 ]}

En lugar de partir de una incrustación topológica de un grafo y buscar una superficie con geometría uniforme en la que dicho grafo pueda representarse mediante un empaquetamiento de círculos, varios autores han estudiado una versión inversa de esta cuestión: ¿qué superficies uniformes admiten empaquetamientos triangulados , es decir, empaquetamientos de círculos en los que cada espacio entre círculos es un triángulo circular con cuernos rodeado por tres círculos tangentes? Según la parte de unicidad del teorema del empaquetamiento de círculos, cada empaquetamiento está determinado de forma única (salvo simetrías de la superficie) por su grafo de tangencias, pero para este problema, el grafo de tangencias se determina a partir de la geometría, y no al revés. ^{[ 30 ]}

Entre los empaquetamientos triangulados infinitos periódicos del plano euclidiano, solo hay un empaquetamiento triangulado con un único radio, el empaquetamiento hexagonal. Hay nueve pares de radios distintos (normalizados de modo que el radio máximo sea uno) y 164 tríos de radios que forman empaquetamientos triangulados. En general, el número de${\displaystyle k}$Las tuplas de radios que pueden formar un empaquetamiento triangulado son finitas, pero con una tasa de crecimiento desconocida en función de${\displaystyle k}$[ ^{31 ] La relación entre el radio más pequeño y el} más grande es como máximo 0,701 para cualquier empaquetamiento triangulado distinto del hexagonal, para el cual esta relación es 1. Existe un empaquetamiento con una relación de radios de aproximadamente 0,651, con tres radios distintos; Robert Connelly y Zhen Zhang han conjeturado que tiene la mayor relación de radios posible de cualquier empaquetamiento triangulado no hexagonal. ^{[ 32 ]}

En 1986, Robert Brooks describió un método para asociar continuamente un número real como un invariante de un rectángulo circular , la región${\displaystyle R}$delimitado por un ciclo de cuatro círculos tangentes (a los que se les pueden dar las simetrías de un rectángulo mediante una transformación de Möbius), de tal manera que cuando el invariante es un número racional , el rectángulo tiene un empaquetamiento triangulado. Su método primero empaqueta una cadena de círculos tangentes a los lados superior e inferior de${\displaystyle R}$, con el círculo más a la izquierda en la cadena tangente al lado izquierdo de${\displaystyle R}$; dejar${\displaystyle r_{1}}$sea ​​el número de círculos que se pueden empaquetar de esta manera sin superponer el lado derecho de${\displaystyle R}$Esta cadena deja un rectángulo circular más pequeño entre su círculo más a la derecha y el lado derecho del rectángulo inicial; rellene este rectángulo recursivamente de la misma manera con otra cadena de círculos, tangentes a sus lados izquierdo y derecho, y deje${\displaystyle r_{2}}$Sea el número de círculos en esta segunda cadena. Este proceso de empaquetamiento puede continuar indefinidamente, dando como resultado una secuencia infinita de enteros positivos.${\displaystyle r_{i}}$, el número de círculos en cada cadena, o puede terminar después de un número finito de etapas con un empaquetamiento triangulado. En cualquier caso, Brooks define su invariante${\displaystyle r(R)}$ser la fracción continua simple$${\displaystyle r(R)=r_{1}+{\frac {1}{r_{2}+{\frac {1}{r_{3}+\cdots }}}}.}$$Este es un número racional si y solo si este proceso de empaquetamiento termina con un empaquetamiento triangulado finito. ^{[ 30 ] [ 33 ]}

No toda superficie uniforme admite un empaquetamiento triangulado. Por ejemplo, en el caso de toros planos (los espacios cociente del plano euclidiano por una red , obtenidos al pegar aristas opuestas de un paralelogramo ), la geometría puede variar continuamente, pero, debido a la unicidad de los empaquetamientos de círculos toroidales, solo un número numerable de toros distintos (salvo escalado) tienen empaquetamientos triangulados, y en particular deben tener formas que puedan describirse mediante números algebraicos . ^{[ 34 ]} Sin embargo, Brooks demostró que, para cada género posible de superficies compactas, las superficies que tienen empaquetamientos triangulados forman un conjunto denso en el espacio de Teichmüller de todas las superficies con ese género. Esto significa que, para cualquier superficie compacta uniforme dada, existe otra superficie compacta uniforme, con casi la misma geometría, en la que existe un empaquetamiento triangulado. Para demostrar esto, Brooks considera primero empaquetamientos en los que todos los huecos entre triángulos tienen tres o cuatro lados, que pueden obtenerse colocando círculos para dividir los huecos con más lados en piezas con menos lados. Luego, deforma cada rectángulo circular obtenido de esta manera en un rectángulo cercano cuyo invariante es racional para obtener un empaquetamiento triangulado dentro de cada uno de los rectángulos deformados. Esto produce una triangulación de toda la superficie que, según el teorema del empaquetamiento de círculos, puede representarse mediante un empaquetamiento de círculos en una superficie uniforme diferente, ligeramente deformada con respecto a la superficie dada. ^{[ 30 ]}

El teorema del empaquetamiento de círculos es una herramienta útil para problemas que incluyen mapas conformes , realización poliédrica de grafos , el teorema del separador planar , dibujo de grafos , caminatas aleatorias en grafos planares y la visualización del cerebro humano .

Mapeo conforme

Una aplicación conforme entre dos conjuntos abiertos en el plano o en un espacio de dimensiones superiores es una función continua de un conjunto al otro que preserva los ángulos entre cualesquiera dos curvas. El teorema de la aplicación de Riemann , formulado por Bernhard Riemann en 1851, establece que, para cualesquiera dos discos topológicos abiertos en el plano, existe una aplicación conforme de un disco al otro. Las aplicaciones conformes tienen aplicaciones en la generación de mallas , la proyección de mapas y otras áreas. Sin embargo, no siempre es fácil construir una aplicación conforme entre dos dominios dados de forma explícita. ^{[ 35 ]}

Una construcción de William Thurston utiliza empaquetamientos circulares para aproximar mapeos conformes. ^{[ 36 ]} Más precisamente, esta construcción mapea un disco abierto arbitrario${\displaystyle A}$al interior${\displaystyle C}$de un círculo; el mapeo de un disco topológico${\displaystyle A}$a otro disco${\displaystyle B}$podría entonces encontrarse componiendo el mapa de${\displaystyle A}$a${\displaystyle C}$con la inversa del mapa de${\displaystyle B}$a${\displaystyle C}$. ^{[ 35 ]} La idea de Thurston era agrupar círculos de un radio pequeño.${\displaystyle r}$en una teselación hexagonal del plano, dentro de la región${\displaystyle A}$, dejando una región estrecha cerca del límite de${\displaystyle A}$, de ancho${\displaystyle r}$donde ya no caben más círculos de este radio. Luego construye un grafo planar maximal${\displaystyle G}$a partir del grafo de intersección de los círculos, junto con un vértice adicional adyacente a todos los círculos en el límite del empaquetamiento. Por el teorema del empaquetamiento de círculos, este grafo planar puede representarse mediante un empaquetamiento de círculos dentro de un círculo${\displaystyle C}$en el que todas las aristas (incluidas las incidentes al vértice del límite) están representadas por tangencias de círculos. Los círculos del empaquetamiento de${\displaystyle A}$corresponder uno a uno con los círculos dentro${\displaystyle C}$, con el círculo que forma el límite de${\displaystyle C}$correspondiente al límite de${\displaystyle A}$. ^{[ 35 ]}

Esta correspondencia de círculos se puede utilizar para construir una función continua a partir de${\displaystyle A}$al interior de${\displaystyle C}$en la que cada círculo y cada espacio entre tres círculos se mapea de un empaquetamiento a otro mediante una transformación de Möbius . Como${\displaystyle n}$va al infinito, la función${\displaystyle f_{n}}$determinado utilizando el método de Thurston a partir de empaquetamientos hexagonales de radio-${\displaystyle 1/n}$Los círculos convergen uniformemente en subconjuntos compactos de${\displaystyle A}$a un mapeo conforme desde${\displaystyle A}$a${\displaystyle C}$. ^{[ 37 ] [ 35 ]} De manera más general, esto se cumple para secuencias de empaquetamientos que no son necesariamente empaquetamientos hexagonales, siempre que la secuencia de radios máximos de los empaquetamientos converja a cero. ^{[ 38 ]} Un método alternativo empaqueta hexagonalmente círculos de radio pequeño en${\displaystyle C}$y construye un empaquetamiento combinatoriamente equivalente de círculos en${\displaystyle A}$, tangente a su frontera; converge de la misma manera. ^{[ 39 ]} Las aplicaciones prácticas de este método se han visto obstaculizadas por la dificultad de calcular empaquetamientos de círculos y por su tasa de convergencia relativamente lenta. ^{[ 40 ]} Sin embargo, tiene algunas ventajas cuando se aplica a dominios no simplemente conexos y en la selección de aproximaciones iniciales para técnicas numéricas que calculan mapeos de Schwarz-Christoffel , una técnica diferente para el mapeo conforme de dominios poligonales . ^{[ 35 ]}

Esta construcción de mapas conformes aproximados también puede describirse en términos de proporcionar una geometría uniforme a una superficie topológica, y puede extenderse desde la superficie misma a otros objetos incrustados en ella. Un ejemplo proviene de los dibujos infantiles , un cierto tipo de incrustación de grafos utilizada en geometría algebraica para estudiar superficies de Riemann y el grupo de Galois absoluto . Estos vienen automáticamente con una triangulación, dentro de la cual el dibujo es un subconjunto de las aristas, pero estas triangulaciones pueden formar multigrafos en lugar de grafos simples. Al aplicar el teorema de empaquetamiento de círculos a subdivisiones de estas triangulaciones, se puede construir una aproximación del dibujo en una superficie de geometría uniforme. ^{[ 35 ] [ 41 ]}

Realización poliédrica y separadores planares

El empaquetamiento primal-dual de cualquier grafo poliédrico se puede elevar del plano a una esfera mediante proyección estereográfica . A continuación, se puede utilizar para construir un poliedro convexo cuyos vértices y aristas sean el grafo dado y que posea una esfera media , una esfera tangente a todas las aristas del poliedro . Cada vértice del poliedro se encuentra fuera de la esfera, en el vértice de un cono tangente a la esfera a lo largo del círculo correspondiente a dicho vértice. Este círculo forma el horizonte en la esfera, visto desde el vértice. Cada cara del poliedro se encuentra en el plano que pasa por su círculo correspondiente. Cada arista del poliedro pasa de un vértice de cono a otro a través del punto de tangencia de dos círculos, donde ambos conos son tangentes a la esfera. Por el contrario, si un poliedro tiene una esfera media, entonces los círculos formados por las intersecciones de la esfera con las caras del poliedro y los círculos formados por los horizontes en la esfera vistos desde cada vértice del poliedro forman un empaquetamiento dual de este tipo. ^{[ 47 ]}

Las transformaciones de Möbius de la esfera conducen a realizaciones de poliedros geométricamente diferentes. Una realización particular, llamada poliedro canónico , se obtiene utilizando una esfera unitaria y eligiendo una transformación de Möbius que hace que el centro de la esfera coincida con el centroide de los puntos de tangencia de las aristas del poliedro. Todos los poliedros combinatoriamente equivalentes producirán de esta manera el mismo poliedro canónico, salvo rotaciones de la esfera. ^{[ 48 ]} Una demostración alternativa del teorema del separador planar , demostrado originalmente de una manera diferente por Lipton y Tarjan, ^{[ 49 ]} utiliza una idea similar de aplicar una transformación de Möbius a un empaquetamiento de círculos esféricos. La construcción obtiene un empaquetamiento de círculos en una esfera, que representa el grafo dado. A continuación, se utiliza una transformación de Möbius de la esfera para transformar un punto central de los centros de los círculos, un punto en el espacio tal que cada plano que pasa por el punto central divide el${\displaystyle n}$se divide en dos subconjuntos, cada uno con un tamaño${\displaystyle \leq 3n/4}$, para coincidir con el centro de la esfera. Un plano uniformemente aleatorio que pasa por el centro de la esfera interseca${\displaystyle O({\sqrt {n}})}$de los círculos de cualquier empaque de${\displaystyle n}$círculos, en expectativa. Para el empaquetamiento de círculos con el punto central en el centro de la esfera, los vértices correspondientes a estos círculos intersecados forman un separador que, cuando se elimina del grafo, deja subgrafos conectados de como máximo${\displaystyle 3n/4}$vértices. ^{[ 50 ]} El empaquetamiento de círculos también se ha utilizado para explicar el éxito de los métodos espectrales para construir separadores para grafos de género acotado y grado acotado . ^{[ 51 ]}

Cuando existe un empaquetamiento de círculos, este existe con números algebraicos para su centro y radios, resolviendo un sistema de ecuaciones cuadráticas que representan los requisitos de que cada par de centros de círculos tangentes estén a una distancia entre sí igual a la suma de sus radios. ^{[ 34 ]} Por lo tanto, en principio, es posible encontrar empaquetamientos de círculos utilizando métodos de cálculo simbólico para resolver sistemas de ecuaciones polinómicas, como el método de base de Gröbner . Sin embargo, este enfoque puede requerir la solución de ecuaciones polinómicas de alto grado, con grupos de Galois irresolubles . En cambio, los investigadores se han centrado en métodos numéricos más eficientes para encontrar aproximaciones precisas a los centros y radios de los empaquetamientos de círculos. ^{[ 58 ]}

Uno de los primeros y más versátiles resultados de aproximación, anunciado por Bojan Mohar en 1993 con detalles en dos artículos posteriores, puede utilizarse para encontrar empaquetamientos de círculos primales-duales en superficies de género arbitrario, en tiempo polinomial en el número de círculos y en el número de bits de precisión utilizados para especificar la salida con la exactitud deseada. El algoritmo de Mohar es un método iterativo aplicado al sistema de radios de un empaquetamiento de círculos primales-duales, partiendo de un sistema inicial de radios impreciso. Considera los cuadriláteros ortodiagonales formados por cada par de aristas primales y duales que se cruzan. A partir de un sistema de radios, se pueden calcular los ángulos de estos cuadriláteros (si los círculos pudieran empaquetarse con estos radios): para que un sistema de radios forme un empaquetamiento, estos ángulos deben sumar${\displaystyle 2\pi }$alrededor de cada vértice. Para sistemas de radios que no dan las sumas correctas, Mohar divide los radios en un subconjunto de radios que son demasiado grandes (los ángulos alrededor de ese vértice suman menos de${\displaystyle 2\pi }$y un subconjunto complementario de radios que son demasiado pequeños, y utiliza el método de bisección para encontrar dos parámetros.${\displaystyle \beta }$y${\displaystyle \gamma }$de tal manera que multiplicar los radios grandes por ${\displaystyle \beta }$y los radios pequeños por${\displaystyle \gamma }$reduce el error cuadrático medio entre las sumas de los ángulos y${\displaystyle 2\pi }$Tras un número suficiente de repeticiones de este proceso, se obtiene un sistema preciso de radios. Mohar utiliza estos radios para ubicar los centros de los círculos, partiendo de un cuadrilátero primal-dual y utilizando los centros ya ubicados de cada cuadrilátero y los radios de sus círculos para determinar la ubicación de los centros restantes. Aunque Mohar afirma que el algoritmo se ejecuta en tiempo polinomial, no especifica explícitamente su límite de tiempo polinomial. ^{[ 59 ]} Un estudio posterior sugirió que la complejidad computacional del algoritmo de empaquetamiento de Mohar es al menos quíntica en el número de círculos a empaquetar. ^{[ 60 ]}

^{Charles Collins y Kenneth Stephenson [ 61 ]} propusieron un método iterativo más sencillo que modifica solo un radio de círculo a la vez, calculando nuevamente el sistema de radios de círculo antes de usar los radios para ubicar los centros de los círculos. La versión del problema de empaquetamiento de círculos que resuelven produce un empaquetamiento de círculos en el plano euclidiano para un grafo planar maximal, con un triángulo exterior especificado y con radios especificados para los tres círculos de este triángulo. Comienzan con un conjunto de radios tentativos que no corresponden a un empaquetamiento válido y luego realizan repetidamente los siguientes pasos:

1. Elige un vértice interno${\displaystyle v}$del gráfico de entrada.
2. Calcula el ángulo total${\displaystyle \theta }$que su${\displaystyle k}$Los círculos vecinos cubrirían alrededor del círculo para${\displaystyle v}$, si los vecinos se colocaran tangentes entre sí y al círculo central utilizando sus radios tentativos.
3. Determinar un radio representativo${\displaystyle r}$para los círculos vecinos, de tal manera que${\displaystyle k}$círculos de radio${\displaystyle r}$daría el mismo ángulo de cobertura${\displaystyle \theta }$como los vecinos de${\displaystyle v}$dar.
4. Establezca el nuevo radio para${\displaystyle v}$ser el valor para el cual${\displaystyle k}$círculos de radio${\displaystyle r}$daría un ángulo de cobertura de exactamente${\displaystyle 2\pi }$.

Cada uno de estos pasos puede realizarse con cálculos trigonométricos sencillos. Collins y Stephenson demuestran que, aplicado solo a un único vértice, este método converge rápidamente a un radio que proporciona un ángulo de cobertura.${\displaystyle 2\pi }$Además, argumentan que el sistema también converge globalmente a un sistema consistente de radios, y proporcionan experimentos computacionales que sugieren que la rápida convergencia local de este método se extiende a una rápida convergencia global de todo el sistema de radios. Una vez que el sistema ha convergido, los círculos pueden colocarse uno a uno, de forma similar al algoritmo de Mohar, utilizando en cada paso las posiciones y los radios de dos círculos vecinos para determinar el centro de cada círculo sucesivo. ^{[ 61 ]}

Otro algoritmo, desarrollado por Gerald L. Orick, Stephenson y Collins en 2017 ^{[ 62 ],} se aplicó a los mismos empaquetamientos planares que el trabajo original de Collins y Stephenson en 2003 y aproxima simultáneamente y de forma iterativa tanto el sistema de radios como el de centros de círculo. Alterna entre pasos que utilizan una incrustación de Tutte ponderada para ubicar los centros y otros que utilizan los centros de círculo resultantes para determinar radios mejorados. Si bien no ofrecen garantías teóricas sobre el rendimiento de este algoritmo, Orick et al. afirman que sus experimentos muestran una convergencia lineal a un empaquetamiento consistente en la práctica, lo que, de ser cierto, conduciría a un límite de tiempo polinomial. ^{[ 62 ]}

El caso de encontrar empaquetamientos planares para grafos planares máximos fue revisado en 2020 por Lee Sally, Yin Lee y Kent Quanrud, ^{[ 60 ]} pero utilizaron una cota de tiempo explícita. Aunque se centraron solo en un empaquetamiento de círculos primales, trabajan con el sistema de radios de un empaquetamiento primal-dual, solo para grafos planares máximos, con un círculo dual para cada cara triangular del grafo. Al igual que Mohar, utilizan cuadriláteros ortodiagonales determinados por pares de cruces de aristas primales y duales, con ángulos calculados a partir de un sistema de radios dado, que para un sistema de radios válido debe sumar${\displaystyle 2\pi }$en cada vértice. Siguiendo el trabajo de Colin de Verdière de 1991, ^{[ 13 ]} plantearon un problema de optimización convexa en el que las variables a optimizar son los logaritmos de los radios del empaquetamiento primal-dual, y la función convexa a minimizar combina términos que son lineales en estas variables y en las antiderivadas de las arcotangentes de las razones de los radios. Demuestran que el minimizador de esta función proporciona un sistema de radios que cumplen las condiciones de un empaquetamiento circular en el que los ángulos de los cuadriláteros alrededor de cada vértice suman${\displaystyle 2\pi }$Al encontrar un árbol de expansión del grafo de círculos ortogonales en el empaquetamiento con la propiedad de que cada arista del árbol de expansión conecta círculos cuyos radios no están demasiado alejados entre sí, demuestran que esta función es fuertemente convexa cerca de su mínimo, lo que permite la aplicación de métodos potentes de programación convexa. Basándose en estas técnicas, dan una cota de tiempo para encontrar un empaquetamiento de $${\displaystyle {\tilde {O}}\left(n\log {\frac {R}{\varepsilon }}\right),}$$ donde el${\displaystyle {\tilde {O}}}$es una forma de notación O grande que suprime los términos que son logarítmicos en su argumento,${\displaystyle n}$es el número de círculos a empaquetar,${\displaystyle R}$es la relación entre el radio más grande y el más pequeño en el empaquetamiento resultante (que puede ser en el peor de los casos exponencial en${\displaystyle n}$), y${\displaystyle \varepsilon }$es un parámetro que controla cuán precisa debe ser la aproximación numérica al empaquetamiento. Todos los radios calculados están dentro de un${\displaystyle 1+\varepsilon }$factor del radio de un empaquetamiento de círculos exacto, y todos los centros calculados están a una distancia de los centros de un empaquetamiento de círculos exacto que es como máximo${\displaystyle \varepsilon }$veces el radio del círculo más pequeño. ^{[ 60 ]}

El concepto de empaquetamientos circulares se utiliza en aplicaciones de enrutamiento basadas en posición con equilibrio de carga . Un grupo de científicos informáticos del que formaba parte Jie Gao desarrolló un enfoque que utiliza un algoritmo numérico distribuido , basado en un flujo de Ricci discreto, para construir empaquetamientos circulares primales-duales aproximados en una esfera, a partir de los cuales se derivan poliedros de esfera media. ^{[ 63 ]} Estos poliedros soportan un esquema desarrollado por los científicos informáticos Christos Papadimitriou y David Ratajczak donde los mensajes pueden reenviarse de un vértice a un vértice vecino de este poliedro de manera que siempre aumente el producto interno de las coordenadas tridimensionales de la ubicación actual y el destino. La existencia de una esfera media garantiza que el mensaje finalmente llegue a su destino. ^{[ 64 ] [ 63 ]}

Una junta apolínea , mencionada por Leibniz en 1706.

Imagen de 1911 de una espiral de Doyle procedente de un artículo sobre el crecimiento de las plantas.

Stephenson escribe que "de hecho hay una larga tradición detrás de nuestra historia" y atribuye el familiar empaquetamiento hexagonal de círculos congruentes al folclore. ^{[ 65 ]} Otros trabajos tempranos sobre empaquetamientos de círculos con patrones específicos de tangencia incluyen:

• El teorema de Descartes sobre los radios de cuatro círculos mutuamente tangentes, enunciado por René Descartes en 1643 ^{[ 66 ]} y por el matemático japonés Yamaji Nushizumi en 1751. ^{[ 67 ]}
• Una variante de la junta apolínea , un empaquetamiento circular fractal infinito formado al colocar repetidamente un círculo dentro de cada triángulo circular entre círculos más grandes en el empaquetamiento, se menciona en una carta de Leibniz de 1706. ^{[ 68 ]}
• El trabajo de Arnold Emch de 1910 sobre las espirales de Doyle en las matemáticas del crecimiento de las plantas ( filotaxis ). ^{[ 69 ]}

El teorema del empaquetamiento de círculos fue enunciado y demostrado por primera vez por Koebe en 1936. ^{[ 70 ]} Thurston mencionó resultados sobre el teorema del empaquetamiento de círculos en una charla de 1978 en el Congreso Internacional de Matemáticos , y señaló que se derivaba del trabajo de EM Andreev . ^{[ 71 ] [ 72 ] [ 73 ]} En el mismo año, Gerd Wegner también conjeturó que el teorema del empaquetamiento de círculos se cumple. ^{[ 74 ]} En la conferencia de Bieberbach en 1985, Thurston propuso un esquema para usar el teorema del empaquetamiento de círculos para obtener un homeomorfismo de un subconjunto propio simplemente conexo del plano sobre el interior del disco unitario, y conjeturó que este esquema converge al mapeo de Riemann cuando los radios de los círculos tienden a cero. ^{[ 36 ]} La conjetura de Thurston fue demostrada en 1987 por Burton Rodin y Dennis Sullivan . ^{[ 37 ]} El trabajo de Thurston en esta área atrajo la atención de los matemáticos hacia el tema de los empaquetamientos de círculos y condujo a la formación de una comunidad de investigación centrada en esta idea. ^{[ 71 ]}

• Círculos de Ford , un empaquetamiento de círculos a lo largo de la recta numérica racional.
• Cadena de Steiner , un empaquetamiento circular para la gráfica de una bipirámide.

• Aharonov, Dov (1997), "La constante precisa en el lema del anillo", Variables complejas , 33 ( 1–4 ): 27–31 , doi : 10.1080/17476939708815009 , MR 1624890 
• Aichholzer, Oswin; Rote, Günter; Schulz, André; Vogtenhuber, Birgit (2012), "Dibujos punteados de grafos planares" , Geometría Computacional , 45 (9): 482– 494, doi : 10.1016/j.comgeo.2010.08.001 , MR 2926292 
• Alam, Md. Jawaherul; Eppstein, David ; Goodrich, Michael T .; Kobourov, Stephen G.; Pupyrev, Sergey (2014), "Empaquetamientos circulares equilibrados para grafos planares", en Duncan, Christian A.; Symvonis, Antonios (eds.), Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, Alemania, 24-26 de septiembre de 2014, Revised Selected Papers , Lecture Notes in Computer Science, vol.  8871, Springer, pp. 125–136 , arXiv : 1408.4902 , doi : 10.1007/978-3-662-45803-7_11 , ISBN  978-3-319-12567-1
• Andreev, EM (1970a), "Poliedros convexos en espacios de Lobačevskiĭ", Matematicheskii Sbornik , Nueva Serie, 81 (123): 445– 478, Bibcode : 1970SbMat..10..413A , doi : 10.1070/SM1970v010n03ABEH001677 , MR 0259734 
• Andreev, EM (1970b), "Polyedros convexos de volumen finito en el espacio de Lobačevskiĭ", Matematicheskii Sbornik , Nueva Serie, 83 (125): 256–260 , Bibcode : 1970SbMat..12..255A , doi : 10.1070/SM1970v012n02ABEH000920 , MR 0273510 
• Bannister, Michael J.; Devanny, William E.; Eppstein, David ; Goodrich, Michael T. (2015), "La complejidad de Galois del dibujo de grafos: por qué las soluciones numéricas son omnipresentes para los dibujos dirigidos por fuerza, espectrales y de empaquetamiento de círculos", Journal of Graph Algorithms and Applications , 19 (2): 619–656 , doi : 10.7155/jgaa.00349 , MR 3430492 
• Beardon, Alan F.; Stephenson, Kenneth (1990), "El teorema de uniformización para empaquetamientos circulares" , Indiana Univ. Math. J. , 39 (4): 1383–1425 , doi : 10.1512/iumj.1990.39.39062
• Beardon, Alan F.; Stephenson, Kenneth (1991), "El lema de Schwarz-Pick para empaquetamientos circulares" , Illinois J. Math. , 35 (4): 577–606 , doi : 10.1215/ijm/1255987673
• Benjamini, Itai ; Schramm, Oded (2001), "Recurrencia de límites distribucionales de grafos planares finitos" , Electronic Journal of Probability , 6 : 1–13 , doi : 10.1214/EJP.v6-96 , MR 1873300 
• Bos, Erik-Jan (2010), "La princesa Isabel de Bohemia y las cartas de Descartes (1650–1665)" , Historia Mathematica , 37 (3): 485–502 , doi : 10.1016/j.hm.2009.11.004
• Bowers, Philip L.; Stephenson, Kenneth (2004), Uniformizing Dessins and Belyĭ Maps via Circle Packing , Memoirs of the American Mathematical Society , vol.  170, doi : 10.1090/memo/0805 , MR 2053391 
• Brightwell, Graham R.; Scheinerman , Edward R. (1993), "Representaciones de grafos planares", SIAM Journal on Discrete Mathematics , 6 (2): 214–229 , doi : 10.1137/0406017
• Brooks, Robert W. (1986), "Empaquetamientos circulares y extensiones cocompactas de grupos kleinianos" , Inventiones Mathematicae , 86 (3): 461–469 , Bibcode : 1986InMat..86..461B , doi : 10.1007/BF01389263 , MR 0860677 
• Carter, Ithiel; Rodin, Burt (1992), "Un problema inverso para el empaquetamiento de círculos y el mapeo conforme" , Transactions of the American Mathematical Society , 334 (2): 861– 875, doi : 10.1090/S0002-9947-1992-1081937-X
• Chow, Bennett; Luo, Feng (2003), "Flujos de Ricci combinatorios en superficies", Journal of Differential Geometry , 63 (1): 97–129 , Bibcode : 2003JDGeo..6335659C , doi : 10.4310/jdg/1080835659 , MR 2015261 
• Colin de Verdière, Yves (1991), "Une principe varianel pour les empilements de cercles" , Inventiones Mathematicae , 104 (1): 655– 669, Bibcode : 1991InMat.104..655C , doi : 10.1007/BF01245096
• Collins, Charles R.; Stephenson, Kenneth (2003), "Un algoritmo de empaquetamiento de círculos", Geometría Computacional. Teoría y Aplicaciones , 25 (3): 233– 256, doi : 10.1016/S0925-7721(02)00099-8 , MR 1975216 
• Connelly, Robert ; Gortler, Steven J. (2021), "Empaquetado de discos mediante volteo y flujo" (PDF) , Discrete & Computational Geometry , 66 (4): 1262–1285 , arXiv : 1910.02327 , doi : 10.1007/s00454-020-00242-8 , MR 4333292 
• Connelly, Robert ; Zhang, Zhen (2025), "Rigidez de empaquetamientos circulares con radios flexibles", Discrete & Computational Geometry , 74 (3): 585–618 , arXiv : 2206.07165 , doi : 10.1007/s00454-025-00776-9 , MR 4965850 
• Coxeter, HSM (2006), "Una propiedad absoluta de cuatro círculos mutuamente tangentes", Geometrías no euclidianas , Math. Appl. (NY), vol.  581, Nueva York: Springer, pp. 109–114 , doi : 10.1007/0-387-29555-0_5 , ISBN  978-0-387-29554-1, MR 2191243 
• de Fraysseix, Hubert; Ossona de Mendez, Patrice ; Rosenstiehl, Pierre (1994), "Sobre grafos de contacto triangulares", Combinatorics, Probability and Computing , 3 (2): 233– 246, doi : 10.1017/S0963548300001139 , MR 1288442 
• Dong, Sally; Lee, Yin Tat; Quanrud, Kent (2020), "Cálculo de representaciones de empaquetamiento circular de grafos planares", en Chawla, Shuchi (ed.), Actas del Simposio ACM-SIAM 2020 sobre Algoritmos Discretos, SODA 2020, Salt Lake City, UT, EE. UU., 5-8 de enero de 2020 , Society for Industrial and Applied Mathematics , pp. 2860-2875 , arXiv : 1911.00612 , doi : 10.1137/1.9781611975994.174 , ISBN  978-1-61197-599-4
• Dubejko, Tomasz (1997), "Conexiones de empaquetamiento de círculos con paseos aleatorios y un método de volumen finito", Séminaire de Théorie Spectrale et Géométrie, No. 15, Année 1996–1997 , vol.  15, Universidad. Grenoble I, Saint-Martin-d'Hères, págs. 153-161 , doi : 10.5802/tsg.187 , MR 1604271  
• Emch, Arnold (1910), "Sur quelques exemples mathématiques dans les sciences naturallles" , L'Enseignement mathématique (en francés), 12 : 114– 123
• Eppstein, David (2014), "Un diagrama de potencia invariante de Möbius y sus aplicaciones a burbujas de jabón y al dibujo de Lombardi planar" , Discrete & Computational Geometry , 52 (3): 515–550 , doi : 10.1007/s00454-014-9627-0 , MR 3257673 
• Felsner, Stefan; Igamberdiev, Alejandro; Kindermann, Philipp; Klemz, Boris; Mchedlidze, Tamara; Scheucher, Manfred (2016), "Dibujos fuertemente monótonos de gráficos planos", en Fekete, Sándor P.; Lubiw, Anna (eds.), 32.º Simposio internacional sobre geometría computacional, SoCG 2016, Boston, MA, EE. UU., 14 al 18 de junio de 2016 , LIPIcs, vol.  51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs.  37:1–37:15, doi : 10.4230/LIPICS.SOCG.2016.37 , ISBN 978-3-95977-009-5
• Felsner, Stefan; Rote, Günter (2019), "Sobre las representaciones de círculos duales y primarios", en Fineman, Jeremy T.; Mitzenmacher, Michael (eds.), 2.º Simposio sobre simplicidad en algoritmos, SOSA 2019, San Diego, CA, EE. UU., 8 y 9 de enero de 2019 , OASIcs, vol.  69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs.  8:1–8:18, doi : 10.4230/OASICS.SOSA.2019.8 , ISBN 978-3-95977-099-6
• Fernique, Thomas (2025), "Empaquetamiento de discos desiguales en el plano euclidiano", Geometría Computacional , 124/125 102134, arXiv : 2305.12919 , doi : 10.1016/j.comgeo.2024.102134 , MR 4784743 
• Hansen, Lowell J. (1988), "Sobre el lema del anillo de Rodin y Sullivan", Variables complejas , 10 (1): 23– 30, doi : 10.1080/17476938808814284 , MR 0946096 
• He, Zheng-Xu; Schramm, Oded (1993), "Puntos fijos, uniformización de Koebe y empaquetamientos de círculos" , Annals of Mathematics , Segunda Serie, 137 (2): 369–406 , doi : 10.2307/2946541 , JSTOR 2946541 , MR 1207210  
• He, Zheng-Xu; Schramm, Oded (1995), "Empaquetamientos hiperbólicos y parabólicos", Geometría discreta y computacional , 14 (2): 123– 149, doi : 10.1007/BF02570699 , MR 1331923 
• He, Zheng-Xu; Schramm, Oded (1996), "Sobre la convergencia de empaquetamientos circulares al mapa de Riemann" , Inventiones Mathematicae , 125 (2): 285–305 , Bibcode : 1996InMat.125..285H , doi : 10.1007/s002220050076 , MR 1395721 
• Hurdal, Monica K.; Stephenson, Kenneth (enero de 2004), "Cartografía cortical mediante el enfoque conforme discreto de empaquetamientos circulares" , NeuroImage , 23 : S119– S128, doi : 10.1016/j.neuroimage.2004.07.018 , PMID 15501081 
• Jonnason, Johan; Schramm, Oded (2000), "Sobre el tiempo de cobertura de grafos planares" , Electronic Communications in Probability , 5 : 85–90 , doi : 10.1214/ECP.v5-1022
• Kapovich, Michael (2001), "Capítulo 13: Teorema de Brooks y empaquetamientos de círculos", Variedades hiperbólicas y grupos discretos , Progress in Mathematics, vol.  183, Boston, Massachusetts: Birkhäuser Boston, pp. 333–350 , doi : 10.1007/978-0-8176-4913-5_13 , ISBN  0-8176-3904-7, MR 1792613 
• Kelner, Jonathan A. (2006), "Particionamiento espectral, límites de valores propios y empaquetamientos circulares para grafos de género acotado", SIAM Journal on Computing , 35 (4): 882–902 , doi : 10.1137/S0097539705447244 , MR 2203731 ; también publicado como tesis de maestría del MIT en 2005, hdl : 1721.1/30169
• Keszegh, Balázs; Pach, János ; Pálvölgyi, Dömötör (2013), "Dibujo de gráficas planas de grado acotado con pocas pendientes", Revista SIAM de Matemáticas Discretas , 27 (2): 1171– 1183, doi : 10.1137/100815001 , MR 3071400 
• Koebe, Paul (1936), "Kontaktprobleme der konformen Abbildung", Ber. Sächs. Akád. Wiss. Leipzig, Matemáticas-Física. kl. , 88 : 141-164​
• Leibniz, Gottfried Wilhelm (11-17 de marzo de 1706), Carta a des Bosses , traducida por Ottaviani, Osvaldo – vía Technion
• Lipton, Richard J.; Tarjan , Robert E. (1979), "Un teorema separador para grafos planares", SIAM Journal on Applied Mathematics , 36 (2): 177–189 , CiteSeerX 10.1.1.104.6528 , doi : 10.1137/0136016 
• Louder, Larsen; Mishchenko, Andrey M.; Souto, Juan (2014), "Tres técnicas para obtener empaquetamientos circulares algebraicos", Michigan Mathematical Journal , 63 (3): 535– 552, arXiv : 1304.1488 , doi : 10.1307/mmj/1409932632 , MR 3255690 
• Malitz, Seth; Papakostas, Achilleas (1994), "Sobre la resolución angular de grafos planares", SIAM Journal on Discrete Mathematics , 7 (2): 172– 183, doi : 10.1137/S0895480193242931 , MR 1271989 
• Michiwaki, Yoshimasa (2008), «Geometría en las matemáticas japonesas», en Selin, Helaine (ed.), Enciclopedia de la historia de la ciencia, la tecnología y la medicina en culturas no occidentales , Springer Netherlands, pp. 1018–1019 , doi : 10.1007/978-1-4020-4425-0_9133 , ISBN  978-1-4020-4559-2
• Miller, Gary L.; Teng , Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1997), "Separadores para empaquetamientos de esferas y grafos de vecinos más cercanos", Journal of the ACM , 44 (1): 1–29 , doi : 10.1145/256292.256294
• Mohar, Bojan (1993), "Un algoritmo de empaquetamiento circular en tiempo polinomial", Matemáticas Discretas , 117 ( 1–3 ): 257–263 , doi : 10.1016/0012-365X(93)90340-Y
• Mohar, Bojan (1997a), "Empaquetamientos circulares de mapas en tiempo polinomial", European Journal of Combinatorics , 18 (7): 785–805 , doi : 10.1006/eujc.1996.0135 , MR 1478825 
• Mohar, Bojan (1997b), "Empaquetamientos circulares de mapas: el caso euclidiano", Rediconti del Seminario Matematico e Fisico di Milano , 67 : 191–206 , doi : 10.1007/BF02930499 , MR 1781041 
• Nachmias, Asaf (2020), "Capítulo 3: El teorema del empaquetamiento circular", Mapas planos, paseos aleatorios y empaquetamiento circular: École d'Été de Probabilités de Saint-Flour XLVIII - 2018 , Lecture Notes in Mathematics, vol.  2243, Springer International Publishing, págs. 33 a 46, doi : 10.1007/978-3-030-27968-4_3 , ISBN  9783030279684
• Nederlof, Jesper; Pilipczuk, Michał; Węgrzycki, Karol (2023), "Acotación de los números de coloración generalizados de grafos planares mediante modelos de monedas", Electronic Journal of Combinatorics , 30 (3) 3.33, arXiv : 2201.09340 , doi : 10.37236/11095 , MR 4644253 
• Orick, Gerald L.; Stephenson, Kenneth; Collins, Charles (2017), "Un algoritmo linealizado de empaquetamiento de círculos", Geometría Computacional , 64 : 13–29 , doi : 10.1016/j.comgeo.2017.03.002 , MR 3638944 
• Papadimitriou, Christos H. ; Ratajczak, David (2005), "Sobre una conjetura relacionada con el enrutamiento geométrico", Theoretical Computer Science , 344 (1): 3– 14, doi : 10.1016/j.tcs.2005.06.022 , MR 2178923 
• Pisanski, Tomaž ; Randić, Milan (2000), "Puentes entre la geometría y la teoría de grafos" (PDF) , en Gorini, Catherine A. (ed.), Geometry at Work , MAA Notes, vol.  53, Cambridge University Press, pp. 174–194 , MR 1782654 , archivado del original (PDF) el 19-01-2022 , recuperado el 19-02-2017.  ; véase especialmente la página  176
• Rodin, Burton ; Sullivan, Dennis (1987), "La convergencia de empaquetamientos circulares al mapeo de Riemann" , Journal of Differential Geometry , 26 (2): 349–360 , Bibcode : 1987JDGeo..2641375R , doi : 10.4310/jdg/1214441375
• Rohde, Steffen (2011), "Oded Schramm: del empaquetamiento circular al SLE" , Annals of Probability , 39 (5): 1621– 1667, arXiv : 1007.2007 , doi : 10.1214/10-AOP590; también publicado en Obras selectas de Oded Schramm , Springer, 2011, doi : 10.1007/978-1-4419-9675-6_1
• Sachs, Horst (1994), "Gráficos de monedas, poliedros y mapeo conforme", Matemáticas Discretas , 134 ( 1–3 ): 133–138 , doi : 10.1016/0012-365X(93)E0068-F , MR 1303402 , Zbl 0808.05043  
• Schramm, Oded (1990), Empaquetamiento de cuerpos bidimensionales con combinatoria prescrita y aplicaciones a la construcción de mapeos conformes y cuasi-conformes (tesis doctoral), Universidad de Princeton, ProQuest 303827410 ; modificado y reimpreso como "Empaquetamientos prescritos combinatoriamente y aplicaciones a mapas conformes y cuasiconformes", arXiv : 0709.0710 , 2007
• Schramm, Oded (1991), "Rigidez de empaquetamientos infinitos (circulares)", Journal of the American Mathematical Society , 4 (1): 127– 149, doi : 10.1090/S0894-0347-1991-1076089-9 , JSTOR 2939257 , MR 1076089  
• Schramm, Oded (1992), "Cómo enjaular un huevo" , Inventiones Mathematicae , 107 (3): 543– 560, Bibcode : 1992InMat.107..543S , doi : 10.1007/BF01231901 , MR 1150601 , Zbl 0726.52003  
• Stephenson, Kenneth (1999), "La aproximación de estructuras conformes mediante empaquetamiento circular" (PDF) , Métodos computacionales y teoría de funciones 1997 (Nicosia) , Ser. Approx. Decompos., vol.  11, World Scientific, pp. 551–582 , MR 1700374  
• Stephenson, Kenneth (2003), "Empaquetamiento de círculos: un cuento matemático" ( PDF) , Notices of the American Mathematical Society , 50 : 1376–1388
• Stephenson, Kenneth (2005), Introducción al empaquetamiento de círculos: la teoría de las funciones analíticas discretas , Cambridge: Cambridge University Press
• Thurston, William (1985), El teorema de mapeo de Riemann finito , charla invitada en el Simposio Internacional en la Universidad de Purdue con motivo de la demostración de la conjetura de Bieberbach .; citado por Stephenson (1999 , p. 1) y Rodin & Sullivan (1987) 
• Thurston, William (marzo de 2002), "§13.6, Teorema de Andreev y generalizaciones, y §13.7, Construcción de patrones de círculos", Geometría y topología de 3-variedades , MSRI Publications, pp. 330–346 , versión electrónica 1.1 , consultado el 9 de diciembre de 2025. 
• Tutte, WT (1963), "Cómo dibujar un gráfico", Actas de la Sociedad Matemática de Londres , Tercera Serie, 13 (1): 743– 767, Bibcode : 1963PLMS...13..743T , doi : 10.1112/plms/s3-13.1.743 , MR 0158387 
• Williams, G. Brock (2019), "Construcción de mapas cuasiconformes mediante empaquetamientos circulares y parametrización de cuadriláteros de Brooks", Annales Academiæ Scientiarum Fennicæ , 44 (2): 877–888 , doi : 10.5186/aasfm.2019.4445 , MR 3973545 
• Yu, Xiaokang; Ban, Xiaomeng; Zeng, Wei; Sarkar, Rik; Gu, Xianfeng; Gao, Jie (2011), "Representación esférica y enrutamiento de poliedros para el equilibrio de carga en redes de sensores inalámbricas", INFOCOM 2011, 30.ª Conferencia Internacional IEEE sobre Comunicaciones Informáticas, Conferencia Conjunta de las Sociedades de Computación y Comunicaciones del IEEE, 10-15 de abril de 2011, Shanghái, China (PDF) , IEEE, pp. 621-625 , doi : 10.1109/INFCOM.2011.5935240 , ISBN  978-1-4244-9919-9
• Ziegler, Günter M. (1995), Lectures on Polytopes , Graduate Texts in Mathematics, vol.  152, Springer-Verlag, pp. 117–118 , arXiv : math/9909177 , doi : 10.1007/978-1-4613-8431-1 , ISBN  0-387-94365-X, MR 1311028 , Zbl 0823.52002  

• CirclePack (software gratuito para construir empaquetamientos circulares a partir de grafos, creado por Kenneth Stephenson, de la Universidad de Tennessee).
• CirclePackings , software de código abierto para construir empaquetamientos circulares a partir de grafos, por Benjamin y Brice Loustau.