Provas do teorema de empacotamento de círculo

Question

O teorema de empacotamento do círculo é um resultado famoso que afirma que para cada grafo planar simples conectado $G$ há um círculo compactado no plano cujo gráfico de interseção é $G$ https://en.wikipedia.org/wiki/Circle_packing_theorem.

Sei que esse resultado tem muitas provas e quero ler uma delas, mas não entendo como começar (há um bom tempo). O artigo na wiki fornece uma referência às notas de Thurston, mas a prova vem apenas na última seção e não tenho certeza se esta é a abordagem mais simples. Gosto muito dessas notas, mas nunca fui capaz de lê-las até o fim. Então, eu me pergunto se existem algumas provas simples desse resultado hoje em dia. Você pode aconselhar algo?

Answer 1

Posso recomendar a exposição de Sariel Har-Peled no capítulo 15 suplementar de seu livro Geometric Approximation Algorithms . Ch15 download do PDF . Ele enfatiza os ângulos por meio de um jogo "whac-an-angle". Ele reconhece que

Nossa apresentação segue Pach e Agarwal [ pa-cg-95 ].

---

---

Answer 2

Livros são escritos sobre o assunto, então encontrar uma prova (que já são muitas) não deve ser um problema. Também gostei muito do tributo de Rohde a Schramm, que explica de maneira muito agradável algumas ideias que Schramm introduziu na área; seguindo referências a partir daí, será possível encontrar relatos mais detalhados.