I'm reading the following paper on universality considerations in VLSI circuits


<http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf>


In Theorem 2 On the second page it states there exists constants $c\_{1},c\_{2}$ such that $c\_{1}n^{2}\leq X\ll(n) \leq c\_{2}n^{2}$


In the construction it states $9n^{2}$ suffices. Can anybody explain how the explicit construction works? It states that the first $I$ vertices can be embedded in a grid of size $3I \times 3I$ and they use figure $2$ to explain it. However the explanation is brief and i can't seem to make sense of the construction i was wondering whether someone could provide some useful insights? 



Construction of planar embedding
Here are some more details. We will prove the following stronger claim. 


**Theorem.** Let $G$ be a planar graph with $n$ vertices and maximum degree 4. For every planar embedding $\Gamma$ of $G$, there is a rectilinear embedding $\Gamma'$ of $G$ such that $\Gamma$ and $\Gamma'$ have the same outer face, and $\Gamma'$ is contained in a $3n \times 3n$ grid. 


**Proof**. We proceed by induction on $n$. Clearly, the claim holds for $n=1$. For the inductive step let $\Gamma$ be an arbitrary planar embedding of $G$, and let $v$ be a vertex on the outerface of $\Gamma$. Let $\Gamma\_0$ be the embedding obtained from $\Gamma$ by deleting $v$. By induction, there is a rectilinear embedding $\Gamma\_0'$ of $G -v$, such that $\Gamma\_0$ and $\Gamma\_0'$ have the same outerface, and $\Gamma\_0'$ is contained in a $3(n-1) \times 3(n-1)$ grid. It remains to show that we can extend $\Gamma\_0'$ to a rectilinear embedding of $G$, while only increasing the grid size by $3$. This is shown in Figure $2$ of the [paper](http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf).


