Construction of planar embedding 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? 
 A: 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.
