\documentclass[12pt,twoside]{report}
\usepackage[italian, english]{babel}
\usepackage[top=4cm,bottom=4cm,hmarginratio=3:2]{geometry}

% usually not needed (loaded by default)
\usepackage[utf8]{inputenc}


% f**king accents
\usepackage[T1]{fontenc}


% font that is probably the default one ?
\usepackage{newlfont}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% PACKAGES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% headers and footers (ty umbi)
\usepackage{fancyhdr}
\pagestyle{fancy}

%\addtolength{\headwidth}{20pt}
\renewcommand{\chaptermark}[1]{\markboth{\thechapter.\ #1}{}}
\renewcommand{\sectionmark}[1]{\markright{\thesection.\ #1}{}}
\cfoot{}
\rhead[\fancyplain{}{\bfseries\thepage}]{\fancyplain{}{\bfseries\rightmark}}
\lhead[\fancyplain{}{\bfseries\leftmark}]{\fancyplain{}{\bfseries\thepage}}
\linespread{1.3}


%% hyperlink and colors
\usepackage[dvipsnames]{xcolor}
\usepackage{hyperref}

% very personal
\hypersetup{
    linktocpage,
    colorlinks,
    citecolor=Sepia,
    filecolor=Sepia,
    linkcolor=Sepia,
    urlcolor=Sepia
}


%% for roman numerals in enumerate
\usepackage{enumerate}

%% indenting things
\usepackage{scrextend}

%% xd
\usepackage{url}

%% figures
\usepackage{graphicx}
\usepackage{subfig}
\usepackage{wrapfig}

%% gives me text
\usepackage{lipsum}

%% puts the bib in the toc
\usepackage[nottoc]{tocbibind}

%% theorem formatting
\usepackage{amsthm}
\usepackage{amssymb,amsmath,bm}

%% arrows on vectors
\usepackage{esvect}



%% defining stuff
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{teorema}{Teorema}[chapter] % per l'intro in italiano
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{observation}[theorem]{Observation}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\begin{document}



    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% TITLE PAGE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    \begin{titlepage}
        \begin{center}
            {{\Large{\textsc{Alma Mater Studiorum $\cdot$ Universit\`a di Bologna}}}}
            \rule[0.1cm]{\textwidth}{0.1mm}
            \rule[0.5cm]{\textwidth}{0.6mm}
            {\small{\bf SCUOLA DI SCIENZE\\
                    Corso di Laurea in Matematica}}
        \end{center}
        \vspace{15mm}
        \begin{center}
            {\LARGE{\bf THE CIRCLE PACKING THEOREM}}\\
            \vspace{3mm}
            \vspace{3mm}
            \vspace{19mm} {\large{\bf Tesi di Laurea in Analisi}}
        \end{center}
        \vspace{55mm}
        \par
        \noindent
        \begin{minipage}[t]{0.47\textwidth}
            {\large{\bf Relatore:\\
                    Chiar.mo Prof.\\
                    Nicola Arcozzi}}
        \end{minipage}
        \hfill
        \begin{minipage}[t]{0.47\textwidth}\raggedleft
            {\large{\bf Pesentata da:\\
                    Georgian Sarghi}}
        \end{minipage}
        \vspace{20mm}
        \begin{center}
            {\large{\bf Sessione Unica\\
                    Anno Accademico 2018/2019}}
        \end{center}
    \end{titlepage}



    \cleardoublepage

    %% such a pro
    \pagenumbering{roman}

    \chapter*{Introduction}
    \addcontentsline{toc}{chapter}{Introduction}



    The study of tangent circles has a rich history that dates back to antiquity. Already in the third century BC, Apollonius of Perga, in his exstensive study of conics, introduced problems concerning tangency. A famous result attributed to Apollonius is the following.

    \begin{theorem}[Apollonius - 250 BC]
        Given three mutually tangent circles $C_1$, $C_2$, $C_3$ with disjoint interiors\footnote{We define the interior of a circle to be one of the connected components of its complement (see the colored regions in Figure \ref{fig:apo} as an example).}, there are precisely two circles tangent to all the three initial circles (see Figure \ref{fig:apo}).
    \end{theorem}
    \begin{wrapfigure}{r}{0.31\textwidth}
        \vspace{-20pt}
        \begin{center}
            \includegraphics[width=0.30\textwidth]{figures/apo3}
        \end{center}
        \vspace{-20pt}
        \caption{}
        \vspace{-10pt}
        \label{fig:apo}
    \end{wrapfigure}

    A simple proof of this fact can be found here \cite{sarnak2011integral} and employs the use of M\"{o}bius transformations.

    The topic of circle packings as presented here, is surprisingly recent and originates from William Thurston's famous lecture notes on 3-manifolds \cite{thurston1978notes} in which he proves the theorem now known as the \textit{Koebe-Andreev-Thurston Theorem} or \textit{Circle Packing Theorem}.
    He proves it as a consequence of previous work of E. M. Andreev and establishes uniqueness from Mostov's rigidity theorem, an imporant result in Hyperbolic Geometry. A few years later Reiner Kuhnau pointed out a 1936 proof by german mathematician Paul Koebe.

    \begin{wrapfigure}{l}{0.36\textwidth}
        \vspace{-15pt}
        \begin{center}
            \includegraphics[width=0.35\textwidth]{figures/apopacking2}
        \end{center}
        \vspace{-15pt}
        \caption{\cite{wiki:Circle_packing_theorem}}
        \vspace{-10pt}
        \label{fig:apopacking}
    \end{wrapfigure}

    A circle packing is a finite set of circles in the plane, or equivalently in the Riemann sphere, with disjoint interiors and whose union is connected.
    To any circle packing we can naturally associate a simple\footnote{Without loops or multiple edges.} planar graph (called \textit{contact graph} or \textit{nerve}) in the following way: to each circle there corresponds a vertex and, to each pair of tangent circles, an edge connecting the two corrisponding vertices.
    Figure \ref{fig:apopacking} shows an example of a circle packing with its associated graph.
    In the three chapters of this document, we will explore the nature of the correspondence between circle packings and simple planar graphs, and present some applications of this correspondence.
    We will ask the question: what are the necessary conditions on a planar graph to be the contact graph of a circle packing? The answer, given by the Koebe-Andreev-Thurston Theorem, is the following: for every finite simple planar graph there exists a circle packing in the plane with contact graph the initial graph.
    In the case of plane triangulations\footnote{Graphs that admit a drawing in the plane in which every face is bounded by three edges.} an important uniqueness result also holds; indeed, if we have two packings with nerve the same planar triangulation, there exists a M\"{o}bius transformation that maps one into the other.
    As an example, consider the circle packings in Figures \ref{fig:apo} and \ref{fig:apopacking}. Letting the colors help us, we can see how these two packings have the same nerve. This graph, shown in Figure \ref{fig:apopacking}, is a plane triangulation as each of its faces is bounded by three edges. By the Koebe-Andreev-Thurston Theorem, the two circle packings are equal up to a certain M\"{o}bius transformation.

    The objective of this document is to give an elementary proof of the theorem, as well as some of its many applications.
    The first chapter is dedicated to the basic definitions concernig circle packings and graphs. By the and of the first chapter we will have in hand a precise statement of the theorem that we will prove in detail in the second chapter.
    The third chapter is dedicated to applications of the theorem, the most important of which is in the field of Conformal Geometry.
    In the 1985 Perdue conference celebrating de Brange's proof of the Bieberbach Conjecture, William Thurston proposed a way to approximate a conformal map using circle packings. In 1987 Burt Rodin and Dennis Sullivan published a seminal paper \cite{rodin1987convergence} in wich they gave a positive answer to Thurston's conjecture thus establishing circle packings as a topic of great research interest.
    %The proof   The proof of koebe relied on the riemann mapping theorem on molti connected domains and we will present a skech in the third chapter. Through the years many proofs of the theorem were found ... metion shcraam .. variational.. the one presented is an elementary proof based on .. etc...



    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


    \cleardoublepage

    %% così ricomincia da 1
    \setcounter{figure}{0}

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \begin{otherlanguage}{italian}
        \chapter*{Introduzione}
        \addcontentsline{toc}{chapter}{Introduzione}


        Lo studio di configuarazioni di cerchi tangenti inizia nell'antichità. Già nel terzo secolo a.C., Apollonio di Perga, nel suo estensivo studio delle coniche, introdusse molti problemi riguardanti la tangenza di cerchi. Un famoso risultato attribuito ad Apollonio é il seguente.

        \begin{teorema}[Apollonio - 250 a.C.]
            Dati tre cerchi mutualmente tangenti $C_1$, $C_2$, $C_3$ con interni\footnote{Definiamo l'interno di un cerchio come una delle componenti connesse del complemantare (vedi ad esempio le regioni colorate in Figura \ref{fig:apoit}).} digiunti, ci sono esattamente due cerchi tangenti a tutti i tre cerchi iniziali (vedi Figura \ref{fig:apoit}).
        \end{teorema}
        \begin{wrapfigure}{r}{0.31\textwidth}
            \vspace{-20pt}
            \begin{center}
                \includegraphics[width=0.30\textwidth]{figures/apo3}
            \end{center}
            \vspace{-20pt}
            \caption{}
            \vspace{-10pt}
            \label{fig:apoit}
        \end{wrapfigure}

        Una semplice dimostrazione di questo fatto si può trovare qui \cite{sarnak2011integral} e sfrutta le trasformazioni di M\"{o}bius.

    Il tema degli impacchettamenti di cerchi come presentato qui è sorprendentemente recente e ha origine nelle famose note di William Thurston sulle 3-variertà \cite{thurston1978notes}. Qui Thurston dimostra quello che oggi è noto con il nome di \textit{Teorema di Koebe-Andeev-Thurston} (o \textit{Circle Packing Theorem}) come corollario di un lavoro di A. M. Andreev e ne deduce la parte di unicità dal teorema di rigidità di Mostov, un importante risultato in Geometria Iperbolica. Qualche anno dopo Reiner Kuhnau fece notare una dimostrazione del 1936 del matematico tedesco Paul Koebe.

        \begin{wrapfigure}{l}{0.36\textwidth}
            \vspace{-15pt}
            \begin{center}
                \includegraphics[width=0.35\textwidth]{figures/apopacking2}
            \end{center}
            \vspace{-15pt}
            \caption{\cite{wiki:Circle_packing_theorem}}
            \vspace{-10pt}
            \label{fig:apopackingit}
        \end{wrapfigure}

        Un impacchettamento di cerchi è un insieme finito di cerchi nel piano, o equivalentemente nella sfera di Riemann, con interni disgiunti e unione connessa.
        Ad un dato impacchettamento di cerchi possiamo, in modo naturale, associare un grafo planare semplice\footnote{Senza archi multipli o cappi.} (chiamato \textit{grafo di contatto} o \textit{nervo}) nel modo seguente: a ogni cerchio corrisponde un vertice e, a ogni coppia di cerchi tangenti, un arco che connette i vertici corrispondenti.
        Figura \ref{fig:apopacking} mostra un esempio di impacchettamento di cerchi con il relativo grafo.
        Nei tre capitoli di questo documento esploreremo la natura della corrispondenza tra impacchettamenti di cerchi e grafi planari semplici e presenteremo alcune applicazioni di questa corrispondenza. Ci chiederemo: quali sono le condizioni su un grafo planare che gli consentono di essere il nervo di un impacchettamento di cerchi? La risposta, data dal teorema di Koebe-Andreev-Thurston, è la seguente: per ogni grafo planare semplice esiste un impacchettamento di cerchi che ha quest'ultimo come grafo di contatto. Nel caso di triangolazioni del piano\footnote{Grafi che ammettono un'immersione nel piano in cui ogni faccia è delimitata da tre archi.} si ha un importante risultato di unicità; infatti, se si hanno due impacchettamenti con nervo una stessa triangolazione del piano, esiste una trasformazione di M\"{o}bius che porta un impacchettamento nell'altro.
        Come esempio, si considerino gli impacchettamenti nelle Figure \ref{fig:apoit} e \ref{fig:apopackingit}. Facendoci aiutare dai colori, si può osservare che questi impacchettamenti hanno lo stesso nervo. Il teorema di Koebe-Andreev-Thurston ci garantisce l'esistenza di una trasformazione di M\"{o}bius che porta uno dei due impacchettamenti nell'altro.

        Il principale obiettivo di questo lavoro è dare una dimostrazione elementare del teorema di Koebe-Andreev-Thurston, insieme a qualche esempio di applicazione.
        Il primo capitolo è dedicato alle definizioni di base riguardati grafi e impacchettamenti. Alla fine del primo capitolo avremo un enunciato preciso del teorema che dimostreremo in dettaglio nel secondo capitolo.
        Il terzo capito è dedicato alle applicazioni; la più importante di queste è nell'ambito della Geometria Conforme. Nell 1985, in occsione dalla conferenza di Perdue in cui si celebrava la dimostrazione della congettura di Bieberbach da parte di de Brange, William Thurston propose una procedura per l'approssimazione di una mappa conforme utilizzando gli impacchettamenti di cerchi. Nel 1987 Burt Rodin e Dennis Sullivan pubblicarono un articolo \cite{rodin1987convergence} in cui risolsero positivmente la congettura posta da Thurston, dando inizio a un ciclo di fiorenti ricerche nell'area.
        %The proof   The proof of koebe relied on the riemann mapping theorem on molti connected domains and we will present a skech in the third chapter. Through the years many proofs of the theorem were found ... metion shcraam .. variational.. the one presented is an elementary proof based on .. etc...
    \end{otherlanguage}



    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% TABLE OF CONTENTS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \cleardoublepage
    %% a empty page
    \thispagestyle{empty}
    \tableofcontents


    \cleardoublepage





    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CAPITOLO 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


    \chapter{The Circle Packing Theorem}
    \setcounter{page}{3}
    \pagenumbering{arabic}
    In this chapter we define circle packings and give different equivalent statements of the Koebe-Andeev-Thurston theorem. As mentioned in the introduction, we can think of circle packings as lying in the plane or equivalently in the sphere. The bridge between these two views is stereographic projection. Closely related are M\"{o}bius transformations, that appear in the statement of the Circle Packing Theorem.

    \section{Stereographic projection and M\"{o}bius transformations}


    \begin{definition}
        Consider the unit spere $S^2 = \{(x, y, z) \in \mathbb{R}^3 \mid x^2+y^2+z^2=1\}$ and call $N = (0,0,1)$ the \textit{North pole}. For every point $P \in S^2 \setminus \{N\}$ we have a unique line $\ell$ passing through $N$ and $P$. We define the \textit{stereographic projection} of $P$ to be the unique point $P'$ in the intersection of $\ell$ and the plane $z = -1$.\footnote{Some authors define stereographic projection with the plane $z=0$.}
    \end{definition}
    \begin{figure}[h!]
        \centering
        %\vspace{-15pt}
        \includegraphics[width=0.4\textwidth]{figures/stereo}
        \caption{\cite{wiki:Stereographic_projection}}
        %\vspace{-10pt}
        \label{fig:stereo}
    \end{figure}
    We can easily compute explicit formulas for stereographic projection and its inverse. Denote with with $(X, Y)$ the coordinates of the plane $z = -1$. We would like to find an expression for $X$ and $Y$ in terms of the coordinates of a point $P = (x_0, y_0, z_0) \in S^2 \setminus \{N\}$. To do so, consider the line
    $$\ell = \{(\lambda x_0,\lambda y_0, \lambda z_0-\lambda +1)\mid \lambda \in \mathbb{R}\}$$ passing through $N$ (when $\lambda=0$) and $P$ (when $\lambda = 1$). Imposing the last coordinate to be $-1$ we find $\lambda = \frac{2}{1-z_0}$ and thus
    %$$(X, Y, -1) = \lambda(-x_0, -y_0, 1-z_0) + N = \left(\frac{2x_0}{1-z_0}, \frac{2y_0}{1-z_0}, -1\right).$$
    $$(X, Y) = \left(\frac{2x_0}{1-z_0}, \frac{2y_0}{1-z_0}\right).$$
    In a similar fashion we can get an expression for $(x,y,z) \in S^2 \setminus \{N\}$ in terms of the coordinates $(X_0, Y_0)$ of a point in the plane $z=-1$.

    Stereographic projection maps circles in the sphere that do not pass through $N$ into circles on the plane, and circles passing through $N$ into straight lines. Coversely, the inverse stereographic projection maps circles in the plane to circles in the sphere, and straight lines to circles passing through $N$. We might define \textit{generalized circles} in the plane to include straight lines (thought as circles of infinite radius) and say that stereographic projection maps circles in the sphere to generalized circles in the plane and viceversa.
    Stereographic projection is also conformal, that is, it preserves angles at which curves meet. Simple proofs of these propreties can be found here \cite{stereographicprojection}.


    Although circle packings are more easily visulaized in the plane, it is useful to think them as lying in the unit sphere. Let $\hat{\mathbb{C}} = \mathbb{C} \cup \{\infty\}$ be the \textit{extended complex plane} (or \textit{Riemann sphere}). We can identify $\hat{\mathbb{C}}$ with the unit sphere using stereographic projection and sending $\infty$ to the North pole. This identification allows to exchange between the two points of views.

    We now introduce M\"{o}bius tranformations, which are a class of circle-preserving maps of the Riemann sphere.

    \begin{definition}
        A \textit{M\"{o}bius transformation} (or \textit{linear fractional tranformation}) is a complex valued function of the form $$f(z) = \frac{az+b}{cx+d}$$ where $a$, $b$, $c$, $d$ are complex numbers satfying the condition $ad-bc \neq 0$ (so that we have non-constant function). We set $f(\frac{-d}{c}) = \infty$ and $f(\infty)=\frac{a}{c}$ when $c \neq 0$, and $f(\infty) = \infty$ when $c = 0$.
        \label{def:mob}
    \end{definition}

    M\"{o}bius transformation are bijective and conformally map the Riemann spere into itself, that is, they preserve angles formed between any two curves. It is easy to see that they also form a group under composition sometimes denoted $Aut(\hat{\mathbb{C}})$.
    Geometrically, a M\"{o}bius transformation can be thought as these three actions:
    \begin{enumerate}
        \item a stereographic projection of the plane to the unit sphere;
        \item a movement of the sphere to another location in space;
        \item a stereographic projection of the moved sphere to the plane.
    \end{enumerate}
    See \cite{arnold2008mobius} for details and here \cite{youtube} for an animation.

    \begin{theorem}
        The M\"{o}bius transformation
        $$f(z) = \frac{az+b}{cx+d}$$
        has the inverse transformation
        $$f^{-1}(z) = \frac{-dz+c}{bz-a}.$$
        In particular, the inverse of a M\"{o}bius transformation is itself a M\"{o}bius transformation.
    \end{theorem}

    \begin{proof}
        It's an easy exercise.
    \end{proof}

    \begin{proposition}
        A M\"{o}bius transformation can be written as the composition of a translation $(z \mapsto z + \lambda)$, a homothety $(z \mapsto \lambda z)$ and an inversion $(z \mapsto 1/z)$.
        \label{prop:comp}
    \end{proposition}
    \begin{proof}
        $$f(z) = \frac{az+b}{cx+d} = \frac{bc-ad}{c^2} \cdot \frac{1}{z + \frac{d}{c}} + \frac{a}{c}$$
    \end{proof}

    \begin{theorem}
        A M\"obius transformation maps circles of $\hat{\mathbb{C}}$ to circles of $\hat{\mathbb{C}}$. That is, every circle in $\mathbb{C}$ gets mapped to a circle or a line (a circle in $\hat{\mathbb{C}}$ passing through $\infty$), and every line gets mapped to a line or a circle.
        \label{thm:circlestocircles}
    \end{theorem}
    \begin{proof}
        By Proposition \ref{prop:comp} we have a decomposition of our M\"obius transformation into an homothety, a translation and an inversion. It is easy to see that translations and homotheties preserve circles, so one only has to prove the statement for the map $z \mapsto \frac{1}{z}$. The proof of this involves some elementary calculations (see \cite{mobiuspreserve}).
    \end{proof}

    \begin{theorem}
        There exists a unique M\"{o}bius tranformation sending three distinct points $z_1, z_2, z_3 \in \hat{\mathbb{C}}$ to any other three distinct points $w_1,w_2,w_3 \in \hat{\mathbb{C}}$.
        \label{thm:threepts}
    \end{theorem}
    \noindent\textit{Proof sketch.} Given three points $z_1, z_2, z_3 \in \hat{\mathbb{C}}$ one can easily verify that the map $$M(z) = \frac{(z-z_2)}{(z-z_3)}\cdot \frac{(z_1 - z_3)}{(z_1-z_2)}.$$ maps $z_1 \mapsto 1$, $z_2 \mapsto 0$, $z_3 \mapsto \infty$. If one of the $z_i$'s is $\infty$ we 'cancel' the terms with $\infty$. By composing with the inverse of the analogous map associated to $w_1,w_2,w_3$, we get the desired M\"{o}bius transformation. The uniqueness part follows from the fact that a M\"{o}bius transformation that is not the identity, cant fix more than two points (see \cite{mobiusdetails} for details).\hfill\qed

    \begin{lemma}
        Given three points $z_1, z_2, z_3 \in \hat{\mathbb{C}}$, there exist three unique mutually tangent circles $C_1$, $C_2$, $C_3$ such that $C_1 \cap C_2 = z_1$, $C_1 \cap C_3 = z_2$ and $C_2 \cap C_3 = z_3$.
        \label{lm:unitri}
    \end{lemma}
    \begin{proof}
        Applying a suitable M\"{o}bius transformation, we may assume $z_1 = -1$, $z_2 = 1$ and $z_3 = \infty$. In the plane, two of these circles will then be parallel lines tangent to a thrid circle at $+1$ and $-1$. Therefore $+1$ and $-1$ are diametrically opposite on this third circles and thus the three circles are determined. %We may now apply the inverse tranformation of the one applied at the beginning to get back the original points.
    \end{proof}

    \begin{theorem}
        There exists a unique M\"{o}bius tranformation that maps three mutually tangent circles $P_1, P_2, P_3$ in $\hat{\mathbb{C}}$ to any other three mutually tangent circles $C_1, C_2, C_3$ in $\hat{\mathbb{C}}$.
        \label{thm:threecircles}
    \end{theorem}
    \begin{proof}
        By Theorem \ref{thm:threepts} there exists a unique M\"{o}bius transformation mapping $P_1 \cap P_2$ to $C_1 \cap C_2$, $P_1 \cap P_3$ to $C_1 \cap P_3$ and $P_2 \cap P_3$ to $C_2 \cap C_3$. We conclude using Theorem \ref{thm:circlestocircles} and Lemma \ref{lm:unitri}.
    \end{proof}



    \section{Planar graphs and maps}

    \begin{definition}
        A \textit{simple graph} is an ordered pair $G = (V, E)$ comprising of:
        \begin{itemize}
            \item[--] a set of vertices $V = (v_i)_{i \in J}$ indexed by some countable set $J$;
            \item[--] a set of edges $E \subset \{\{u,v\} \mid u, v \in V \land u \neq v\}$.
        \end{itemize}
        If $\{v_i, v_j\} \in E$ we say that $v_i$ and $v_j$ are connected by an (undirected) edge. The term \textit{simple} stands for the fact that our graph does not have \textit{multiple edges} or \textit{loops} (like the ones in red below).
    \end{definition}
    \begin{figure}[h!]
        \centering
        \includegraphics[width=\textwidth]{figures/try}
        \caption{Example of a \textit{non-simple} graph.}
    \end{figure}
    \begin{definition}
        A graph $G = (V, E)$ is \textit{connected} if for each $u, v \in V$, there exists a $m$-tuple (or \textit{path}, in this case) of vertices $(v_1,...,v_m)$ such that $v_1 = u$, $v_m = v$ and $\{v_i, v_{i+1}\} \in E$ for each $i \in \{1,...,m-1\}$.
    \end{definition}

    \begin{definition}
        Let $G = (E, V)$ be any graph, and let $S$ be a subset of $V$. Then the \textit{induced subgraph} $G[S]$ is the graph on vertex set $S$ and whose edges are the edges in $E$ that have both endpoints in $S$.
    \end{definition}

    \begin{definition}
        A graph $G = (V, E)$ is \textit{planar} if it has a \textit{planar embedding}. A planar embeddng is a graph $G = (V, E)$ endowed with a map such that:
        \begin{itemize}
            \item[--] vertices are mapped to distinct points of $\mathbb{R}^2$;
            \item[--] edges are mapped to continuous curves between the corrisponding vertices;
            \item[--] no two curves intersect, except at the vertices they share.
        \end{itemize}
        We use the term \textit{drawing} to refer to the image in $\mathbb{R}^2$ of the map of the embedding.
    \end{definition}

    %For the purpose of what follows we will consider all the %graphs to be planar and simple.
    A planar embedding uniquely defines a cyclic order of the edges and therefore one could regard some drawings to be similar or different (Figure \ref{fig:map}).
    \begin{figure}[h]
        \centering
        \begin{minipage}{0.48\textwidth}
            \centering
            \includegraphics[width=0.9\textwidth]{figures/map12} % first figure itself

        \end{minipage}\hfill
        \begin{minipage}{0.47\textwidth}
            \centering
            \includegraphics[width=0.9\textwidth]{figures/map21} % second figure itself

        \end{minipage}
        \caption{On the left: two embeddings representing the same class of planar maps. On the right: two embeddings that represent the same graph but different classes of planar maps. The clockwise order of neighbors for the yellow vertex is (green, red, blue) in one case and (green, blue, red) in the other.}
        \label{fig:map}
    \end{figure}

    \begin{definition}
        A \textit{planar map} (or \textit{combinatorial embedding}) is a graph in which every vertex $v$ has a cyclic ordering $\sigma_v$ of edges incident to it. These cyclic orders are such that there exists a planar embedding in which the clockwise order of the curves touching the image of a vertex respects the cyclic order. %The set of these cyclic orders is called a \textbf{rotation system}.
    \end{definition}


    We now want to define precisely what we mean by \textit{face}. Intuitively faces are the connected components of the complement of the drawing, but this intitive definition might fail to capture the essence of a face in the case of countably infinite graphs. Furthermore, we want to define a face combinatorially, that is, without referring to the embedding, but only to the planar map. To do so we consider each edge of the graph as directed in both ways, and give the following definition.

    \begin{definition}
        Let $\vec{e}$, $\vec{f}$ be directed edges of a planar map. We say that $\vec{e}$ \textit{precedes} $\vec{f}$, if there exist vertices $v$, $x$, $y$ such that $\vec{e} = (x, v)$, $\vec{f} = (v, y)$ and $y$ is the successor of $x$ in the cyclic order $\sigma_v$ (see Figure \ref{fig:prec}).
    \end{definition}

    \begin{figure}[h]
        \centering
        \begin{minipage}{0.35\textwidth}
            \centering
            \includegraphics[width=\textwidth]{figures/prec1} % first figure itself
            (a)\hspace{.4cm}$\vec{e}$ preceeds $\vec{f}$.
            \label{fig:prec1}
        \end{minipage}\hspace{2cm}
        \begin{minipage}{0.35\textwidth}
            \centering
            \includegraphics[width=\textwidth]{figures/prec2} % second figure itself
            (a)\hspace{.4cm}$(x, y)$ preceeds $(y, x)$.
            \label{fig:prec2}
        \end{minipage}
        \caption{\cite[p.~28]{nachmias2018planar} Examples of the precedence relation.}
        \label{fig:prec}
    \end{figure}

    Intuitively, we can think of two directed edges as belonging to the same face if, starting from one, we can reach the other by always moving to the next leftmost edge (the leftmost edge is the one that succeds the current one). This is formalized with the next definition.

    \begin{definition}
        Let $\vec{e}$, $\vec{f}$ be directed edges of a planar map. We say that $\vec{e}$ and $\vec{f}$ \textit{belong to the same face} if there exists an $m$-tuple $(\vec{e}_1,...,\vec{e}_m)$ with $\vec{e}_i$ preceding $\vec{e}_{i+1}$ for $i \in \{1,...,m-1\}$ and either $\vec{e} = \vec{e}_1$ and $\vec{f} = \vec{e}_m$, or $\vec{f} = \vec{e}_1$ and $\vec{e} = \vec{e}_m$. Therefore a \textit{face} is just an equivalence class in the relation we just defined.
        Even though a face is a set of directed edges, we may ignore orientation and therefore have that each edge is incident to eighter one or two faces.
    \end{definition}



    The \textit{degree} of a face is the number of directed edges that make up its boundary.
    Note that for simple planar graphs with at least two faces the degree of every face is at least three. Given a finite planar map, the complement of its drawing has a unique unbounded component. We call \textit{outer face} the face that bounds it.
    The outer face should not be regarded as a special one; indeed we can find an embedding in which the outer face is any face $f$ in the following way:
    \begin{enumerate}
        \item project stereographically the drawing to the unit sphere;
        \item rotate the sphere so that $f$ contains the (new) north pole;
        \item project the rotated sphere on the plane.
    \end{enumerate}
    This actions can be summarized in a M\"{o}bius tranformation and gives an embedding in which $f$ takes the role of outer face. See Figure \ref{fig:ste123} below for an example.

    \begin{figure}[h!]
        \centering
        \vspace{-5pt}
        \begin{minipage}{0.5\textwidth}
            \centering
            \includegraphics[width=\textwidth]{figures/ste1}\\
        \end{minipage}\hfill
        \begin{minipage}{0.5\textwidth}
            \centering
            \includegraphics[width=\textwidth]{figures/ste2}\\
        \end{minipage}\hfill
        \begin{minipage}{0.5\textwidth}
            \centering
            \includegraphics[width=\textwidth]{figures/ste3}\\
        \end{minipage}
    \vspace{-5pt}
        \caption{In the top left the cube graph $\mathcal{Q}_3$ embedded in the sphere and projected to the plane. Note how the outer face is bounded by four red edges. If we continuously rotate the sphere (thus continuously changing the North pole through which we project) as shown in the top right, we can get some other arbitrary face to be the outer one. In our example the new outer face is bounded by red and blue edges.}
        \label{fig:ste123}
    \end{figure}

    \begin{definition}
        A \textit{plane triangulation} is a simple planar map in which every face is bounded by exactly three edges.
    \end{definition}
    Any plane triangulation can be seen as the 1-skeleton of a triangulation of the sphere\footnote{The plane triangulation on three vertices is not, strictly speaking, a triangulation, but is a regular CW complex decomposition of the sphere}.
    \begin{theorem}[Euler's formula]
        \label{euler}
        Suppose G = (V, E) is a connected planar graph with n vertices, m edges and f faces. Then
        \begin{equation}
        n - m + f = 2
        \label{eq:euler}.
        \end{equation}
    \end{theorem}
    For proof(s) see \textit{Twenty Proofs of Euler's Formula} by David Eppstein \cite{eppstein2013proofs}.


    \begin{corollary}
        Suppose $G = (V, E)$ is a plane triangulation. Denote by n, m and f the number of vertices, edges and faces. Then
        \begin{equation}
        f = 2n - 4
        \label{eq:euler_t}.
        \end{equation}
    \end{corollary}
    \begin{proof}
        Observe that $3f = 2n$, since each face is bounded by three edges and each edge bounds exactly two faces. Then applying Euler's formula (\ref{eq:euler}), we have (\ref{eq:euler_t}).
    \end{proof}



    \section{The Circle Packing Theorem}
    The interior of a circle $P \subset \mathbb{C}$ is usually defined as the bounded connected component of $\mathbb{C} \setminus P$. For generalized circles we can define it parametrizing the circle and saying that the interior of our circle is the part of the plane that remains on the left when we follow the trajectory defined by the parametrization. Given a circle $P = \{ z \in \mathbb{C} \mid |z-z_0| = r\}$ we denote with $D(P)$ the union of $P$ and its interior.


    \begin{definition}
        A \textit{circle packing} is a countable collection $P = {(P_j)_{j \in J}}$ of circles $P_j = \{ z \in \mathbb{C} \mid |z-z_j| = r_j\}$ in the complex plane, indexed by some set $J$, which are allowed to intersect only tangentially (they have disjoint interiors), and whose union is connected.
    \end{definition}

    \begin{definition}
        An \textit{interstice} is a connected component of the complement of $\bigcup_{j \in J} (P_j \cup D(P_j))$. A \textit{triangular interstice} is an interstice whose closure intersects three circles.
    \end{definition}

    \begin{definition}
        The \textit{contact graph} (or \textit{nerve}) associated to a circle packing $P = {(P_j)_{j \in J}}$ is the graph on the vertex set $V = \{v_j \mid j \in J\}$ and edge set $E$ such that for each $\alpha, \beta \in J$ we have: $$\{v_{\alpha}, v_{\beta}\} \in E \iff P_{\alpha} \cap P_{\beta} \neq \emptyset.$$
    \end{definition}


    \begin{observation}
        \label{planarnerve}
        The contact graph of circle packing $P = {(P_j)_{j \in J}}$ is connected, planar and simple.
    \end{observation}
    \begin{proof}
        We can embedd the contact graph in the plane by mapping each vertex in the center of the corrisponding circle and drawing the edges as a lines segments between the centers of intersecting circles. These line segments reamain internal to the circles except for the point of intersection through which they pass. These points of intersections form a discrete set in bijection with the set of edges. Therefore, no two of the drawn line segments can cross.
    \end{proof}

    We are now ready to give a first formulation of the Circle Packing Theorem.

    \begin{theorem}[\textbf{Koebe-Andreev-Thurston} (v1)]
        For every finite planar graph $G$, there is a circle packing in the plane with nerve G. If G is a plane triangulation the packing is unique up to M\"{o}bius transformations and reflections.
    \end{theorem}
    Figure \ref{fig:no_uniqueness} shows how uniqueness up to M\"{o}bius transformations and reflections fails for planar graphs that are not triangulations. On the left a planar embedding of a graph which is not a plane triangulation (the outer face is bounded by 7 edges). In the packing on the right, we can modify cicles 1, 5, 6 and 4 to be bigger or smaller leaving the other circles unchanged and without modifying the tangency pattern. We could also swap circles 5 and 6 and still have a valid packing for the graph. These changes can not be described in terms of a reflections or M\"{o}bius transformations, therefore the uniqueness statement does not hold in this case.

    \begin{figure}[h]
        \centering
        \begin{minipage}{0.4\textwidth}
            \centering
            \includegraphics[width=\textwidth]{figures/ex_1_1}
        \end{minipage}\hspace{1.5cm}
        \begin{minipage}{0.4\textwidth}
            \centering
            \includegraphics[width=\textwidth]{figures/ex1_2}
        \end{minipage}
        \caption{\cite[p.~2]{nachmias2018planar} A planar simple graph and an associated packing.}
        \label{fig:no_uniqueness}
    \end{figure}


    We can see how, again in Figure \ref{fig:no_uniqueness}, the ordering of the neighbors of every circle (the ones tangent to it) agrees with the ordering of the neighbors of the associated vertex. That is, the structure of the planar map is also preserved. Swapping circles 5 and 6 would not change the tangency graph, but would certainly change the 'tangency map'. Indeed, the statement of the theorem can be strengthened in the following way.

    \begin{theorem}[\textbf{Koebe-Andreev-Thurston} (v2)]
        Given any finite simple planar map $G = (V, E)$, $V = \{v_j \mid j \in J\}$, there exists a circle packing in $\mathbb{C}$, $P = (P_j)_{j \in J}$, with nerve $G$. Furthermore, for every vertex $v_i$, the clockwise order of the circles tangent to $P_i$ agrees with the cyclic permutation of $v_i$'s neighbors in the map. Furthermore, if $G$ is a plane triangulation, the packing is unique up to M\"{o}bius transformations.
    \end{theorem}
    Note how reflections invert the cyclic orderings of the vertices in the planar map. This is why we do not have uniqueness up to reflections in this case.
    %An immediate corollary is that there is an essentially unique combinatorial embedding for a plane triangulation.

    \begin{observation}
        It suffices to prove the theorem for plane triangulations.
    \end{observation}
    \begin{proof}
        In any planar graph, if we add a vertex in each face bounded by more that three edges and connect it to all the vertices of the face, we obtain plane triagulation. At this point we just apply the Circle Packing Theorem for triangulations and remove the circles corresponding to the added vertices. This gives a packing with the desired pattern of tangency (see Figure \ref{fig:notriang} below).
    \end{proof}

    \begin{figure}[h]
        \centering
        \vspace{-15pt}
        \begin{minipage}{0.48\textwidth}
            \centering
            \includegraphics[width=\textwidth]{figures/ex_notriang_1}
        \end{minipage}\hfill
        \begin{minipage}{0.48\textwidth}
            \centering
            \includegraphics[width=\textwidth]{figures/ex_notriang_2}
        \end{minipage}
        \caption{\cite[p.~29]{nachmias2018planar} On the left: we add new (red) vertices and adges to make the graph a plane triangulation. On the right: a circle packing associated with the triangulation. Removing the circles corresponding to the added vertices gives a packing with nerve the original graph.}
        \label{fig:notriang}
    \end{figure}
    %We now give the last version of the theorem; the one we will prove in the next chapter.
    \begin{theorem}[\textbf{Koebe-Andreev-Thurston} (v3)]
        Let $G = (V, E)$ be a finite triangulation for which $V = \{v_j \mid j \in J\}$ where  $J = \{1,..,n\}$. Assume that $\{v_1,v_2,v_3\}$ are the vertices a face. Then for any three positive numbers $\rho_1,\rho_2, \rho_3$, there exists a circle packing $P = (P_j)_{j \in J}$ with nerve G and the addition property that $C_1, C_2, C_3$ are mutually tangent, correspond to the outer face, and have radii $\rho_1,\rho_2, \rho_3$, respecively. Furthermore, this circle packing is unique up to translations and rotations of the plane.
        \label{thm:cpt}
    \end{theorem}

    Fixing the three radii amounts to fix the sides of the triangle obtained connecting their centers. Thus, the type of rigidity we have is only up to rotations and translations.
    We will get a circle packing similar to the one in Figure \ref{fig:notriang}: all the circle that correspond to internal vertices will lie in the triangular interstice of the three 'outer' circles.
    %In this case, once we found the packing, we cannot apply M\"{o}bius transformations as we have fixed three circles (see \ref{thm:threecircles}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CAPITOLO 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \cleardoublepage
    \chapter{Proof of the Circle Packing Theorem}
    In this chapter we present an elementary proof of Theorem \ref{thm:cpt} based on \cite{nachmias2018planar}. The proof takes inspiration from Thurston's argument \cite{thurston1978notes} and from the work of Brightwell and Scheinerman \cite{brightwell1993representations}.
    We also use a theorem due to Ohad Feldheim and Ori Gurel-Gurevich (Theorem \ref{thm:draw}) for the drawing part of the argument. The uniqueness proof is due to Oded Schramm, published as a contribution on Wikipedia \cite{wiki:Circle_packing_theorem}.
    \section{Setup}
    %\begin{theorem}[\textbf{Koebe-Andreev-Thurston} (v3)]
    %   Let $G = (V, E)$ be a finite triangulation on vertex set $V = \{v_j \mid j \in J\}$ and assume $\{v_1,v_2,v_3\}$ form a face. Then for any three positive numbers $\rho_1,\rho_2, \rho_3$, there exists a circle packing $P = (P_j)_{j \in J}$ with nerve G and the addition property that $C_1, C_2, C_3$ are mutually tangent, correspond to the outer face, and have radii $\rho_1,\rho_2, \rho_3$, respecively. Furthermore, this circle packing is unique up to translations and rotations of the plane.
    %   \label{thm:cp1t}
    %\end{theorem}
    Given a circle packing in the plane we could describe it providing the radii of the circles and the position of their centers. With this information, there is only one configuration of circles we can draw, and what makes this drawing a circle packing lies inside the \textit{verctor of radii} that should have certain characteristics. We will now describe these characteristics and see how these radii, packed in a vector, are the key to the proof of Theorem \ref{thm:cpt} we are presenting.

    \begin{definition}
        A \textit{label} for $G$ is a collection $R = (r_i)_{i \in J}$ of positive numbers. We will also denote $r_i$ with $R(v_i)$.
    \end{definition}

    As Theorem \ref{thm:cpt} states, we assume $G = (V, E)$ to be a finite triangulation on vertex set $V = \{v_j \mid j \in J\}$ where $J = \{1,...,n\}$. Remebering the arbitrary nature of the outer face, we also assume that $\{v_1, v_2, v_3\}$ forms the outer face of the map.
    Let $v_i, v_j, v_k$ be the vertices of a face $f$ and consider a configuration of three mutually tangent circles of radii $r_i$, $r_j$, $r_k$ Connecting the centers of these circles we obtain a triangle $\bigtriangleup v_i v_j v_k$ of side lengths $r_i+r_j$, $r_i+r_k$ and $r_j+r_k$.

    \begin{figure}[h!]
        \centering
        \includegraphics[width=\textwidth]{figures/triangle}
        \caption{The triangle $\bigtriangleup v_i v_j v_k$.}
    \end{figure}

    Given a label $R$ and three vertices $v_i$, $v_j$, $v_k$ bounding a face $f$ we define $\alpha_f^R(v_j)$ to be the angle corrisponding to the vertex $v_j$ in a triangle $\bigtriangleup v_i v_j v_k$.



    \begin{theorem}[Law of cosines]
        \label{cosines}
        In a triangle of side lengths $a$, $b$, $c$ let $\gamma$ denote the angle between sides of lengths a and b and opposite to the side of length c. Then
        \begin{equation}
        \cos{\gamma} = \frac{a^2 + b^2 - c^2}{2ab}
        \label{eq:cosine}
        \end{equation}

    \end{theorem}
    \begin{proof}
        See \cite{wiki:Law_of_cosines}.
    \end{proof}

    \begin{corollary}
        In the notation above we have:
        \begin{equation}
        \cos\left(\alpha_f^R(v_j)\right) = 1-\frac{2r_i r_k}{(r_i+r_j)(r_j+r_k)} \in (0, 1).
        \label{eq:cosine2}
        \end{equation}
    \end{corollary}
    \begin{proof}
        In the triangle $\bigtriangleup v_i v_j v_k$ the angle $\alpha_f^R(v_j)$ is the one between sides of lengths $r_i+r_j$ and $r_k+r_j$ and opposite to the side of length $r_i+r_k$. Setting $a = r_i + r_j$, $b = r_k + r_j$ and $c = r_j + r_k$ in (\ref{eq:cosine}) we get (\ref{eq:cosine2}).
    \end{proof}

    Denote with $F^\mathrm{o}$ the set of faces of the map except the outer face. Given $A \subset V$ let $F(A)$ be the set of the faces in $F^\mathrm{o}$ that have at least one vertex in $A$. When we write $F(v)$ we mean $F(\{v\})$. We write $V(f)$ to denote the set of vertices composing the face $f$.

    \begin{definition}
        Let $R$ be a label for our planar triangulation $G$. For every $j \in J$, we define the \textit{sum of angles} at $v_j \in V$ with respect to $R$ to be:
        \begin{equation}
        \sigma_R(v_j) = \sum_{f \in F(v_j)} \alpha_f^R(v_j).
        \end{equation}
        \label{eq:sigma}
    \end{definition}

    Let $\theta_1$, $\theta_2$, $\theta_3$ be the angles formed at the centers of three mutually tangent circles $C_1$, $C_2$, $C_3$ of radii $\rho_1$, $\rho_2$, $\rho_3$.

    \begin{definition}
        Let $R$ be a label for our planar triangulation $G$. We call $R$ a \textit{packing label} if it satisfies:
        \begin{equation}
        \sigma_R(v_i) =
        \begin{cases}
        \theta_i &\text{$i \in \{1,2,3\}$}\\
        2\pi &\text{otherwise}
        \end{cases}
        \label{eq:label}
        \end{equation}
    \end{definition}

    Observe that if we consider a circle packing of a map sarifying Theorem \ref{thm:cpt} must satisfy (\ref{eq:label}) and therefore be a packing label. The idea of the proof revolves around finding a packing label and then showing how it gives us the desired circle packing. The proof is split in three parts:

    \begin{enumerate}[(i)]
        \item A packing label exists;
        \item Given a packing label, we can draw a circle packing with those radii and such that:
        \begin{enumerate}
            \item $(r_1, r_2, r_3)$ is a positive multiple of $(\rho_1, \rho_2, \rho_3)$;
            \item this circle packing is unique up to translations and rotations.
        \end{enumerate}
        \item The packing label is unique up to scaling all the entries by a positive number.
    \end{enumerate}



    \section{Finding a packing label}

    The most important part of the proof will be finding a verctor of radii such that we can draw a circle packing in wich the circles have exactly those radii. Starting with a chosen arbitrary label we will define an iterative algorithm that we prove to converge to a label that allows the construction of a circle packing. Altough we will have an algorithm to compute packings, this will not run in finite (guaranteed) runnings time. It is an open problem to find an algorithm thar runs in finite (hopefully polynomial) time, even if we relax some condition\footnote{Like allowing circles to have intersecting interiors or shapes different from circles}.

    \begin{observation}
        Let $R$ be a label for our planar triangulation $G$. Then
        \begin{equation}
        \displaystyle\sum_{i \in J} \sigma_R(v_i) = |F^\mathrm{o}|\pi = (2n-5)\cdot\pi.
        \label{eq:sumsigma}
        \end{equation}
    \end{observation}
    \begin{proof}
        Each inner face $f$ is bounded by three vertices $v_i, v_j, v_k$ and contributes with the three angles $\alpha_f^{R}(v_i)$, $\alpha_f^{R}(v_j)$, and $\alpha_f^{R}(v_k)$ wich sum to $\pi$. By (\ref{eq:euler_t}), there are $2n-5$ inner faces.
    \end{proof}

    We now set
    \begin{equation}
    \delta_R(v_i) =
    \begin{cases}
    \sigma_R(v_i)-\theta_i &\text{$i \in \{1,2,3\}$}\\
    \sigma_R(v_i)-2\pi &\text{otherwise}
    \end{cases}
    \label{eq:delta}
    \end{equation}
    Finding a packing label is equivalent to find $R$ such that $\delta_R \equiv 0$. From (\ref{eq:sumsigma}) and the fact that $\theta_1$, $\theta_3$, $\theta_3$ constitute the internal angles of a triangle, that for every label $R$,
    \begin{equation}
    \sum_{i \in J}\delta_R(v_i) = \sum_{i \in J}\sigma_R(v_i) - \theta_1 - \theta_2 - \theta_3 - (n-3)\cdot 2\pi = 0.
    \label{eq:sumdelta}
    \end{equation}
    We define
    \begin{equation}
    \mathcal{E}_R = \sum_{i \in J}\delta_R(v_i)^2.
    \end{equation}

    Proving the existence of a packing label now comes down to find $R$ for which $\mathcal{E}_R = 0$. To do so, we will use the following geometric observation.

    \begin{observation}
        Let $(R_i)_{i \in J}$ and $(R'_i)_{i \in J}$ be labels for our plane triangulation G, and $f \in F^\mathrm{o}$ be bounded by $v_i, v_j, v_k$ for some $i,j,k \in J$. Then
        \begin{enumerate}[(I)]
            \item\hspace{.3cm} If $R'(v_i) \leq R(v_i)$, $R'(v_k) \leq R(v_k)$ and $R'(v_j) \geq R(v_j)$,

            \hspace{1cm} then $\alpha_f^{R'}(v_j) \leq \alpha_f^R(v_j)$.
            \item\hspace{.3cm} If $R'(v_i) \geq R(v_i)$, $R'(v_k) \geq R(v_k)$ and $R'(v_j) \leq R(v_j)$,

            \hspace{1cm} then $\alpha_f^{R'}(v_j) \geq \alpha_f^R(v_j)$.
            \item\hspace{.3cm} $\alpha_f^R(v)$ is continuous in $R$.
        \end{enumerate}
        \label{obs:mono}
    \end{observation}
    \begin{proof}
        In (\ref{eq:cosine2}) increasing $r_i$ and $r_k$ while decreasing $r_j$ makes the cosine increse. Therefore the angle decreases and (I) is proven. Figure \ref{fig:mono} shows an illustration of this fact. Similarly we prove (II). Point (III) is immediate consequence of (\ref{eq:cosine2}).
    \end{proof}

    \begin{figure}[h]
        \centering
        \includegraphics[width=0.9\textwidth]{figures/mono3}
        \caption{Given three vertices forming a face, increasing the radius of the circle corresponding to one vertex while decreasing the radii of the other two, makes the angle at the first vertex decrease.}
        \label{fig:mono}
    \end{figure}



    Starting with an initial vector of labels $R^{(0)}$ we define an iteration that we prove to converge to a packing label. The input and autput of the algorithm will be labels for $G$, normalized to have $\ell_1$ norm 1, that is, we whant the sum of the entries to be 1. We take $R^{(0)} = (\frac{1}{n},...,\frac{1}{n})$ to be our starting label and given given $R=R^{(t)}$ we construct $R'=R^{(t+1)}$. To the new label $R'$, we associate $\delta' = \delta_{R'}$ and $\mathcal{E}' = \mathcal{E}_{R'}$. If $\delta' \equiv 0$ we are done, othrwise, we continue the iteration.

    To define the iteration, we study the set $(\delta(v_i))_{i \in J}$. If $\delta' \not\equiv 0$, choose $s \in \mathbb{R}$ such that the sets $S = \{v \in V \mid \delta(v) > s\}$ and $V \setminus S$ are non-empty and the gap
    $$gap_{\delta}(S) \overset{\mathrm{def}}{=} \min_{v \in S} \delta(v) - \max_{v \notin S} \delta(v)$$
    is maximal.

    %\begin{figure}[h!]
    %   \centering
    %   \includegraphics[width=1.0\textwidth]{figures/gap}
    %   \caption{Left: the maximum gap between two consecutive values of $\delta$. Right: if we define $R'$ in the right way, the gap will be closed.}
    %   \label{fig:gap}
    %\end{figure}


    We now define $R' = R^{(t+1)}$ from $R = R^{(t)}$ :
    \begin{enumerate}\label{eq:update}
        \item For some $\lambda \in (0, 1)$ to be chosen later, we set
        \begin{equation}
        (R_{\lambda})_i =
        \begin{cases}
        R(v_i) &\text{$v_i \in S$}\\
        \lambda R(v_i) &\text{$v_i \notin S$}
        \end{cases}
        \end{equation}
        \item We normalize $R_{\lambda}$ to have $\ell_1$ norm 1. Let $\hat{R}_{\lambda}$ be the normalized vector and define $R' = \hat{R}_{\lambda}$.
    \end{enumerate}


    Normalizing $R_\lambda$ in step 2 does not influence the vector $\delta'$. We will often work with $R_\lambda$ for this reason.

    We now want to show that:
    \begin{itemize}
        \item[\textbf{(a)}] for any $\lambda \in (0, 1)$, step 1 will decrease all values of $\delta(v)$ for $v \in S$ and increase all values of $\delta(v)$ for $v \notin S$;
        \item[\textbf{(b)}] there exists a $\lambda$ that closes the gap, that is,
        $$gap_{\delta'}(S) = \min_{v \in S} \delta'(v) - \max_{v \notin S} \delta'(v).$$
    \end{itemize}

    Part \textbf{(a)} is formalized with the following lemma relying on the geometric Observation \ref{obs:mono}.

    \begin{lemma}
        For every $\lambda \in(0, 1)$, whe have:
        \begin{enumerate}[(I)]
            \item\hspace{.3cm} $\delta'(v) \geq \delta(v)$ for every $v \notin S$;
            \item\hspace{.3cm} $\delta'(v) \leq \delta(v)$ for every $v \in S$.
        \end{enumerate}
    \end{lemma}
    \begin{proof}
        Consider $v_j \notin S$ and $f \in F^{\mathrm{o}}$ bounded by vertices $v_i$, $v_j$, $v_k$.
        \bigskip \\
        \textbf{Case 1:} $v_i$, $v_k \notin S$.
        \begin{addmargin}[2em]{0em}
            In this case the radii of $P_i$, $P_j$, $P_k$ are all multiplied by $\lambda$, so $\alpha_f^{R'}(v_j) = \alpha_f^{R}(v_j)$.
        \end{addmargin}
        \bigskip
        \textbf{Case 2:} $v_i$, $v_k \in S$.
        \begin{addmargin}[2em]{0em}
            In this  case the radii of $P_i$, $P_k$ remain unchanges while the radius of $C_j$ decreases, thus by observation \ref{obs:mono} we get that $\alpha_f^{R'}(v_j) \geq \alpha_f^{R}(v_j)$.
        \end{addmargin}
        \bigskip
        \textbf{Case 3:} $v_i \notin S$, $v_k \in S$.
        \begin{addmargin}[2em]{0em}
            In this  case the radii of $P_i$, $P_j$ are multiplied by $\lambda$. If we multiply each of the three radii by $\lambda^{-1}$ the agles ramain the same and it is as if we left the radii of $P_i$ and $P_j$ unchanged and increased the radius of $C_k$ (because $\lambda^{-1} > 1$). By observation \ref{obs:mono}, we get that $\alpha_f^{R'}(v_j) \geq \alpha_f^{R}(v_j)$.
        \end{addmargin}
        \bigskip
        In all cases we have that $\alpha_f^{R'}(v_j) \geq \alpha_f^{R}(v_j)$, therefore, it follows from (\ref{eq:delta}) and (\ref{eq:sigma}) that $\delta'(v) \geq \delta(v)$ for any $v \notin S$. A similar argument also shows that $\delta'(v) \leq \delta(v)$ for all $v \in S$.
    \end{proof}

    We now want to show \textbf{(b)}: that there exists $\lambda \in (0,1)$ that closes the gap. This is done with the following lemma. The proof is a little technical and we advise the reader to just read the statement and return to it later.
    \begin{lemma}
        \begin{equation}
        \lim_{\lambda \searrow 0} \sum_{v \notin S} \delta_{R_{\lambda}}(v) > 0
        \end{equation}
        \label{lm:abovezero}
    \end{lemma}
    \begin{proof}
        The proof is split in two parts. We first show that for each face $f \in F(V \setminus S)$ bounded by $v_i$, $v_j$ ,$v_k$, the sum of angles at the vertices belonging to $V \setminus S$ converges to $\pi$ as $\lambda \searrow 0$. The argument relies again on Observation \ref{obs:mono}.
        \bigskip \\
        \textbf{Case 1:} $v_i$, $v_j$, $v_k \notin S$.
        \begin{addmargin}[2em]{0em}
            In this case, since the face is a triangle, $\alpha_f^{R_{\lambda}}(v_i) + \alpha_f^{R_{\lambda}}(v_j) + \alpha_f^{R_{\lambda}}(v_k) = \pi$ for all $\lambda \in (0, 1)$.
        \end{addmargin}
        \bigskip
        \textbf{Case 2:} $v_i$, $v_j \notin S$ but $v_k \in S$.
        \begin{addmargin}[2em]{0em}
            In this case, it follows from the cosine formula (\ref{eq:cosine2}) that $\lim_{\lambda \searrow 0} \alpha_f^{R_{\lambda}}(v_k) = 0$, hence $\lim_{\lambda \searrow 0}\alpha_f^{R_{\lambda}}(v_i) + \alpha_f^{R_{\lambda}}(v_j) = \pi$.
        \end{addmargin}
        \bigskip
        \textbf{Case 3:} $v_i \notin S$, $v_j$, $v_k \in S$.
        \begin{addmargin}[2em]{0em}
            In this case, again from (\ref{eq:cosine2}), it follows that $\lim_{\lambda \searrow 0} \alpha_f^{R_{\lambda}}(v_j) + \alpha_f^{R_{\lambda}}(v_k) = 0$, hence $\lim_{\lambda \searrow 0}\alpha_f^{R_{\lambda}}(v_i) = \pi$.
        \end{addmargin}
        \bigskip
        Therefore we have
        \begin{equation}
        \lim_{\lambda \searrow 0} \sum_{v \notin S} \sigma_{R_{\lambda}}(v) = |F(V \setminus S)|\cdot\pi.
        \end{equation}
        Now set
        \begin{equation}
        \theta(v_i) =
        \begin{cases}
        \theta_i &\text{$i \in \{1,2,3\}$}\\
        2\pi &\text{otherwise}
        \end{cases}
        \end{equation}
        so that we can write $\delta_R(v) = \sigma_R(v) - \theta(v)$ for all $v \in V$ . Then
        \begin{equation}
        \begin{split}
        \lim_{\lambda \searrow 0} \sum_{v \notin S} \delta_{R_{\lambda}}(v) &  \overset{\mathrm{def}}{=} \lim_{\lambda \searrow 0} \sum_{v \notin S} \sigma_{R_{\lambda}}(v) - \sum_{v \notin S} \theta(v) \\[10pt]
        & = |F(V \setminus S)|\pi - \sum_{v \notin S} \theta(v)
        \end{split}
        \label{eq:ine1}
        \end{equation}
        Let $\widetilde{F} = F^{\mathrm{o}} \setminus F(V \setminus S)$, so every face in $\widetilde{F}$ contains only vertices of $S$. We will show that
        \begin{equation}
        |\widetilde{F}|\pi < \sum_{v \in S} \theta(v).
        \label{eq:ine2}
        \end{equation}
        If (\ref{eq:ine2}) holds, the quantity $|\widetilde{F}|\pi - \sum_{v \in S} \theta(v)$ is negative. Adding it to (\ref{eq:ine1}) gives
        \begin{equation}
        \begin{split}
            \lim_{\lambda \searrow 0} \sum_{v \in V} \delta_{R_{\lambda}}(v)
            &= |F(V \setminus S)|\pi - \sum_{v \notin S} \theta(v) + |\widetilde{F}|\pi - \sum_{v \in S} \theta(v) \\[10pt]
            &= |F^\mathrm{o}|\pi - \sum_{v \in V} \theta(v)\\[10pt]
            &= (2n - 5)\cdot \pi - (2n - 5)\cdot \pi = 0.
        \end{split}
        \label{eq:ine3}
        \end{equation}
        Therefore (\ref{eq:ine1}) is strictly positive, proving our lemma. Thus we proceed showing (\ref{eq:ine2}).

        We fix an embedding of G in the plane with $(v_1, v_2, v_3)$ as the outer face and consider the induced subgraph $G[S]$.
        Partition $S$ into equivalence classes, $$S = S_1 \cup\cdot\cdot\cdot\cup S_k,$$ where two vertices are equivalent if they are in the same connected component of $G[S]$.
        Thus we have the decomposition $$G[S] = G[S_1] \cup\cdot\cdot\cdot\cup G[S_k].$$
        Let $\widetilde{F}_j$ be the set of faces in $\widetilde{F}$ that appear as faces of $G[S_j]$, so that we have the disjoint union $$\widetilde{F} = \widetilde{F}_1 \cup\cdot\cdot\cdot\cup \widetilde{F}_k.$$
        Now it is enough to show that for any $j \in \{1,...,k\}$,
        \begin{equation}
        |\widetilde{F}_j|\pi < \sum_{v \in S_j} \theta(v).
        \label{eq:ine3}
        \end{equation}
        Let $m_j$ and $f_j$ denote the number of edges and faces of $G[S_j]$. Observe that $|\widetilde{F}_j| \leq f_j - 1$, as the outer face of $G[S_j]$ will never be counted.

        If $|\widetilde{F}_j| = 0$, then (\ref{eq:ine3}) is trivial.

        If $|\widetilde{F}_j| \geq 1$, then $G[S_j]$ is a simple graph with at least one inner face. Each edge is countend in one or two faces, therefore the sum of the degrees of all the faces is less then or equal to twice the number of edges. In a simple graph with at least one face the degree of each one of them is at least three, we have $2m_j \geq 3f_j$ and using Euler's formula we get
        \begin{align}
        \frac{3}{2} f_j &\leq  m_j = |S_j| + f_j - 2 \\
        f_j &\leq 2|S_j| - 4 \label{eq:xd}
        \end{align}
        Thus, summing over $j \in \{1,...,k\}$ and multiplying by $\pi$, we get that the left side of (\ref{eq:ine3}) satisfies
        \begin{equation}
        |\widetilde{F}_j|\cdot\pi \leq (2|S_j| - 5)\cdot\pi.
        \label{eq:ine5}
        \end{equation}
        If $\{v_1, v_2, v_3\} \subset S_j$ then the right side of (\ref{eq:ine3}) is
        \begin{equation}
        \sum_{v \in S_j} \theta(v) = \theta_1 + \theta_2 + \theta_3 + (|S_j| - 3) \cdot 2\pi = (2|S_j| - 5)\cdot \pi.
        \label{eq:ine4}
        \end{equation}
        Thus we have

        $$|\widetilde{F}_j|\pi \leq (2|S_j| - 5)\cdot\pi = \sum_{v \in S_j} \theta(v).$$

        We see that stict inequality holds by the following case analysis.
        \bigskip \\
        \textbf{Case 1:} $\{v_1, v_2, v_3\} \not\subset S_j$.
        \begin{addmargin}[2em]{0em}
            In this case, at least one of the $\theta_i$ in (\ref{eq:ine4}) is replaced by $2\pi$ and so the right side of (\ref{eq:ine3}) is strictly greater than the left side.
        \end{addmargin}
        \bigskip
        \textbf{Case 2:} $|\widetilde{F}_j| < f_j - 1$.
        \begin{addmargin}[2em]{0em}
            In this case, (\ref{eq:xd}) implies $|\widetilde{F}_j| < 2|S_j| - 5$ and we have a strict inequality in (\ref{eq:ine5}). Therefore (\ref{eq:ine3}) holds.
        \end{addmargin}
        \bigskip
        \textbf{Case 3:} $\{v_1, v_2, v_3\} \subset S_j$ and $|\widetilde{F}_j| = f_j - 1 = 2|S_j| - 5$.
        \begin{addmargin}[2em]{0em}
            We prove that this case cannot occur. The equality $\widetilde{F}_j = f_j - 1$ means that every inner face of $G[S_j]$ is an element $\widetilde{F}_j$ and therefore a face of G. Since $\{v_1, v_2, v_3\} \subset S_j$ , the outer face of $G[S_j]$ is $\{v_1, v_2, v_3\}$, which is the same as the outer face of $G$.
            So, every face of $G[S_j]$ is also a face of $G$.
            But this is impossible: if we choose any $v \in V \setminus S$, then $v$ is not a vertex of $G[S_j]$ (the vertices of $G[S_j]$ all bellong to $S$) but must lie in some face of $G[S_j]$, which then cannot be a face of $G$.
        \end{addmargin}
        \bigskip

        So we conclude that (\ref{eq:ine3}) always holds.
    \end{proof}

    \begin{proposition}
        Let $R$ be a label for $G$. There exists $\lambda \in (0, 1)$ for which $R_\lambda$ is such that $gap_{\delta'}(S) = 0.$
        \label{th:lambdaexists}
    \end{proposition}

    \begin{proof}
        By the third bullet of Observation (\ref{obs:mono}) the function $\lambda \mapsto gap_{\delta_{R_{\lambda}}}(S)$ is continuous on $(0, 1]$, and its value at $\lambda = 1$ is $$gap_{\delta}(S) = min_{v \in S} \delta_{R}(v) - max_{v \not\in S} \delta_{R}(v) > 0.$$
        Lemma \ref{lm:abovezero} says that if $\mu > 0$ is small enough, then
        $$\sum_{v \notin S} \delta_{R_{\mu}}(v) > 0$$
        from which it follows that $max_{v \not\in S} \delta_{R_{\mu}}(v) > 0$. By (\ref{eq:sumdelta}), we also have
        $$\sum_{v \in S} \delta_{R_{\mu}}(v) = -\sum_{v \notin S} \delta_{R_{\mu}}(v) < 0,$$
        meaning that $min_{v \in S} \delta_{R_{\mu}}(v) < 0$ and therefore
        $$gap_{\delta_{R_{\mu}}}(S) = min_{v \in S} \delta_{R_{\mu}}(v) - max_{v \not\in S} \delta_{R_{\mu}}(v) < 0.$$
        By continuity, there exists $\lambda \in (\mu, 1)$ such that $gap_{\delta_{R_{\lambda}}}(S) = 0$.
    \end{proof}

    \newpage

    We now analyse the algorithm to show that $\mathcal{E}^{(t)} \to 0$ as $t \to \infty$.
    \begin{proposition}
        Let $R$ be a label for $G$, $\lambda \in (0, 1)$ be the one guaranteed by Proposition (\ref{th:lambdaexists}), and set $\mathcal{E}' = \mathcal{E}_{R_{\lambda}}$. Then
        $$\mathcal{E}' \leq \mathcal{E} \cdot \left(1 - \frac{1}{2n^3}\right).$$
        \label{prop:convergence}
    \end{proposition}
    \begin{proof}
        Define $$t = \min_{v \in S} \delta'(v) = \max_{v \notin S}\delta(v).$$
        By (\ref{eq:sumdelta}) we have that $$\sum_{i \in J}\delta(v_i) = \sum_{i \in J}\delta'(v_i) = 0,$$
        and therefore the following holds:
        \begin{equation}
        \begin{split}
        \mathcal{E} - \mathcal{E}' &= \sum_{i \in J}\delta(v_i)^2 - \sum_{i \in J}\delta'(v_i)^2 \\[10pt]
        & = \sum(\delta(v_i) - \delta'(v_i))^2 + 2 \sum_{i \in J}(t - \delta'(v_i))(\delta'(v_i) - \delta(v_i)).
        \end{split}
        \end{equation}
        If $v \in S$, then $t \leq \delta'(v) \leq \delta(v)$ and if $v \notin S$, then $t \geq \delta'(v) \geq \delta(v)$. Thus, in both cases $(t - \delta'(v_i))(\delta'(v_i) - \delta(v_i)) \geq 0$ and we already have $\mathcal{E}' < \mathcal{E}$. Taking $u \in S$ and $v \in V\setminus S$ with $\delta'(u)  = \delta'(v) = t$, we have that
        \begin{equation}
        \mathcal{E} - \mathcal{E}' \geq (\delta(u) - t)^2 + (\delta(v) - t)^2 \geq \frac{(\delta(u) - \delta(v))^2}{2} \geq \frac{gap_{\delta}(S)^2}{2}.
        \label{eq:bound1}
        \end{equation}
        Since we have $n-1$ possible gaps between $n$ numbers and $gap_{\delta}(S)$ was chosen to be the maximal gap we may bound,
        \begin{equation}
        gap_{\delta}(S) \geq \frac{1}{n}\left(\max_{v \in V} \delta(v) - \min_{v \in V} \delta(v)\right).
        \label{eq:bound2}
        \end{equation}
        Again (\ref{eq:sumdelta}) implies that for every $v \in V$,
        \begin{equation}
        \max_{w \in V}\delta(w) - \min_{w \in V}\delta(w) \geq |\delta(v)|,
        \label{eq:bound3}
        \end{equation}
        and thus, squaring (\ref{eq:bound2}) to bound (\ref{eq:bound1}) and then using (\ref{eq:bound3}) we get
        \begin{equation*}
        \begin{split}
        \frac{gap_{\delta}(S)^2}{2} &\geq \frac{1}{2n^2} \left(\max_{v \in V}\delta(v) - \min_{v \in V}\delta(v)\right)^2 \\[10pt]
        &\geq \frac{1}{2n^2 \cdot n} n \left(\max_{v \in V}\delta(v) - \min_{v \in V}\delta(v)\right)^2 \\[10pt]
        & \geq \frac{1}{2n^3}\sum_{i \in J}\delta(v_i)^2 = \frac{1}{2n^3} \mathcal{E}.
        \end{split}
        \end{equation*}
        Hence, from this and (\ref{eq:bound1}) we get $$\mathcal{E} - \mathcal{E}' \geq \frac{1}{2n^3} \mathcal{E},$$ and we conclude that
        $$\mathcal{E}' \leq \mathcal{E} \cdot \left(1 - \frac{1}{2n^3}\right).$$
    \end{proof}

    By iterating the described algorithm, we obtain from Prop. \ref{prop:convergence} that $$\mathcal{E}^{(t)} \leq \mathcal{E}^{(0)}\left(1 - \frac{1}{2n^3}\right)^t \xrightarrow[t \to \infty]{} 0.$$
    For every $t$ we have $\lVert R^{(t)}\rVert_{\ell_1} = 1$ and therefore, by compactness, there exists a subsequence $(t_k)_{k \in \mathbb{N}}$ and a vector $R^{\infty}$ such that $R^{(t_k)} \to R^{\infty}$ as $k \to \infty$.
    Continuity of $\mathcal{E}$ implies $\mathcal{E}_{R^\infty} = 0$, meaning that (\ref{eq:label}) is satisfied. We might not have a packing label still, as some entries of $R^{(\infty)}$ may be 0. We do not have to worry obout entries blowing up to $\infty$ as $\lVert R^{(t)}\rVert_{\ell_1} = 1$ for every $t$, and therefore $\lVert R^{\infty}\rVert_{\ell_1} = 1$.
    \begin{proposition}
        $R^{(\infty)}(v_i) > 0$ for all $i \in J$.
    \end{proposition}
    \begin{proof}
        Let $T = \{v_i \in V \mid R^{(\infty)}(v_i) > 0\}$. We have $\lVert R^{\infty}\rVert_{\ell_1} = 1$ and therefore $S$ is nonempty. If we assume for contradiction that $V \setminus T$ is also nonempty, a statment similar to Lemma \ref{lm:abovezero} also holds. Indeed, we have that
        \begin{equation}
        \lim_{t \to \infty} \sum_{v \notin T} \delta_{R^{(t)}}(v) > 0.
        \label{eq:similar}
        \end{equation}
        The proof relies on the same argument used in Lemma \ref{lm:abovezero}; we first show by case analysis that
        $$\lim_{t \to \infty}\sum_{v \notin T} \sigma_{R^{(t)}}(v) = |F(V \setminus T)|\cdot\pi$$
        and then deducing the result proving $$|\widetilde{F}| < \sum_{v \in T} \theta(v)$$ where $\widetilde{F} = F^{\mathrm{o}} \setminus F(V \setminus T)$.
        Now, if (\ref{eq:similar}) holds, it can not be true that $\lim_{t \to \infty} \mathcal{E}^{(t)} = 0$, and thus we have a contradiction. We conclude that $T = V$.
    \end{proof}


    \section{Drawing the circle packing}
    We now show that the packing label $R^{\infty}$ we found in the previous section, gives us a circle packing that can be drawn uniquely up to translations and rotations. The result we present is slightly more general and is due to Ori Gurel-Gurevich and Ohad Feldheim.

    Let $G = (V, E)$ be a finite planar triangulation on vertex set $V = (v_j)_{j \in J}$ with $J = \{1,...,n\}$, and assume that $\{v_1, v_2, v_3\}$ forms the outer face. Instead of working with labels of radii we consider a vector $\bm{\ell}=(\ell_e)_{e \in E}$ of positive real numbers, indexed by the edge set $E$. Let $f$ be a face of $G$ enclosed by $e_\alpha, e_\beta, e_\gamma$ and such that the edge lengths $\ell_{e_\alpha},\ell_{e_\beta}, \ell_{e_\gamma}$ can be made to form a triangle, that is, the following three triangle inequalities hold:
    \begin{equation}
    \ell_{e_i} + \ell_{e_j} > \ell_{e_k} \hspace{1cm}\{i, j, k\} = \{1, 2, 3\}.
    \label{eq:tri}
    \end{equation}
    Then, we can use the cosine formula (\ref{eq:cosine}) to compute the angle corresponding to a vertex $v \in V(f)$ in the triangle with side lengths $\ell_{e_\alpha},\ell_{e_\beta}, \ell_{e_\gamma}$. We denote this angle with $\alpha_f^{\bm{\ell}}(v)$. Similarly to what we have done with labels of radii, we define the \textit{sum of angles} at a vertex $v$ as
    $$\sigma_{\bm{\ell}}(v) = \sum_{f \in F(v)}\alpha_f^{\bm{\ell}}(v).$$
    \begin{definition}
        A vector of positive real numbers $\bm{\ell}=(\ell_e)_{e \in E}$ is called \textit{feasible} if the following conditions hold:
        \begin{itemize}
            \item[--] for any face enclosed by edges $e_\alpha, e_\beta, e_\gamma$, the lengths $\ell_{e_\alpha},\ell_{e_\beta}, \ell_{e_\gamma}$ satisfy (\ref{eq:tri});
            \item[--] For any internal vertex $v \in V \setminus \{v_1, v_2, v_3\}$ we have
            $\sigma_{\bm{\ell}}(v) = 2\pi$.
        \end{itemize}
    \end{definition}

    \begin{theorem}
        Let $G$ be a finite planar triangulation and $\bm{\ell}$ a feasible vector of edge lengths. Then there is a drawing of $G$ in the plane so that each edge $e$ is drawn as a straight line segment of length $\ell_e$ and no two edges cross. Furthermore,
        this drawing is unique up to translations and rotations.
        \label{thm:draw}
    \end{theorem}

    Before proving this theorem, we state without proof the following classical result, known as the Two Ears Theorem \cite{meisters1975polygons}.

    \begin{theorem}[Two Ears Theorem]
        Every simple closed polygon that is not a triangle has at least two ears. An ear is a vertex such that the open line segment connecting its neighbors lies entirely on the interior of the polygon.
    \end{theorem}

    \begin{corollary}
        Every simple closed polygon $P$ on $n$ vertices can be triangulated without adding eny vertex. Furthermore, every triangulation with no new vertices contains $n-3$ non-crossing
        diagonals.
        \label{cor:two}
    \end{corollary}
    \begin{proof}
        We can construct a triangulation $\mathcal{T}$ of the polygon $P$ by cuttig triangular ears. Every time we cut a ear, the ramaining polygon has one vertex less, and therefore we can itarate this process until we remain with a triangle.

        Let $t$ be the number of triangles in a triangulation $\mathcal{T}$ of $P$. The sum $\bm\Sigma$ of internal angles in a polygon with $n$ vertices can be proven to be $\bm\Sigma = (n-2) \cdot \pi$, but also $\bm\Sigma = t\pi$ (as we did not add new vertices). Thus we have $t = n-2$ and the number of feces in $\mathcal{T}$ is $n-1$. Now, denoting with $k$ the number of diagonals and using Euler's formula (\ref{eq:euler}) , we have $n - (n + k) + (n-1) = 2$ and therefore $k = n-3$.
    \end{proof}
    In \cite{meisters1975polygons} it is also shown how this Corollary implies the Two Ears Theorem.
    \newpage\noindent
    \textit{Proof of Theorem 2.14.} We use induction on the number of vertices $n$.


    \textit{Base case:} The case $n = 3$ is trivial since $\bm{\ell}$ is feasible and thus the three edges of the outer face can form a triangle. Any two triangles with the same side lengths are similar and therefore the uniqueness statement also holds.


    \textit{Induction step:} If $n > 3$, there exists an internal vertex $v$. We want to draw the faces to which $v$ belongs. Consider the Euclidean plane with Cartesian coordinates $(x,y)$ and place $v$ at the origin. Letting $(v_1,...,v_m)$ denote the neighbors of $v$ in clockwise ordered, we want to determine their position in the plane.
    To do so we draw the edge $\{v, v_1\}$ as a straight line segment of length $\ell_{\{v,v_1\}}$ on the positive $x$-axis emanating from the origin. For each $i \in \{2,...,m\}$ we draw the edge $\{v, v_i\}$ as a straight line segment of length $\ell_{\{v,v_i\}}$ emanating from the origin $(v)$ at a clockwise angle of $\alpha_f^{\bm{\ell}}(v)$ from the previous drawn line segment of $\{v, v_i-1\}$, where $f = \{v, v_i-1, v_i\}$.
    Feasibility of $\bm{\ell}$ guarantees that we can complete the triangles by drawing the straight line segments connecting $v_i$ to $v_i+1$, each of length $\ell_{\{v,v_i+1\}}$ where $i \in \{1,...,m\}$ (with $v_m+1 = v_1$). Denote these edges by $e_1,..., e_m$.

    \begin{figure}[h]
        \centering
        \includegraphics[width=1.0\textwidth]{figures/inductive}
        \caption{\protect\cite[p.~37]{nachmias2018planar} On the left, we first draw the polygon surrounding $v$. On the right, we then erase $v$ and the edge emanating from it, replacing it with diagonals that triangulate the polygon while recording the lengths of the diagonals in $\bm{\ell}'$. The latter is the input to the induction hypothesis.}
        \label{fig:inductive}
    \end{figure}


    Since $\bm{\ell}$ is feasible we have $\sigma_{\bm{\ell}}(v) = 2\pi$, and therefore these $m$ triangles we have drawn have disjoint interiors. The edges $e_1,...,e_m$ form a simple closed polygon containing the origin in its interior (Figure \ref{fig:inductive}, left). By Corollary \ref{cor:two} we have that every closed polygon on $m$ verices can be triangulated by drawing $m-3$ diagonals as straight line segments in the interior of the polygon. We erase vertex $v$ and draw the $m-1$ chosen diagonals (Figure \ref{fig:inductive}. right).
    Adding the corrispondin edges and removing $v$ gives a new graph $G'$ on $n - 1$ vertices and $|E(G)| - 3$ edges.
    Assigning to the new edges the corrisponding Euclidean lengths of the diagonals in the drawing, we get a new edge length vector $\bm{\ell}'$ corresponding to $G'$ that is clearly feasible.

    By the induction hypothesis we have a drawing of $G'$ with edge lengths $\bm{\ell}'$. This drawing is unique up to translations and rotations by induction. In this drawing, the polygon corresponding to $e_1,..., e_m$ must be the exact same polygon as before, up to translations and rotations, since it has the same edge lengths and the same angles between its edges. Since it is the same polygon, we can now erase the diagonals in this drawing and place a new vertex in the same relative position in which we have drawn $v$ before. We connect this new vertex to $v_1,..., v_m$ with straight line segments. Thus we have obtained the desired drawing of $G$. The uniqueness up to translations and rotations of this drawing follows from the uniqueness of the drawing of $G'$ and the fact that the location of $v$ is uniquely defined in that drawing.\hfill\qed


    \begin{corollary}
        Let $R = (R_j)_{j \in J}$ be a packing label for a finite planar triangulation $G = (V, E)$, where $V = (R_j)_{j \in J}$. Then, there is circle packing $P = (P_j)_{j \in J}$ with contact graph $G$ and such that circle $P_j$ corrisponding to $v_j$ has radius $R_i$ for every $j \in J$. Furthermore, this packing is unique up to translations and rotations.
    \end{corollary}
    \begin{proof}
        Let $\bm{\ell}$ be the vector of edge lenghts indexed by $E$, and such that $\ell_e = R(v_i) + R(v_j)$ for any edge $e = \{v_i, v_j\} \in E$. Condition (\ref{eq:label}) implies that $\bm{\ell}$ is feasible. Applying Theorem \ref{thm:draw} we get a drawing of $G$, unique up to translations and rotation. We draw a circle $P_i$ of radius $R_i$ around the point representing $v_i$. For any edge $\{v_\alpha, v_\beta\}$, the distance between the two endpoints of the line segment representing it, is exactly $R(v_\alpha) + R(v_\beta)$ and therefore $P_\alpha$ and $P_\beta$ are tangent to each other.

        Assume instead that $\{v_\alpha, v_\beta\}$ is not an edge. We must show that $P_\alpha$ and $P_\beta$ are not tangent to each other. For any $v \in V$ let $A_{v}$ be the union of the faces touching $v$ in the drawing of Theorem \ref{thm:draw}. Since $v_\alpha$ and $v_\beta$ are not adjacent we have that $Int(A_{v_\alpha}) \cap Int(A_{v_\beta}) = \emptyset$. We also have that $P_\alpha \subset Int(A_{v_\alpha})$ since each of the segments composing the boundary of $A_{v_\alpha}$ is contained in the circles associated to the adjacent vertices. Similarly $P_\beta \subset Int(A_{v_\beta})$ and thus $P_\alpha$ and $P_\beta$ are not tangent to each other.
    \end{proof}

    \section{Uniqueness}
    \begin{theorem}
        Given a simple finite triangulation with outer face $v_1, v_2, v_3$ and three radii $\rho_1, \rho_2, \rho_3$, the circle packing with $C_1 , C_2 , C_3$ having radii $\rho_1, \rho_2, \rho_3$ is unique up to translations and rotations.
    \end{theorem}
    \begin{proof}
        We have already seen in step 2 that given the radii vector $r$ the drawing we obtain is unique up to translations and rotations. Thus, we only need to show the uniqueness of r given $\rho_1, \rho_2, \rho_3$. To that aim, suppose that $R^a$ and $R^b$ are two vectors satisfying (\ref{eq:label}). Since the outer face in both vectors correspond to a triangle of angles $\theta_1, \theta_2, \theta_3$ we may rescale so that $R^a_i = R^b_i =\rho_i$ for $i = 1, 2, 3$. After this rescaling, assume by contradiction that $R^a \neq R^b$ and let $v$ be the interior vertex which maximizes $R^a_v/R^b_v$. We can assume without loss of generality that this quantity is strictly larger than 1, as otherwise we can swap $R^a$ and $R^b$. Now we claim that for each $f = (v, u_1, u_2) \in F(v)$, we have
        $\alpha_f^{R^a}(v)\leq\alpha_f^{R^b}(v)$, with equality if and only if the ratios $R_{u_i}^a / R_{u_i}^b$, for $i = 1, 2$, are both equal to $R_{v}^a / R_{v}^b$. This is a direct consequence of Observation \ref{obs:mono}.
        Indeed, scale all the radii in $R^b$ by a factor of $R_{v}^a / R_{v}^b$ to get a new vector $R'$ such that $R_{v}^a = R_{v}'$ and $R_{u}^a \leq R_{u}'$ for all $u \neq v$. The second bullet point in Observation \ref{obs:mono} implies that $\alpha_f^{R^a}(v)\leq\alpha_f^{R'}(v) = \alpha_f^{R^b}(v)$. As well, if either $R_{u_1} < R_{u_1}'$ or $R_{u_2} < R_{u_2}'$, then the cosine formula yields the strict inequality $\alpha_f^{R^a}(v) < \alpha_f^{R'}(v)$. Thus, $\alpha_f^{R^a}(v)=\alpha_f^{R^b}(v)$ only if $R_{u_i}^a / R_{u_i}^b = R_{v}^a / R_{v}^b$ for $i = 1, 2$.
        Now, since for each $f \in F(v)$, while $\sigma_{R^{a}}(v) = \sigma_{R^{b}}(v) = 2\pi$, the equality $\alpha_f^{R^a}(v)=\alpha_f^{R^b}(v)$ must hold for each $f$. Therefore, each neighbor $u$ of $v$ satisfies $R_{u}^a / R_{u}^b = R_{v}^a / R_{v}^b$.
        Because the graph is connected, the ratio $R_{u}^a / R_{u}^b$ must be constant for all vertices $u \in V(G)$. But this contradicts that $R_{u}^a / R_{u}^b > 1$ while $R_{v_i}^a / R_{v_i}^b = 1$ for $i = 1, 2, 3$. We conclude that $R^a = R^b$.
    \end{proof}



    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% CAPITOLO 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \cleardoublepage
    \chapter{Applications and other results}


    \section{Thurston Conjecture for Circle Packings}
    In 1936 Paul Koebe proved the Circle Packing Theorem as a consequance of his generalization of the Riemann Mapping Theorem to $n$-connected domains (a domain whose complement has exactly $n$ connected components). Surprisingly Koebe's proof remained hidden and unknown until the 80's despite Koebe being a renowed mathematician of his time. In the following pages we state the Riemann Mapping Theorem and its generalization to $n$-connected domains along with a sketch of Koebe's proof of the Circle Packing Theorem. After that, we present Thurston's conjecture on the approximation of conformal mappings using circle packings.

    \begin{definition}
        Let $U$, $V$ be open subsets of the complex plane. The map $f : U \to V$ is \textit{biholomofic} if it is a bijective holomorphic map whose inverse is also holomorphic. %A function is \textit{holomorphic} when it is complex differentiable in every point of its domain of definition.
        A biholomophic map is also conformal and therefore angle-preserving. If such a map exists we say that $U$ and $V$ are \textit{conformally equivalent}.
    \end{definition}

    \begin{theorem}[Rieman Mapping Theorem]
        Let $\Omega$ be a simply connected open proper subset of $\mathbb{C}$. Then $\Omega$ is conformally equivalent to the unit closed disk $D = \{z \in \mathbb{C} \mid |z| \leq 1\}$. Furthermore, the biholomorphic mapping $f : \Omega \to D$ is unique up to post-composition with a M\"{o}bius transformation preserving the disk.
        \label{thm:riemann}
    \end{theorem}
    This is a remarkable theorem with numerous consequences. One immediate corollary is the fact that any two simply connected proper subsets of $\mathbb{C}$ are homeomorphic. Let $U$ and $V$ be such subsets and let $f$ and $g$ be the maps guaranteed by the Riemann Mapping Theorem. Then the map $g^{-1}\circ f : U \to V$ is a (conformal!) homeomorphism.

    A generalization of Theorem \ref{thm:riemann} due to Koebe is the following.

    \begin{theorem}
        Let $\Omega$ be a $n$-connected open subset of $\mathbb{C}$. Then there exists a biholomorphic map $f : \Omega \to \Omega'$ such that $\Omega'$ is a \textit{circle domain}, that is, its boundary components are points or circles. Furthermore, both $f$ and $\Omega'$ are unique up to M\"{o}bius transformation.
        \label{thm:koebe}
    \end{theorem}

    We now present a sketch of Koebe's original argument for existence of a circle packing with prescribed tangency graph.
    \begin{figure}[h]
        \centering
        \begin{minipage}{0.244\textwidth}
            \centering
            \includegraphics[width=0.9\textwidth]{figures/koebe1}\\ % first figure itself
            (a) Step 1.
        \end{minipage}\hfill
        \begin{minipage}{0.244\textwidth}
            \centering
            \includegraphics[width=0.9\textwidth]{figures/koebe2}\\ % second figure itself
            (b) Step 2.
        \end{minipage}
        \begin{minipage}{0.244\textwidth}
            \centering
            \includegraphics[width=0.9\textwidth]{figures/koebe3}\\ % second figure itself
            (c) Step 3.
        \end{minipage}
        \begin{minipage}{0.244\textwidth}
            \centering
            \includegraphics[width=0.9\textwidth]{figures/koebe4}\\ % second figure itself
            (d) Step 4.
        \end{minipage}
        \caption{\cite[p.~2]{nachmias2018planar}.}
        \label{fig:steps}
    \end{figure}
    \\\textit{Sketch of Koebe's proof.} Let $G = (V, E)$ be a finite simple planar graph. Consider an embedding of $G$ (Figure \ref{fig:steps}a) in which the edges are given as the images of a family $(\gamma_e)_{e \in E}$ of simple curves $\gamma_e : [0,1] \to \mathbb{C}$. Let $\varepsilon > 0$ and define
    $$\Omega_\varepsilon = \mathbb{C} \setminus \left(\bigcup_{e \in E}\gamma_e\left[0, \frac{1}{2} - \varepsilon\right] \cup \bigcup_{e \in E} \gamma_e\left[\frac{1}{2} + \varepsilon, 1\right]\right).$$
    This is a $|V|$-connected subset of $\mathbb{C}$ (Figure \ref{fig:steps}b) that, by Theorem \ref{thm:koebe}, is conformally equivalent to a circle domain (Figure \ref{fig:steps}c). Taking the limit as $\varepsilon \to 0$ can be proven to yield the desired circle packing.\hfill\qed

    Perhaps recognizing the similar rigidity propreties of circle packings and conformal maps, William Thurston was led to propose the following scheme to approximate the conformal map in Theorem $\ref{thm:riemann}$. Let $\Omega$ be an open simply connected proper subset of $\mathbb{C}$ and let $(\varepsilon_n)_{n \in \mathbb{N}}$ be a sequence of positive real number such that $\varepsilon_n \to 0$ as $n \to \infty$. Consider the triangular lattice with lattice spacing $\varepsilon_n$
    $$\mathbb{T}_n = \left\{\varepsilon_n a + \varepsilon_n \frac{1+\sqrt{3}i}{2} b \mid a,b \in \mathbb{Z}\right\}$$ and connect two points if they are $\varepsilon$ apart from each other. This gives an infinite triangulation of the plane that can be naturally packed with circles of radius $\varepsilon_n/2$ centered at the points of $\mathbb{T}_n$. Let $P_n$ be the set of circles of this infinite packing that lie in the interior of $\Omega$. For $\varepsilon_n$ small enough we can assume $P_n$ to be a connected circle packing like the one shown in Figure \ref{fig:conf1}, left.
    \begin{figure}[h]
        \centering
        \includegraphics[width=1.0\textwidth]{figures/conf1}
        \caption{\cite[p.~5]{nachmias2018planar}.}
        \label{fig:conf1}
    \end{figure}
    In general the nerve of $P_n$ will not be a planar triangulation, as we can see in Figure \ref{fig:conf1}, left; the boundary circles correspond to a non-triangular face in the graph. To get a triangulation we add a new vertex $w$ and connect it to all the vertices that correspond to boundary circles. Now, by the Circle Packing Theorem, there exists a circle packing $P_n'$ in the sphere with nerve isomorphic to the nerve of $P_n$ with the added vertex $w$. We normalize $P_n'$ so, when projected to the plane, the circle corresponding to $w$ has boundary the unit circle centered at 0. This is illustrated in Figure \ref{fig:conf1}, right; the big circle containing all the other circles is the one corresponding to $w$ and his interior is actually $\mathbb{C}\setminus\{z \in \mathbb{C} \mid |z| \leq 1\}$. Consider the map $f_n$ sending the centers of the circles in $P_n$ to the corrisponding circles in $P_n'$ and extend it in a piecewise linear fashion. Thurston conjectured that this map, suitably normalized, converges to the biholomorphic map of Theorem \ref{thm:riemann} as the radii of the circles in the exagonal packing tend to 0 (Figure \ref{fig:conf2}).
    \begin{figure}[h!]
        \centering
        \includegraphics[width=1.0\textwidth]{figures/conf2}
        \caption{\cite[p.~5]{nachmias2018planar}.}
        \label{fig:conf2}
    \end{figure}


    Short after Thurston made his conjecture, Rodin and Sullivan solved it proving the following theorem.
    \begin{theorem}
        [\cite{rodin1987convergence}] Let $\Omega$ be a simply connected open proper subset of $\mathbb{C}$ and $p, q \in \Omega$. Normalize $P_n'$ as explained above, and so that
        \begin{itemize}
            \item the circle closest to $p$ corresponds to a circle containing 0;
            \item the circle closest to $q$ corresponds to a circle containing some positive real number.
        \end{itemize}
        Then $f_n$ converges to the conformal map $f: \Omega \to D$ of the Riemann Mapping Theorem \ref{thm:riemann}, normalized to have $f(p) = 0$ and $f(q) > 0$, uniformly on compact subsets of $\Omega$ as $n \to \infty$.
    \end{theorem}
    The proof of Rodin and Sullivan relies on the theory of quasiconformal maps and on the non-trivial uniqueness of the triangular packing as the only (up to rotation and homothety) infinite packing in the plane with nerve the triangular lattice. The theorem of Rudin and Sullivan deals with packings based on the triangular lattice; in  \cite{he1996convergence} He and Schramm give a generalization of this theorem in which they only require the circles of the 'covering' packing to have suitably bounded radii\footnote{They also define $f_n$ differently, see \cite{he1996convergence} for details.}. Their proof is also much more elementary and does not depend on the Riemann Mapping Theorem, contrary to the proof of Rudin and Sullivan. We have seen how, with Koebe's argument, the Rimann Mapping Theorem implies the Circle Packing Theorem. Conversely \cite{he1996convergence} can be used to give an independent proof of the Riemann Mapping Theorem using the Circle Packing Theorem. An analogus conjecture holds for $n$-connected domains.

    \begin{figure}[h!]
        \centering
        \begin{minipage}{0.36\textwidth}
            \includegraphics[width=\textwidth]{figures/tri1}
            \\[3mm]
            \includegraphics[width=\textwidth]{figures/tri2}
        \end{minipage}
        \hfill
        \begin{minipage}{0.55\columnwidth}
            \includegraphics[width=\textwidth]{figures/tri3}
        \end{minipage}
        \caption{\cite{rohde2011oded} A circle packing approximation for a 3-connected domain.}
        \label{fig:tri}
    \end{figure}

    In Figure \ref{fig:tri} we see an illustration of the approximation of the conformal mapping for a 3-connected domain into a circle domain. Similarly to what we did for the simply connected case, we add a new vertex fo each connected component of the boundary and add the necessary edges, to then apply the Circle Packing Theorem. Note how the 'big circles' in the packing (on the left bottom of Figure \ref{fig:tri}) correspond to the 'holes' in the domain.

    The proof of Thurston's conjecture shedded light to a deep connection between conformal mappings and circle packings. Maps like the $f_n$'s above may be thought as discrete analogs of conformal maps, and indeed, many classical results in complex analysis have a discrete counterpart that involve the theory of circle packings \cite{stephenson2002circle}.



    \section{Planar Separator Theorem}

    The planar separator theorem is an important result in graph theory with numerous applications in theoretical computer science. It states that a simple planar graph can be split evenly with the removal of a small subset of its vertex set. We dedicate the next pages to make this statement precise and give a proof using the circle packing theorem.

    \begin{definition}
        Let $G = (V, E)$ be a simple planar graph on $n$ vertices and let $A, B, S$ be a partition of the vertex set $V$. The set $S$ is a \textit{separator} for $G$ if no edge connects a vertex in A with a vertex in B.
    \end{definition}

     The planar separator theorem concerns the existence of a small separator that divides the graph evenly, that is, in parts of size at most $c n$, where $c \in (1/2,1)$ is a constant. The first result of this type is due to Ungar \cite{ungar1951theorem} and states that there exists a separator of size $\mathcal{O}(\sqrt{n} \log n)$ %\footnote{Big O notation}
     that splits the graph evenly. The planar separator theorem gives a bound of $\mathcal{O}(\sqrt{n})$ on the size of the separator and was first proven by Lipton \& Tarjan in 1979 \cite{lipton1979separator}. It was later discovered (Miller \textit{et al.} \cite{miller1997separators}) that the circle packing theorem implies the planar separator theorem quite easily. The proof we present can be found here \cite{har2011simple}.
\begin{wrapfigure}{R}{0.21\textwidth}
    \vspace{-20pt}
    \begin{center}
        \includegraphics[width=0.20\textwidth]{figures/seven}
    \end{center}
    \vspace{-20pt}
    \caption{}
    \vspace{-15pt}
    \label{fig:seven}
\end{wrapfigure}
    \begin{theorem}[Planar Separator Theorem]
        Let $G = (V, E)$ be a simple planar graph. There exists a partition $A, B, S$ of $G$ such that
        \begin{itemize}
            \item $S$ is a separator of size $|S| = \mathcal{O}(\sqrt{n})$;
            \item $|A| \leq (7/8) n$, $|B| \leq (7/8) n$ where $n = |G|$.
        \end{itemize}
    \end{theorem}
    \vspace{3mm}
     The constant $7/8$ in the statement of the theorem is the one that will come out of the proof, but is arbitrary and can be replaced with any number in the interval $(1/2,1)$. Another constant is hidden in the big O notation; in our case we will have $|S| \leq 4\sqrt{6}\sqrt{n}$ but it can be improved.

    \vspace{3mm}
    \noindent\textit{Proof of Theorem 3.6.} By the circle packing theorem there exists a circle packing $P$ in the plane with $G$ as its tangency graph. Let $N$ be the set of centers of the circles in $P$ and let $\mathcal{D}$ be the disk with the smallest radius containing $(1/8)n$ centers. We can assume that $\mathcal{D}$ is centered at the origin and has radius 1. Pick a number $x$ uniformly at random in the interval $[1, 2]$, and consider the circle $C_x$ of radius $x$ and centered at the origin. Denote with $S$ the set of circles in $P$ that intersect with $C_x$. We show that $S$ is the separator we want, starting with the following lemma.
    \begin{lemma}
    $S$ is a separator that splits $G$ in parts of size at most $(7/8)n$.
    \end{lemma}
    \begin{proof}
        It is clear that eliminating the circles of $S$ form $P$ we get at least two distinct components; the circles outside $C_x$ and the circles inside $C_x$. Therefore, we have a splitting of the graph.

        We know that $(1/8)n$ of the circles have their centers inside the circle of radius 1 centered at the origin. In Figure \ref{fig:seven} we can see how we can cover the circle of radius 2 with 7 circles of radius 1. Therefore, the circle of radius 2 contains at most $(7/8)n$ centers and therefore at least $(1/8)n$ circles have their centers outside $C_x$. Thus, removing $S$ from $G$, the remaining connected components can not be of size greater then $(7/8)n$.
    \end{proof}
    We now want to show that the size of $S$ is good in expectation.
    \begin{lemma}
        We have that $\mathbb{E}[|S|] \leq 4\sqrt{6}\sqrt{n}$.
    \end{lemma}
    \begin{proof}
        Let $\ell \in (0,1)$ be a paramenter to be specified later. Let $P_{\leq \ell}$ be the set of circles in P with radius less then or equal to $\ell$ and $P_{>\ell}$ be the set of circles in $P$ with radius greater then $\ell$. Conside the circular ring $R = \{z \in \mathbb{C} \mid x-\ell \leq |z| \leq x+\ell\}$
        \begin{figure}[h!]
            \centering
            \includegraphics[width=1.0\textwidth]{figures/sep}
            \caption{}
            \label{fig:sep}
        \end{figure}
        as the one in orange in Figure \ref{fig:sep}. The area of this ring is $\beta = \pi ((x+\ell)^2 - (x-\ell)^2) = 4\pi x\ell$. Given a disk $f \in P_{>\ell}$ intersecting $C_x$, there exists a disk of radius $\ell/2$ contained completely in $f$ and in $R$. Therefore $f$ covers at least an area of $\alpha = \pi (\ell/2)^2$ of the ring.
        Therefore, we can bound from above the number of disks in $P_{>\ell}$ intersecting $C_x$ with $\beta/\alpha = 4\pi x \ell / (\pi \ell^2/4) = 16x/\ell$. Remember that $x$ was chosen uniformly at random in the interval $[1,2]$, therefore we have $\mathbb{E}[x] = 3/2$ and thus $\mathbb{E}[\beta/\alpha] = 24/\ell$. Let $g \in P_{\leq \ell}$ of radius $r$ and centered at $p$. The circle $C_x$ intersects $g$ if and only if $x \in [\lVert p \rVert - r, \lVert p \rVert + r]$ and this happens with probability $2r / (2 - 1) = 2r \leq \ell$ as $x$ was chosen uniformly at random in the interval $[1, 2]$. Since $|P_{\leq \ell}| \leq n$, the expected number of disks in $P_{\leq \ell}$ intersecting $C_x$ is at most $\ell n$. Therefore, $\mathbb{E}[|S|] \leq 24/\ell + \ell n$. Choosing $\ell = 2\sqrt{6/n}$ we get the result.
    \end{proof}
    From the two lemmas it follows that there exists $x \in [1,2]$ such that $C_x$ leads to the desired separator and thus the theorem is proved.\hfill\qed

    \cleardoublepage
    \thispagestyle{empty}
    \clearpage\null\newpage
    \footnotesize
    \bibliographystyle{alpha}
    \bibliography{bibfile}
    \nocite{*}

\end{document}