--- abstract: | We give a new proof of Steinitz's classical theorem in the case of plane triangulations, which allows us to obtain a new general bound on the grid size of the simplicial polytope realizing a given triangulation, subexponential in a number of special cases. Formally, we prove that every plane triangulation $G$ with $n$ vertices can be embedded in $\rr^2$ in such a way that it is the vertical projection of a convex polyhedral surface. We show that the vertices of this surface may be placed in a $4n^3 \times 8n^5 \times \zeta(n)$ integer grid, where $\zeta(n) \leq (500 \ts n^8)^{\tau(G)}$ and $\tau(G)$ denotes the *shedding diameter* of $G$, a quantity defined in the paper. author: - 'Igor Pak$^\ast$ and Stedman Wilson$^\dagger$' title: A Quantitative Steinitz Theorem for Plane Triangulations --- Introduction ============ The celebrated *Steinitz's theorem* states every $3$-connected plane graph $G$ is the graph of a $3$-dimensional convex polytope. An important corollary of the original proof is that the vertices of the polytope can be made integers. The *Quantitative Steinitz Problem* @R asks for the smallest size of such integers as they depend on a graph. The best current bounds are exponential in the number of vertices in all three dimensions, even when restricted to triangulations, see @RRS. In this paper we improve these bounds in two directions. While the main result of this paper is rather technical (Theorem \[t:size\]), the following corollary requires no background. Let $G$ be a plane triangulation with $n$ vertices. Then $G$ is a graph of a convex polyhedron with vertices lying in a . $4\ts n^3 \times 8\ts n^5 \times (500\ts n^8)^{n}$ . integer grid. \[c:size\] This result improves known bounds in two directions at the expense of a somewhat weaker bound in the third direction. However, for large families of graphs we make sharp improvements in the third direction as well. Below we give our our main application. A *grid triangulation* of $[a \times b] = \{1, \ldots, a\} \times \{1, \ldots, b\}$ is a triangulation with all grid points as the set of vertices. These triangulations have a curious structure, and have been studied and enumerated in a number of papers (see @A [@KZ; @W] and references therein). Let $G$ be a grid triangulation of $[k \times k]$, such that every triangle fits in an $\ell \times \ell$ subgrid. Then $G$ is a graph of a convex polyhedron with vertices lying in a . $O(k^6) \times O(k^{10}) \times k^{O(\ell k)}$ . integer grid. \[c:grid\] Setting $\ell=O(1)$ as $k\to \infty$, for the grid triangulations as in the corollary, we have a subexponential grid size in the number $n=k^2$ of vertices: $O(n^3)\ts \times\ts O(n^5)\ts \times \. \exp O(\sqrt{n} \ts \log n)$. ![An example of a grid triangulation of $[5 \times 5]$, with $\ell = 3$.<span data-label="f:santos"></span>](grid1){height="3.5cm"} The basic idea behind the best known bounds in the quantitative Steinitz problem, is as follows (see @R [@RRS; @Ro]). Start with the *Tutte spring embedding* of $G$ with unit weights @T, and lift it up to a convex surface according to the *Maxwell–Cremona theorem* (see @L [@R]). Since Tutte's embedding and the lifting are given by rational equations, this embedding can be expanded to an integer embedding. However, there is only so much room for this method to work, and since the determinants are given by the number of spanning trees in $G$, the bounds cannot be made subexponential in the case of triangulations. Although there are several interesting proofs of the Steinitz theorem @Z1 [@Z2], neither seem to simplify in the case of triangulations. The proof we present follows a similar idea, but in place of the Tutte spring embedding we present an inductive construction. In essence, we construct a *strongly convex embedding* of plane triangulations, based on a standard inductive proof of *Fáry's theorem* @F. We make our construction quantitative, by doing this on a $O(n^3) \times O(n^5)$ grid, thus reproving a weak version of the main result in @BR. We then lift the resulting triangulation directly to a convex surface. The inductive argument allows us to obtain a new type of quantitative bound $\zeta(n)= n^{O(\tau(G))}$ on the height of the lifting. The parameter $\tau(G)$ here may be linear in $n$ in the worst case. It is bounded from below by both the diameter of $G$ and the diameter of the dual graph of $G$. However, this parameter is sublinear in a number of special cases, such as the grid triangulations mentioned above (see $\S$\[ss:fin-diam\]). The rest of this paper is structured as follows. In the next section we recall some definitions and basic results on *graph drawing*. In Section \[s:grid\] we prove Theorem \[plane\], the crucial technical result on graph embedding. Then, in Section \[s:diam\], we define the *shedding diameter* and prove Theorem \[t:size\], the main result of this paper. We discuss grid triangulations in Section \[s:grid-tri\], and conclude with final remarks in Section \[s:fin\]. Definitions and basic results {#s:def} ============================= Let $G = (V, E)$ denote a plane graph. By abuse of notation we will identify $G$ with the subset of ${{\mathbb R}}^2$ consisting of its vertices and edges. We write $V(G)$ for the vertices of $G$ and $E(G)$ for the edges of $G$. When $G$ is $2$-connected we let $\cF(G) = \{F_1, \ldots, F_m\}$ denote the set of (closed) bounded faces of $G$. We define $\F(G) = \bigcup_i F_i$, the region of ${{\mathbb R}}^2$ determined by $G$. For a subgraph $H$ of $G$, we write $H \subseteq G$. When $G$ is $2$-connected, a vertex $v \in V$ is called a *boundary vertex* if $v$ is in the boundary of $\F(G)$, and an *interior* vertex otherwise. Similarly, an edge $e \in E$ is called a *boundary edge* if $e$ is completely contained in the boundary of $\F(G)$, and an *interior edge* otherwise. A *diagonal* of $G$ is an interior edge whose endpoints are boundary vertices of $G$. For a plane graph $G$ with vertex $v$, let $G - \{v\}$ denote the plane graph obtained by removing $v$ and all edges adjacent to $v$. Let $\Delta(G)$ denote the diameter of $G$. We say that two plane graphs $G, G'$ are *face isomorphic*, written $G \sim G'$, if there is a graph isomorphism $\psi : V(G) \rightarrow V(G')$ that also induces a bijection $\psi_\cF : \cF(G) \rightarrow \cF(G')$ of the bounded faces of $G$ and $G'$. This last property means that $v_1, \ldots, v_k$ are the vertices of a face $F \in \cF(G)$ if and only if $\psi(v_1), \ldots, \psi(v_k)$ are the vertices of a face $F' \in \cF(G')$. By definition, $G \sim G'$ implies that $G$ and $G'$ are isomorphic as abstract graphs, but the converse in not always true. When $G \sim G'$ and $v$ is a vertex of $G$, we will write $v'$ for the corresponding vertex of $G'$, indicating that a face isomorphism $\psi$ is defined by $v' = \psi(v)$. A *geometric* plane graph is a plane graph for which each edge is a straight line segment. A *geometric embedding* of a plane graph $G$ *in the set* $S \subseteq {{\mathbb R}}^2$ is a geometric plane graph $G'$ such that $G \sim G'$ and every vertex of $G'$ is a point of $S$. For a point $u = (a, b) \in {{\mathbb R}}^2$, we will write $x(u) = a$ and $y(u) = b$ for the standard projections. For a plane graph $G$ with $n$ vertices and an ordering of the vertices $\ba = (a_1, \ldots, a_n)$, we define a sequence of plane graphs $G_0(\ba), \ldots, G_n(\ba)$ recursively by $G_n(\ba) = G$ and $G_{i - 1}(\ba) = G_i(\ba) - \{a_i\}$. We will write $G_i$ for $G_i(\ba)$ when $\ba$ is understood. If $v$ is a vertex of $G_i$ then we let $d_i(v)$ denote the degree of $v$ *in the graph $G_i$*. A *plane triangulation* is a $2$-connected plane graph $G$ such that each bounded face of $G$ has exactly $3$ vertices. Note in particular that if $G$ is a plane triangulation then $\F(G)$ is homeomorphic to a $2$-ball. A boundary vertex $v$ of a plane triangulation $G$ is a *shedding vertex* of $G$ if $G - \{v\}$ is a plane triangulation. Let $G$ be a plane triangulation with $n$ vertices. A vertex sequence $\ba = (a_1, \ldots, a_n)$ is called a *shedding sequence* for $G$ if $a_i$ is a shedding vertex of $G_i(\ba)$ for all $i = 4, \ldots, n$. We have the following technical lemma given in @FPP [$\S$2], where it was used for an effective embedding of graphs. \[@FPP\] Let $G$ be a plane triangulation. Then, for every boundary edge $uv$ of $G$, there is a shedding sequence $\ba = (a_1,\ldots, a_n)$ for $G$, such that $u = a_1$ and $v = a_2$. \[shedding\] We say that a *strictly* convex polygon $P \subset {{\mathbb R}}^2$ with edge $e$ is *projectively convex* with respect to $e$ if $P$ is contained in a triangle having $e$ as an edge. A shedding sequence $\ba = (a_1, \ldots, a_n)$ for a plane triangulation $G$ is a *convex shedding sequence* if the region $\F(G_i(\ba))$ is a projectively convex polygon with respect to the edge $a_1a_2$ for all $i = 3, \ldots, n$. A geometric embedding $G'$ of $G$ is *sequentially convex* if $G'$ has a convex shedding sequence. Drawing the triangulation on a grid {#s:tri} =================================== A Rational Embedding -------------------- First we address a much easier question: How does one obtain a sequentially convex embedding of $G$ in $\qqq^2$ (that is, with vertex coordinates *rational*)? We describe a simple construction that produces such an embedding. The method used to accomplish this easier task will provide part of the motivation and intuition behind the more involved method we will use to obtain a polynomially sized embedding in ${{\mathbb Z}}^2$. Let $G$ be a plane triangulation with $n$ vertices and boundary edge $uv$, and let $\ba = (a_1, \ldots, a_n)$ be a shedding sequence for $G$ with $u= a_1$, $v = a_2$. Then $G$ has a geometric embedding $G'$ in $\qqq^2$, such that the corresponding sequence $\ba' = (a_1', \ldots, a_n')$ is a convex shedding sequence for $G'$. \[t:rational\] To simplify the proof, we make the stronger claim that the edge $a_1'a_2'$ lies along the $x$-axis, with $a_1'$ to the left of $a_2'$, and $G'$ lies in the upper half-plane. We proceed by induction on $n$. If $n = 3$ then we may take the triangle with coordinates $a_1' = (0, 0)$, $a_2' = (2, 0)$, $a_3' = (1, 1)$ as a sequentially convex embedding of $G$ in $\qqq^2$. If $n > 3$, then by the inductive hypothesis there is an embedding $G_{n - 1}'$ of $G_{n - 1}$ in $\qqq^2$ such that $(a_1', \ldots, a_{n - 1}')$ is a convex shedding sequence for $G_{n - 1}'$, and furthermore $y(a_1') = y(a_2') = 0$, $x(a_1') < x(a_2')$, and $G_{n - 1}'$ lies in the upper half-plane. Let $w_1, \ldots, w_k$ denote the neighbors of $a_n$ in $G$, and let $w_1', \ldots, w_k'$ denote the corresponding vertices of $G_{n - 1}'$, ordered from left to right. If $w_1' \neq a_1'$, then let $z_1'$ denote the left boundary neighbor of $w_1'$. Similarly, if $w_k' \neq a_2'$, let $z_2'$ denote the right boundary neighbor of $w_k'$. For adjacent vertices $u$ and $v$, we will denote the slope of the edge $uv$ by $s(uv)$. Similarly, we will denote the slope of a line $\ell$ by $s(\ell)$. Consider the lines $\ell_1, \ell_2, \ell_3, \ell_4$ spanned by the edges $z_1'w_1'$, $w_1'w_2'$, $w_{k - 1}'w_k'$, and $w_k'z_2'$, respectively. If $w_1' = a_1'$, we may take $\ell_1$ to be any non-vertical line passing through $a_1'$, with slope satisfying $s(\ell_1) > s(\ell_2)$. Similarly, if $w_k' = a_2'$, we may take $\ell_4$ to be any non-vertical line passing through $v'$, with slope satisfying $s(\ell_3) > s(\ell_4)$. Let $A_1, A_4 \subset {{\mathbb R}}^2$ denote the open half-planes below the lines $\ell_1$ and $\ell_4$, respectively, and let $A_2$ and $A_3$ denote the open half-planes above the lines $\ell_2$ and $\ell_3$, respectively. Since $\F(G_{n - 1}')$ is projectively convex with respect to $a_1'a_2'$, the slopes of the lines $\ell_i$ must satisfy $s(\ell_1) > s(\ell_2) > s(\ell_3) > s(\ell_4)$. Thus the region $S = A_1 \cap A_2 \cap A_3 \cap A_4$ is non-empty (see Figure \[f:newvertexset\]). Since each set $A_i$ is open, the set $S$ is open, so we may choose a rational point in $S$, call it $a_n'$. For each $j = 1, \ldots, k$ add a straight line segment $e_j$ between $a_n'$ and the vertex $w_j'$. Since $a_n'$ lies in the region above the lines $\ell_2$ and $\ell_3$, each line segment $e_j$ will intersect $G_{n - 1}'$ only in the vertex $w_j'$. \[width=11cm\]<span>newvertexset</span> (17, 20)<span>$G_{n - 1}'$</span> (79, 20)<span>$G'$</span> (16, 50)<span>$a_n'$</span> (3, 20)<span>$\ell_1$</span> (8, 49)<span>$\ell_3$</span> (24, 57)<span>$\ell_2$</span> (30, 29)<span>$\ell_4$</span> (2, 1.5)<span>$w_1'$</span> (5, 33)<span>$w_2'$</span> (22, 38)<span>$w_3'$</span> (33, 20)<span>$w_4'$</span> (58, 1.5)<span>$a_1'$</span> (100, 1.5)<span>$a_2'$</span> (76, 50)<span>$a_n'$</span> (17, 55)<span>$S$</span> Let $G'$ denote the plane graph obtained from $G_{n - 1}'$ by adding the vertex $a_n'$ and the edges $e_j$. Then $G'$ is clearly a geometric embedding of $G_n = G$, such that each vertex $a_i$ corresponds to $a_i'$, for $i = 1, \ldots, n$. Furthermore, since $a_n'$ lies in the region below the lines $\ell_1$ and $\ell_4$, the region $\F(G')$ is projectively convex with respect to $a_1'a_2'$. From this, together with the fact that $(a_1', \ldots, a_{n - 1}')$ is a convex shedding sequence for $G_{n - 1}'$, we have that $\ba' = (a_1', \ldots, a_n')$ is a convex shedding sequence for $G'$. The Shedding Tree of a Plane Triangulation ------------------------------------------ Now we address the problem of embedding the triangulation $G$ on an integer grid. The idea behind our construction is roughly as follows. We start with a triangular base whose the horizontal width is very large. We then show that, because this horizontal width is large enough, we may add each vertex in a manner similar to that used in the proof of Theorem \[t:rational\], and we will always have enough room to find an acceptable integer coordinate. The crucial part of the construction is the careful method in which we add each new vertex. In particular, there are two distinct methods for adding the new vertex $a_i$, depending on whether $d_i(a_i) = 2$ or $d_i(a_i) > 2$. To facilitate the proper placement of the vertices $a_i$ with $d_i(a_i) = 2$, we will appeal to a certain tree structure determined by the shedding sequence $\ba$. We introduce the following definitions. Let $G$ be a plane triangulation with shedding sequence $\ba$. We may assume that $G$ is embedded geometrically as in Theorem \[t:rational\]. Proceeding recursively, we define a binary tree $T = T(G, \ba)$, such that the nodes of $T$ are edges of $G$, and the edges of $T$ correspond to faces of $G$. Let $\nu_2$ denote the edge of $G$ containing vertices $a_1, a_2$, and let $T_2$ be the tree consisting of the single node $\nu_2$. Now let $3 \leq i \leq n$, and let $\nu_i, \nu_i'$ denote the boundary edges of $G_i(\ba)$ immediately to the left and right of $a_i$, respectively (this is well defined because $G$ is embedded as in Theorem \[t:rational\]). Assume that we have already constructed $T_{i - 1}$, and that all boundary edges of $G_{i - 1}(\ba)$ are nodes of $T_{i - 1}$. Let $\xi, \xi'$ be the boundary edges of $G_{i - 1}(\ba)$ such that $\xi$ shares a face with $\nu_i$, and $\xi'$ shares a face with $\nu_i'$. Define $T_i = T_i(G, \ba)$ to be the tree obtained from $T_{i - 1}$ by adding $\nu_i$ and $\nu_i'$ as nodes, and adding the edges $(\xi, \nu_i)$ and $(\xi', \nu_i')$, designated *left* and *right*, respectively. Then clearly all boundary edges of $G_i(\ba)$ are vertices of $T_i$. Thus we have a recursively defined sequence of trees $(T_2, T_3, \ldots, T_n)$, and nodes $(\nu_2, \nu_3, \nu_3', \ldots, \nu_n, \nu_n')$, such that $T_i$ has nodes $\nu_2, \nu_3, \nu_3', \ldots, \nu_i, \nu_i'$. We call the trees $T_i(G, \ba)$ the *shedding trees* of $G$, and we write $T = T_n$ (see Figure \[f:tree\]). Note that for all $i = 2, \ldots, n$, we have $T_i(G, \ba) = T(G_i(\ba), (a_1, \ldots, a_i))$. Let ${\mathcal{R}}= \{i \in \{1, \ldots, n\} \ | \ d_i(a_i) \leq 2\}$, and define a set of edges $$E_{\mathcal{R}}= \{(\xi, \sigma) \in E(T) \ | \ \text{$\sigma = \nu_j$ or $\sigma = \nu_j'$ for some $j \notin {\mathcal{R}}$}\}.$$ Let $T_i^\ast = T_i^\ast(G, \ba)$ be the tree obtained from $T_i$ by contracting all edges in $E(T_i) \cap E_{\mathcal{R}}$ (shown in blue in Figure \[f:tree\]). Note that each $T_i^\ast$ is a *full* binary tree. We call the trees $T_i^*$ the *reduced trees* of $G$, and we write $T^\ast = T_n^\ast$. If $d_i(a_i) = 2$ for all $i \geq 3$, then $T^\ast = T$. \[width=11.5cm\]<span>sheddingtree</span> (1, 47)<span>$G$</span> (97, 47)<span>$G^\ast$</span> (1, 3)<span>$T$</span> (97, 3)<span>$T^\ast$</span> (0, 24)<span>$a_1$</span> (39, 24)<span>$a_2$</span> (59, 24)<span>$a_1$</span> (97, 24)<span>$a_2$</span> A fundamental idea behind our integer grid embedding is that the reduced tree $T^\ast$ contains all of the critical information needed for carrying out the embedding of $G$. For example, for each $i \in {\mathcal{R}}- \{1, 2\}$, the vertex $a_i$ corresponds to an internal node of $T^\ast$ (shown as large dots in Figure \[f:tree\]). Thus the structure of $T^\ast$ tells us how to horizontally space the vertices $a_i$ with $d_i(a_i) = 2$, and how to choose the slopes of the boundary edges adjacent to them. On the other hand, when adding vertices $a_i$ with $d_i(a_i) > 2$, our construction will have the property that the boundary slopes will be perturbed only slightly, and the horizontal distances between vertices will only increase. Furthermore, throughout our entire construction the total horizontal width of the embedding will remain fixed. Given a subsequence of $T_2^*, T_3^*, \ldots, T_n^*$ consisting of the *distinct* reduced trees of $G$, there is a natural construction which produces a triangulation $G^*$ and shedding sequence $\ba^\ast$, such that the distinct reduced trees of $G$ are exactly the shedding trees of $G^\ast$. This construction is the content of the next lemma. That is, we will use Lemma \[t:degree2\] to define $G^\ast$ precisely in Section \[s:grid\]. This lemma can also be thought of as a special instance of Theorem \[plane\], in the case that $d_i(a_i) = 2$ for all $i \geq 3$. Let $n \geq 3$, and let $(t_2, \ldots, t_n)$ be a sequence of full binary trees, such that $t_{i - 1}$ is a subtree of $t_i$, and $t_i$ has $1 + 2(i - 2)$ nodes, for all $i = 2, \ldots, n$. Then there is a sequentially convex plane triangulation $H$ with $n$ vertices, embedded in a $2(n - 2) \times \binom{n - 1}{2}$ integer grid, and a convex shedding sequence $\ba$ for $H$, such that $t_i$ is isomorphic to $T_i(H, \ba)$ for all $\nobreak{i = 2, \ldots, n}$. \[t:degree2\] Let $m$ and $m'$ denote the number of internal nodes of $t_n$ to the left and right of the root node, respectively. Note that $m + m' + 3 = n$. Without loss of generality we may assume $m \leq m'$. For $-m \leq k \leq m' + 1$, we define $$x_k = k, \quad \quad \quad y_k = \binom{m' + 2}{2} - \binom{|k| + 1}{2}.$$ Additionally, we define $$x_{-m - 1} = -x_{m' + 1}, \quad \quad \quad y_{-m - 1} = 0.$$ Note that the $n$ points $(x_k, y_k)$ all lie on the (piecewise) parabola defined by $$y \. = \. -\ts \frac{x^2+|x|}{2} \. + \. \frac{(m' + 2)(m' + 1)}{2}.$$ These points will serve as the vertices of the triangulation $H$ (compare with the vertices of $G^*$ in Figure \[f:tree\]). For all $i = 3, \ldots, n$, since $t_i$ is full and contains two more nodes than $t_{i - 1}$, it follows that $t_i$ contains exactly one more internal node than $t_{i - 1}$. Let $(\xi_3, \ldots \xi_n)$ denote the sequence of internal nodes so obtained. Note that $\xi_3$ is the root node of all the trees $t_i$, and $t_2$ consists of the single node $\xi_3$. The nodes of $t_n$ may be linearly ordered by a depth-first search on $t_n$, such that left nodes are visited before right nodes. Call this order $\Omega$. This restricts to a linear order on the internal nodes of $t_n$, which induces a permutation $\omega : \{3, \ldots, n\} \rightarrow \{3, \ldots, n\}$. That is, node $\xi_i$ has position $\omega(i)$ in the order $\Omega$. Then we define a sequence of points $\ba = (a_1, a_2, \ldots, a_n)$ by $$\begin{array}{cclc} a_1 & = & (x_{-m - 1}, y_{-m - 1}),& \\ a_2 & = & (x_{m' + 1}, y_{m' + 1}), &\\ a_i & = & (x_{\omega(i) - m - 3}, y_{\omega(i) - m - 3}) & \text{for $3 \leq i \leq n$.} \end{array}$$ For $\nobreak{i = 3, \ldots, n}$, let $\nobreak{\omega_i : \{3, \ldots, i\} \rightarrow \{3, \ldots, i\}}$ denote the permutation induced by restricting the order $\Omega$ to the internal nodes $(\xi_3, \ldots, \xi_i)$ of $t_i$. Note that $\omega = \omega_n$. For each $\nobreak{i = 3, \ldots, n}$, we would like to determine the internal nodes of $t_i$ that immediately precede and succeed $\xi_i$ in the order $\omega_i$. For this purpose, we define functions $$f, g : \{3, \ldots, n\} \rightarrow \{1, \ldots, n\}$$ as follows. $$\begin{aligned} f(i) & = \begin{cases} \omega_i^{-1}(\omega_i(i) - 1) & \text{if $\omega_i(i) > 3$}, \\ 1 & \text{otherwise} \end{cases} \\ g(i) & = \begin{cases} \omega_i^{-1}(\omega_i(i) + 1) & \text{if $\omega_i(i) < i$}, \\ 2 & \text{otherwise.} \end{cases}\end{aligned}$$ We may now define a sequence of plane triangulations $H_1, \ldots, H_n$ recursively. Let $H_1$ consist of the single vertex $a_1$, and let $H_2$ consist of the vertices $a_1$, $a_2$ and the line segment $a_1a_2$. Now let $3 \leq i \leq n$, and suppose we have constructed $H_{i - 1}$. We obtain $H_i$ by adding the vertex $a_i$ and the line segments $a_ia_{f(i)}$ and $a_ia_{g(i)}$ to $H_{i - 1}$. This completes the construction of the graphs $H_2, \ldots, H_n$. We write $H = H_n$. We now check that $\ba = (a_1, \ldots, a_n)$ is a convex shedding sequence for $H$. By construction, we have immediately that $H_i$ is a plane triangulation with $H_{i - 1} = H_i - \{a_i\}$ for all $\nobreak{i = 2, \ldots, n}$, and furthermore $d_i(a_i) = 2$ for all $i \geq 3$. For $k \geq -m$, the slope of the edge between adjacent vertices $(x_k, y_k)$ and $(x_{k + 1}, y_{k + 1})$ of $H$ is $$\frac{y_{k + 1} - y_k}{x_{k + 1} - x_k} = \binom{|k| + 1}{2} - \binom{|k + 1| + 1}{2} = \begin{cases} -(k + 1) & \text{if $k \geq 0$}, \\ -k & \text{if $k < 0$.} \end{cases}$$ Additionally, the slope of the edge between $(x_{-m - 1}, y_{-m - 1})$ and $(x_{-m}, y_{-m})$ is $$\begin{aligned} & \frac{y_{-m} - y_{-m-1}}{x_{-m} - x_{-m-1}} = \frac{y_{-m}}{-m + (m' + 1)} = \frac{1}{m' - m + 1}\left[\binom{m' + 2}{2} - \binom{m + 1}{2}\right] \\ &= \frac{(m' + 2)(m' + 1) - (m + 1)m}{2(m' - m + 1)} = \frac{(m' - m + 1)(m' + m + 2)}{2(m' - m + 1)} \\ &= \frac{m' + m + 2}{2} \geq \frac{m + m + 2}{2} = m + 1. \end{aligned}$$ Thus the boundary edge slopes of $H$ are strictly decreasing from left to right. Since $\nobreak{d_i(a_i) = 2}$ for all $i \geq 3$, this implies that the boundary edge slopes of each $H_i$ are also strictly decreasing from left to right. It follows that $\F(H_i)$ is projectively convex, for all $i \geq 3$. Hence $\ba$ is a convex shedding sequence for $H$. To see that $t_i$ is isomorphic to $T_i(H, \ba)$ for all $i = 2, \ldots, n$, we construct an explicit isomorphism. We define a map $\psi_2 : t_2 \rightarrow T_2(H, \ba)$ by $\psi_2(\xi_3) = a_{f(3)}a_{g(3)} = a_1a_2$, which is trivially an isomorphism. For $i \geq 3$, and $j = 3, \ldots, i$, let $\xi_j^-$ and $\xi_j^+$ denote the left and right child, respectively, of the internal node $\xi_j$ of $t_i$. We define a map $\psi_i : t_i \rightarrow T_i(H, \ba)$ by $$\begin{array}{lclr} \psi_i(\xi_j) & = & a_{f(j)}a_{g(j)}, & \\ \psi_i(\xi_j^-) & = & a_ja_{f(j)}, & \\ \psi_i(\xi_j^+) & = & a_ja_{g(j)} & \quad \text{for $j = 3, \ldots, i$}. \end{array}$$ From the definition of the order $\Omega$ and the resulting functions $f$ and $g$, it is straightforward to check that $\psi_i$ is well-defined and bijective. Since the triangle $(a_ja_{f(j)}a_{g(j)})$ is a face of $H_j$ for all $j = 3, \ldots, i$, the pairs $(a_{f(j)}a_{g(j)}, a_ja_{f(j)})$ and $(a_{f(j)}a_{g(j)}, a_ja_{g(j)})$ are edges of $T_i(H, \ba)$. Thus $\psi_i$ is clearly a tree isomorphism. We may think of $\psi_n$ as providing a correspondence between the internal node $\xi_i$ and the vertex $a_i$ (whose neighbors in $H_i$ are $a_{f(i)}$ and $a_{g(i)}$), for all $i = 3, \ldots, n$ (see Figure \[f:tree\]). Finally, the width of the grid is $$x_{m' + 1} - x_{-m - 1} = 2x_{m' + 1} = 2(m' + 1) \leq 2(n - 2),$$ and the height of the grid is $$y_0 = \binom{m' + 2}{2} \leq \binom{n - 1}{2}.$$ Therefore $H$ is embedded in an integer grid of size $2(n - 2) \times \binom{n - 1}{2}$. The Integer Grid Embedding {#s:grid} -------------------------- Given a plane triangulation $G$ with $n$ vertices and shedding sequence $\ba$, let $t_i = T_i^\ast(G, \ba)$ denote the reduced trees of $G$. Let $\rho$ denote the unique increasing bijection from ${\mathcal{R}}$ to $\{1, \ldots, R\}$, where ${\mathcal{R}}$ is the subset of $\{1, \ldots, n\}$ defined above, and $R = |{\mathcal{R}}|$. Note that $\nobreak{1, 2, 3 \in {\mathcal{R}}}$, so $\rho(1) = 1, \rho(2) = 2, \rho(3) = 3$. Define a map $\nobreak{h : \{1, \ldots, n\} \rightarrow \{1, \ldots, R\}}$ by taking $h(i)$ to be the unique index for which $$\rho^{-1}(h(i)) \leq i < \rho^{-1}(h(i) + 1).$$ (We require the inequality on the right to hold only when $h(i) + 1 \leq R$.) In particular, if $i \in {\mathcal{R}}$ then $h(i) = \rho(i)$. The sequence of distinct trees $t_{\rho^{-1}(1)}, \ldots, t_{\rho^{-1}(R)}$ satisfies the hypotheses of Lemma \[t:degree2\]. Therefore we let $G^\ast$ denote the sequentially convex triangulation constructed from this sequence of trees as in Lemma \[t:degree2\]. That is, $G^\ast$ is the triangulation $H$ in the notation of the lemma, and $G^\ast$ has the exact vertex coordinates given in the lemma. We let $\ba^\ast = (a_1^\ast, \ldots, a_R^\ast)$ denote the corresponding convex shedding sequence of $G^\ast$ produced by Lemma \[t:degree2\]. We also define $G_i^\ast = G^\ast_i(\ba^\ast)$ for all $i = 1, \ldots, R$, so in particular $G^\ast_R = G^\ast$. We call the $G_i^\ast$ the *reduced triangulations* of $G$ (see Figure \[f:tree\]). Note that each vertex $a_i^\ast$ has degree $2$ in $G_i^\ast$. So we may think of $G^\ast$ as being obtained from $G$ by "throwing away" all vertices $a_i$ for which $d_i(a_i) > 2$. It was this property that originally motivated our definition of $G^\ast$. As we will see, the triangulation $G^\ast$ will tell us exactly how to add vertices of degree $2$, in our construction of a sequentially convex embedding of $G$. A particular property of the reduced triangulations makes this possible. Namely, for any boundary edge $e$ of $G_i$, there is a *corresponding boundary edge* $e^\ast$ of $G_{h(i)}^\ast$, which we define as follows. First note that from the definitions, the trees $T_{h(i)}(G^\ast, \ba^\ast)$ and $T_i^\ast(G, \ba)$ are isomorphic. Thus we may think of an edge of $G_{h(i)}^\ast$ (which is a node of $T_{h(i)}(G^\ast, \ba^\ast)$) as a node of $T_i^\ast(G, \ba)$. So for a boundary edge $e$ of $G_i$, we denote by $e^\ast$ the unique boundary edge of $G_{h(i)}^\ast$ (thought of as a node of $T_i^\ast(G, \ba)$), that is identified with the node $e$ of $T_i(G, \ba)$ upon contracting the edges in the set $E_{\mathcal{R}}$. Let $G$ be a plane triangulation with $n$ vertices and boundary edge $uv$, and let $\ba = (a_1, \ldots, a_n)$ be a shedding sequence for $G$ with $u = a_1$, $v = a_2$. Then $G$ has a geometric embedding $G'$ in a $4n^3 \times 8n^5$ integer grid, such that the corresponding sequence $\ba' = (a_1', \ldots,a_n')$ is a convex shedding sequence for $G'$. \[plane\] We recursively construct a sequence of graphs $G_1', \ldots, G_n'$, and a sequence of vertices $a_1', \ldots, a_n'$, such that each $G'_i$ is a geometric embedding of $G_i$ with convex shedding sequence $\ba' = (a_1', \ldots, a_i')$, where $a_i'$ is the vertex of $G'$ corresponding to $a_i$. Let $G_i^*$ denote the reduced triangulations of $G$, and let $\ba^\ast = (a_1^\ast, \ldots, a_{R}^\ast)$ denote the corresponding shedding sequence for $G^\ast$. Let $m'$ denote the number of vertices of $G^\ast$ lying between $a_3^\ast$ and $a_2^\ast$, and $m$ the number of vertices lying between $a_1^\ast$ and $a_3^\ast$. Then $m' + m + 3 = n$. Without loss of generality we may assume that $m \leq m'$. For points $v_1, v_2 \in {{\mathbb R}}^2$ and $e = v_1 v_2$ the line segment between them, we write $$x(e) = |x(v_1) - x(v_2)| \quad \quad \text{and} \quad \quad y(e) = |y(v_1) - y(v_2)|.$$ We first scale $G^\ast$ to obtain a much larger triangulation, which we will use to construct the triangulations $G_i'$. We choose the scaling factors large enough so that we will have "enough room" to carry out our constructions. Specifically, let $\alpha = 2n^2 + n + 1$ and $\beta = 2n\alpha$. We define $Z_i$ to be the result of scaling $G_i^*$ by a factor of $\alpha$ in the $x$ dimension and $\beta$ in the $y$ dimension. That is, for each $i = 1, \ldots, R$, we define $z_i = (\alpha x(a_i^\ast), \beta y(a_i^\ast))$. Then $\bz = (z_1, \ldots, z_R)$ is the shedding sequence for $Z_R$ corresponding to $\ba^\ast$. We write $Z = Z_R$. Since $G_i' \sim G_i$ (as we verify below) the edges of $G_i'$ and $G_i$ are in correspondence. Thus every boundary edge $e$ of $G_i'$ has a *corresponding boundary edge* $e^\ast$ of $G_{h(i)}^\ast$, as defined above. We then write $Z(e)$ for the edge of $Z_{h(i)}$ corresponding to $e^\ast$. Note that if $e^\ast$ has slope $s$, then $Z(e)$ has slope $\frac{\beta}{\alpha}s$. In particular, since $m' + 1$ is the largest magnitude of the slope of any edge of $G^\ast$, we see that $\frac{\beta}{\alpha}(m' + 1) = 2n(m' + 1)$ is the largest magnitude of the slope of any edge of $Z$. Let $M$ denote this slope, and note that $M \leq 2n^2$. Note also that the absolute difference of two boundary edge slopes of $Z$ is at least $\frac{\beta}{\alpha} = 2n$. It follows immediately that for each $i = 1, \ldots, R$, the absolute difference of two boundary edge slopes of $Z_i$ is at least $2n$. Define $a_1' = z_1$ and $a_2' = z_2$. Take $G_1'$ to consist of the single vertex $a_1'$, and take $G_2'$ to consist of the vertices $a_1', a_2'$, together with the line segment $a_1'a_2'$. Now let $3 \leq i \leq n$, and suppose we have constructed $G_{i - 1}'$. To define $a_i'$, we consider two cases, namely whether $d_i(a_i) = 2$ or $d_i(a_i) > 2$. \[height=4cm\]<span>deg4vertex</span> (47, 10)<span>$G_{i - 1}'$</span> (41, 20)<span>$(\overline{x}, \overline{y})$</span> (37.5, 30)<span>$a_i' = (x', y')$</span> (0, 3.5)<span>$w_1'$</span> (23, 17)<span>$w_2'$</span> (52, 17)<span>$w_3'$</span> (77, 14)<span>$w_4'$</span> (11, 33)<span>$\ell_u$</span> (62, 33)<span>$\ell_s$</span> **Construction of $a_i'$, in the case $d_i(a_i) > 2$**. If $d_i(a_i) > 2$, then let $w_1, \ldots, w_k$ denote the neighbors of $a_i$ in $G_i$, and let $w_1', \ldots, w_k'$ denote the corresponding vertices of $G_{i - 1}'$, ordered from left to right. Let $s$ denote the slope of the edge $w_1'w_2'$, and $u$ the slope of the edge $w_{k - 1}'w_k'$. Let $\ell_s$ denote the line of slope $s$ containing the point $w_1'$, and $\ell_u$ the line of slope $u$ containing the point $w_k'$. We denote by $(\overline{x}, \overline{y})$ the point of intersection of the lines $\ell_s$ and $\ell_u$. Let $x' = \lceil \overline{x} \rceil$ and $\gamma = x' - \overline{x}$, and let $y' = \lceil \overline{y} \rceil + \lfloor \gamma s \rfloor + 1$. We now define $a_i' = (x', y')$ (see Figure \[f:highdegree\]). We obtain $G_i'$ from $G_{i - 1}'$ by adding the vertex $a_i'$, together with all line segments between $a_i'$ and the vertices $w_1', \ldots, w_k'$. **Construction of $a_i'$, in the case $d_i(a_i) = 2$**. If $d_i(a_i) = 2$, then let $\Delta$ be the triangle of $Z_i$ containing $z_{\rho(i)}$. Let $w_1, w_2$ denote the boundary neighbors of $a_i$ in $G_i$, and let $w_1', w_2'$ denote the corresponding vertices of $G_{i - 1}'$, so that $w_1'$ lies to the left of $w_2'$. We are going to construct a triangle $\Delta'$, such that $\Delta'$ is the image of $\Delta$ under an affine map which is the composition of a uniform scaling and a translation. Furthermore, we will place $\Delta'$ in a specific position with respect to the triangulation $G_{i - 1}'$. In particular, if $v_1, v_2, v_3$ denote the vertices of $\Delta'$, we require that $x(v_1) = x(w_1')$, $v_2 = w_2'$, and $x(v_1) < x(v_3) < x(v_2)$ (see Figure \[f:degree2\]). It is easily verified that these conditions, together with the requirement that $\Delta'$ is a scaled, translated copy of $\Delta$, determine the vertices $v_1, v_2, v_3$ of $\Delta'$ uniquely. To define the new vertex $a_i'$, we start by applying a vertical shearing to the triangle $\Delta'$, namely the unique shearing that fixes $v_2 = w_2'$ and maps $v_1$ to $w_1'$. We will denote the image of $v_3$ under this shearing by $\overline{v_3}$. So in terms of the vertices of $Z_{\rho(i)}$ and $G_{i - 1}'$, the point $\overline{v_3}$ is defined as follows. Let $\eta = y(v_1) - y(w_1')$. Let $b_1$ and $b_2$ denote the left and right boundary neighbors, respectively, of $z_{\rho(i)}$ in $Z_{\rho(i)}$. Notice that the edge $b_1b_2 = Z(w_1'w_2')$ is a boundary edge of $Z_{h(i - 1)}$. We will define a ratio $\kappa$, which describes how far away $z_{\rho(i)}$ is from $b_2$, in the $x$ direction. That is, we define $$\kappa = \frac{x(b_2) - x(z_{\rho(i)})}{x(b_2) - x(b_1)}.$$ We may now define $\overline{v_3} = (x(v_3), y(v_3) - \kappa \eta)$. Note that $z_3$ is the apex of $Z_i$ for all $i = 1, \ldots, R$, and $x(z_3) = \alpha x(a_3^\ast) = \alpha \cdot 0 = 0$. So if $x(z_{\rho(i)}) < 0$ then $x(z_{\rho(i)})$ lies to the left of the apex of $Z_i$, and if $x(z_{\rho(i)}) > 0$ then $z_{\rho(i)}$ lies to the right of the apex. With this understanding, we let $$v_3' = \begin{cases} (\lfloor x(\overline{v_3}) \rfloor, \lceil y(\overline{v_3}) \rceil) & \text{if $x(z_{\rho(i)}) \leq 0$,} \\ (\lceil x(\overline{v_3}) \rceil, \lceil y(\overline{v_3}) \rceil) & \text{if $x(z_{\rho(i)}) > 0$.} \end{cases}$$ We now define $a_i' = v_3'$. We obtain $G_i'$ from $G_{i - 1}'$ by adding the vertex $a_i'$ and the two line segments between $a_i'$ and the vertices $w_1', w_2'$. \[height=6cm\]<span>deg2sim</span> (1, 47)<span>$Z_{\rho(i)}$</span> (90, 47)<span>$G_{i - 1}'$</span> (.5, 23)<span>$z_{\rho(i)}$</span> (3.5, 2.5)<span>$b_1$</span> (41.5, 2.5)<span>$z_2$</span> (20, 43)<span>$z_3$</span> (9, 35)<span>$b_2$</span> (55, 11)<span>$v_1$</span> (67.5, 53.5)<span>$v_2 = w_2'$</span> (63, 35)<span>$v_3$</span> (56, 5)<span>$\eta$</span> (62, 3)<span>$w_1'$</span> (0, 13)<span>$\Delta$</span> (59, 25)<span>$\Delta'$</span> **Verification of the construction.** We have now explicitly described the construction. It remains to show that the above constructions actually produce a *convex* shedding sequence $\ba' = (a_1', \ldots, a_n')$ for $G'$, and that $G'$ lies in the grid size indicated. Clearly, the horizontal width of the grid remains constant throughout the construction. Specifically, the triangulations $G_1', G_2', \ldots, G_n'$ all have the same width $\alpha 2(n - 2)$, which is the width of the $Z_i$. So to show that the construction is sequentially convex, and that the bound on the height of $G'$ is correct, we will calculate how the boundary slopes are modified when we add the new vertex $a_i'$ in the two cases $d_i(a_i) = 2$ and $d_i(a_i) > 2$. For each $3 \leq i \leq n$, let **$\cP(i)$** denote the conjunction of the following three properties, that we wish to show: $$\begin{aligned} {\mathcal{P}}(i, 1). & \quad \text{For every boundary edge $e$ of $G_i'$, we have $x(e) \geq x(Z(e))$.} \\ \cP(i, 2). & \quad \text{For every boundary edge $e$ of $G_i'$, the slopes of $e$ and $Z(e)$ differ by at most $i$.} \\ \cP(i, 3). & \quad \text{$G_i' \sim G_i$ and $G_i'$ has convex shedding sequence $(a_1', \ldots a_i')$.}\end{aligned}$$ To prove $\cP(i)$ for each $i = 3, \ldots, n$, we proceed by induction on $i$. For $i = 3$, note that $a_1' = z_1$, $a_2' = z_2$, and the vertex $a_3'$ is chosen so that in particular the triangle $(a_1'a_2'a_3')$ is a scaling of the triangle $(z_1z_2z_3) = \F(Z_3)$. This implies that $a_3' = z_3$. Thus $G_3' = Z_3$, which immediately establishes $\cP(3)$. Now let $i > 3$, and suppose that $\cP(i - 1)$ holds. As in the construction, we consider separately the cases $d_i(a_i) > 2$ and $d_i(a_i) = 2$. **Verification of $\cP(i)$ in the case $d_i(a_i) > 2$.** Clearly, we have $Z(w_1'a_i') = Z(w_1'w_2')$ and $Z(a_i'w_k') = Z(w_{k - 1}'w_k')$. Note that $x(w_2') \leq \overline{x} \leq x(w_{k - 1}')$, and thus $\nobreak{x(w_2') \leq x(a_i') \leq x(w_{k - 1}')}$. Therefore $$x(w_1'a_i') = x(a_i') - x(w_1') \geq x(w_2') - x(w_1') = x(w_2'w_1') \geq x(Z(w_2'w_1')) = x(Z(w_1'a_i')),$$ where the last inequality follows from $\cP(i - 1,1)$. Similarly, we have $x(a_i'w_2') \geq x(Z(a_i'w_2'))$. Thus $\cP(i, 1)$ holds. We now show that the slopes of the boundary edges of $G_i'$ containing $a_i'$ differ only slightly from the slopes $s$ and $u$ defined in the above construction. That is, let $s'$ denote the slope of the line passing through $w_1'$ and $a_i' = (x', y')$, and let $u'$ denote the slope of the line passing through $a_i'$ and $w_k'$. Since $$y' - \overline{y} = (\lceil \overline{y} \rceil - y) + \lfloor \gamma s \rfloor + 1 \geq \lfloor \gamma s \rfloor + 1 > \gamma s,$$ we clearly have $s' - s > 0$. On the other hand, $$\begin{aligned} & s' - s = \dfrac{y' - y(w_1')}{\overline{x} + \gamma - x(w_1')} - s = \dfrac{y' - y(w_1') - (\overline{x} - x(w_1'))s - \gamma s}{\overline{x} + \gamma - x(w_1')} = \dfrac{(y' - \overline{y}) - \gamma s}{\overline{x} + \gamma - x(w_1')} \\ &= \dfrac{(\lceil \overline{y} \rceil - y) + (\lfloor \gamma s \rfloor - \gamma s) + 1}{\overline{x} + \gamma - x(w_1')} < \dfrac{2}{\overline{x} + \gamma - x(w_1')} \leq \dfrac{2}{\overline{x} - x(w_1')} \leq \dfrac{2}{x(w_2') - x(w_1')} \\ &\leq \dfrac{2}{x(Z(w_2'w_1'))} \leq \dfrac{2}{\alpha} \leq 1. \end{aligned}$$ In the last line we have used $\cP(i - 1, 1)$. Since $s > u$, we have $y' - \overline{y} > \gamma s > \gamma u$. From this, together with the fact that $x' \geq \overline{x}$, it follows that $u - u' > 0$. By $\cP(i - 1, 2)$, we have $|s| \leq M + (i - 1)$. Thus $$\begin{aligned} & u - u' = \dfrac{y(w_k') - \overline{y}}{x(w_k') - \overline{x}} - \dfrac{y(w_k') - y'}{x(w_k') - x'} \leq \dfrac{y(w_k') - \overline{y}}{x(w_k') - x'} - \dfrac{y(w_k') - y'}{x(w_k') - x'} = \dfrac{y' - \overline{y}}{x(w_k') - x'} \\ &= \dfrac{(\lceil \overline{y} \rceil - \overline{y}) + \lfloor \gamma s \rfloor + 1}{x(w_k') - x'} < \dfrac{|s| + 2}{x(w_k') - x'} \leq \dfrac{|s| + 2}{x(w_k') - x(w_{k - 1}')} \leq \dfrac{|s| + 2}{x(Z(w_{k - 1}'w_k'))} \\ &\leq \dfrac{|s| + 2}{\alpha} \leq \dfrac{M + (i - 1) + 2}{\alpha} \leq \dfrac{2n^2 + i + 1}{\alpha} \leq \dfrac{2n^2 + n + 1}{\alpha} = 1. \end{aligned}$$ In the second line we have used $\cP(i - 1, 1)$. Let $Z(s)$ denote the slope of the edge $Z(w_1'w_2')$, and let $Z(u)$ denote the slope of $Z(w_{k - 1}'w_k')$. By $\cP(i - 1, 2)$, we have $|s - Z(s)| \leq i - 1$ and $|u - Z(u)| \leq i - 1$. Thus $$|s' - Z(s)| \leq |s' - s| + |s - Z(s)| \leq 1 + (i - 1) = i,$$ and similarly $|u' - Z(u)| \leq i$, so $\cP(i, 2)$ holds. Since $s' - s > 0$ and $u - u' > 0$, each line segment $a_i'w_j'$ intersects $G_{i - 1}'$ only in the vertex $w_j'$, for all $j = 1, \ldots k$. Thus $G_i'$ is a plane triangulation, and $G_i' \sim G_i$. It remains to show that $\F(G_i')$ is projectively convex, in order to establish $\cP(i, 3)$. To do this, we will show that when the slope $s$ is changed to $s'$ for example, convexity is preserved at the vertex $w_1'$. That is, the slope $s'$, while greater than $s$, is still less than the slope of the boundary edge to the left of $w_1'w_2'$. Let $\hat{s}$ denote the slope of the boundary edge of $G_i'$ adjacent and to the left of $w_1'$, if such an edge exists, and let $\hat{u}$ denote the slope of the boundary edge of $G_i'$ adjacent and to the right of $w_k'$, if such an edge exists. Let $Z(\hat{s})$ and $Z(\hat{u})$ denote the boundary slopes of $Z_{h(i - 1)}$ corresponding to $\hat{s}$ and $\hat{u}$, respectively. By $\cP(i - 1, 2)$, we have $s - Z(s) < i - 1$ and $Z(\hat{s}) - \hat{s} < i - 1$. Thus $$\begin{aligned} &\hat{s} - s = (\hat{s} - Z(s)) - (s - Z(s)) \geq (\hat{s} - Z(s)) - (i - 1) \\ &= (Z(\hat{s}) - Z(s)) - (Z(\hat{s}) - \hat{s}) - (i - 1) \geq (Z(\hat{s}) - Z(s)) - 2(i - 1) \\ & \geq 2n - 2i + 2 \geq 2. \end{aligned}$$ We conclude that $$\hat{s} - s' = (\hat{s} - s) - (s' - s) \geq (\hat{s} - s) - 1 \geq 2 - 1 = 1 > 0.$$ An analogous calculation shows that $u' - \hat{u} > 0$. Thus $w_1'$ and $w_k'$ are convex vertices of $G_i'$. Because the region $\F(G_{i - 1}')$ is projectively convex by $\cP(i - 1, 3)$, we conclude that $\F(G_i')$ is projectively convex. The sequence $(a_1', \ldots, a_{i - 1}')$ is a convex shedding sequence for $G_{i - 1}'$ by $\cP(i - 1, 3)$, hence $(a_1', \ldots, a_i')$ is a convex shedding sequence for $G_i'$. Thus $\cP(i, 3)$ holds. We have now established $\cP(i)$ in the case that $d_i(a_i) > 2$. **Verification of $\cP(i)$ in the case $d_i(a_i) = 2$.** First note that by $\cP(i - 1, 1)$, we have $$x(v_1v_2) = x(w_1'w_2') \geq x(Z(w_1'w_2')) = x(b_1b_2).$$ This implies that $x(w_1'\overline{v_3}) = x(v_1v_3) \geq x(b_1z_{\rho(i)})$, because $\Delta'$ is a scaled, translated copy of $\Delta$. Since $x(a_i') = \lfloor x(\overline{v_3}) \rfloor$, and $x(b_1z_{\rho(i)})$ and $x(w_1')$ are integers, we also have $$x(w_1'a_i') \geq x(b_1z_{\rho(i)}) = x(Z(w_1'a_i')).$$ Similarly, we obtain $x(a_i'w_2') \geq x(z_{\rho(i)}b_2) = x(Z(a_i'w_2'))$. Thus $\cP(i, 1)$ holds. We now consider two relevant slopes in the construction of $G_i'$. Let $r$ denote the slope of the edge $w_1'w_2'$ of $G_{i - 1}'$, and let $Z(r)$ denote the slope of the corresponding edge $Z(w_1'w_2') = b_1b_2$ of $Z_{h(i - 1)}$. Since the triangle $\Delta'$ is a scaled, translated copy of $\Delta$, we see that $Z(r)$ is also the slope of the edge $v_1v_2$ of $\Delta'$. Let $\varepsilon = r - Z(r)$, and note that $$\varepsilon = \frac{y(w_2') - y(w_1')}{x(w_2') - x(w_1')} - \frac{y(v_2) - y(v_1)}{x(v_2) - x(v_1)} = \frac{y(w_2') - y(w_1')}{x(v_2) - x(v_1)} - \frac{y(w_2') - y(v_1)}{x(v_2) - x(v_1)} = \frac{\eta}{x(v_2) - x(v_1)}.$$ We consider another important pair of slopes arising in the construction of $G_i'$, together with the corresponding pair of slopes of $Z_{\rho(i)}$. Specifically, let $q_1$ and $q_2$ denote the slopes of the line segments $v_1v_3$ and $v_3v_2$, respectively. Since $\Delta'$ is a scaled, translated copy of $\Delta$, these slopes $q_1$ and $q_2$ are also the slopes of the boundary edges $b_1z_{\rho(i)}$ and $z_{\rho(i)}b_2$ of $Z_{\rho(i)}$, respectively. Let $\overline{q_1}$ and $\overline{q_2}$ denote the slopes of the line segments $\overline{v_3}w_1'$ and $\overline{v_3}w_2'$, respectively. We may think of $\overline{q_1}$ and $\overline{q_2}$ as *modifications* of the slopes $q_1$ and $q_2$, which arise from replacing the vertices $v_1$ and $v_3$ of $\Delta'$ with the vertices $w_1'$ and $\overline{v_3}$, respectively. A consequence of our definitions is that $\overline{q_1} - q_1 = \overline{q_2} - q_2 = \varepsilon$. Indeed, $$\begin{aligned} & \overline{q_1} - q_1 = \frac{y(\overline{v_3}) - y(w_1')}{x(\overline{v_3}) - x(w_1')} - \frac{y(v_3) - y(v_1)}{x(v_3) - x(v_1)} = \frac{y(\overline{v_3}) - y(w_1')}{x(v_3) - x(v_1)} - \frac{y(v_3) - y(v_1)}{x(v_3) - x(v_1)} \\ &= \frac{(y(v_1) - y(w_1')) + (y(\overline{v_3}) - y(v_3))}{x(v_3) - x(v_1)} = \frac{\eta - \kappa \eta}{x(v_3) - x(v_1)} = (1 - \kappa)\frac{\eta}{x(v_3) - x(v_1)} \\ &= \frac{x(z_{\rho(i)}) - x(b_1)}{x(b_2) - x(b_1)} \cdot \frac{\eta}{x(v_3) - x(v_1)} = \frac{x(v_3) - x(v_1)}{x(v_2) - x(v_1)} \cdot \frac{\eta}{x(v_3) - x(v_1)} \\ &= \frac{\eta}{x(v_2) - x(v_1)} = \varepsilon. \end{aligned}$$ In the third line, we have used the fact that $\Delta'$ is a scaled, translated copy of $\Delta$. An analogous calculation shows that $\overline{q_2} - q_2 = \varepsilon$. The result is that if $\varepsilon$ is the difference between a current boundary slope $r$ of $G_{i - 1}'$ and the corresponding boundary slope $Z(r)$ of $Z_{h(i- 1)}$, then this difference is propagated, but not increased, by the addition of $a_i'$. That is, the slopes of the boundary edges of $G_i'$ adjacent to $a_i'$ will differ by $\varepsilon$ from the corresponding boundary slopes of $Z_{\rho(i)}$. We now investigate how the slopes $\overline{q_1}$ and $\overline{q_2}$ change when we move $\overline{v_3}$ to the integer point $v_3' = a_i'$. We may assume without loss of generality that $x(z_{\rho(i)}) < 0$, and hence that $a_i' = (\lfloor x(v_3) \rfloor, \lceil y(v_3) \rceil)$, as the other case is treated identically. We will let $q_1'$ and $q_2'$ denote the slopes that result from replacing $\overline{v_3}$ with $v_3' = a_i'$. That is, let $q_1'$ be the slope of the line passing through $a_i'$ and $w_1'$, and let $q_2'$ be the slope of the line passing through $a_i'$ and $w_2'$. Since $z_{\rho(i)}$ lies to the left of the apex of $Z_{\rho(i)}$, the vertex $a_i'$ lies below and to the left of the apex of $G_i'$. Therefore we clearly have $q_1' - \overline{q_1} > 0$ and $\overline{q_2} - q_2' > 0$. By $\cP(i - 1, 2)$, we have $|\varepsilon| < i - 1$. Therefore we obtain $$\begin{aligned} & q_1' - \overline{q_1} = \frac{\lceil y(\overline{v_3}) \rceil - y(w_1')}{\lfloor x(\overline{v_3}) \rfloor - x(w_1')} - \overline{q_1} < \frac{y(\overline{v_3}) - y(w_1') + 1}{x(\overline{v_3}) - x(w_1') - 1} - \overline{q_1} \\ & = \frac{y(\overline{v_3}) - y(w_1') + 1 - (x(\overline{v_3}) - x(w_1'))\overline{q_1} + \overline{q_1}}{x(\overline{v_3}) - x(w_1') - 1} = \frac{1 + \overline{q_1}}{x(\overline{v_3}) - x(w_1') - 1} = \frac{1 + \overline{q_1}}{x(v_3) - x(v_1) - 1} \\ & \leq \frac{1 + \overline{q_1}}{x(z_{\rho(i)}) - x(b_1) - 1} \leq \frac{1 + \overline{q_1}}{\alpha - 1} = \frac{1 + q_1 + \varepsilon}{\alpha - 1} \leq \frac{1 + M + \varepsilon}{\alpha - 1} \leq \frac{1 + M + (i - 1)}{\alpha - 1} \\ & \leq \frac{2n^2 + n}{\alpha - 1} = 1.\end{aligned}$$ In the third line we have used the fact that $x(v_3) - x(v_1) \geq x(z_{\rho(i)}) - x(b_1)$, which we demonstrated above in order to establish $\cP(i, 1)$. An analogous calculation shows that $\overline{q_2} - q_2' < 1$. We may now compute $$|q_1' - q_1| \leq |q_1' - \overline{q_1}| + |\overline{q_1} - q_1| = |q_1' - \overline{q_1}| + \varepsilon < 1 + \varepsilon \leq 1 + (i - 1) = i.$$ An identical calculation shows that $|q_2' - q_2| \leq i$. Note that $q_1'$ is the slope of the boundary edge $w_1'a_i'$ of $G_i'$ and $q_1$ is the slope of the edge $b_1z_{\rho(i)} = Z(w_1'a_i')$, and similarly for $q_2'$ and $q_2$. This establishes $\cP(i, 2)$. From the construction of $a_i'$ it is clear that the line segments $w_1'a_i'$ and $a_i'w_2'$ intersect $G_{i - 1}'$ only in the vertices $w_1'$ and $w_2'$. Thus $G_i'$ is a plane triangulation, and $G_i' \sim G_i$. To show that $\F(G_i')$ is projectively convex, we carry out a calculation similar to that of the $d_i(a_i) > 2$ case. Let $\hat{q_1}$ denote the slope of the boundary edge of $G_i'$ adjacent and to the left of $w_1'$, if such an edge exists, and let $\hat{q_2}$ denote the slope of the boundary edge of $G_i'$ adjacent and to the right of $w_2'$, if such an edge exists. Let $Z(\hat{q_1})$ and $Z(\hat{q_2})$ denote the boundary slopes of $Z_{h(i - 1)}$ corresponding to $\hat{q_1}$ and $\hat{q_2}$, respectively. By $\cP(i - 1, 2)$, we have $\overline{q_1} - q_1 = \epsilon \leq i - 1$ and $Z(\hat{q_1}) - \hat{q_1} \leq i - 1$. Thus $$\begin{aligned} &\hat{q_1} - \overline{q_1} = (\hat{q_1} - q_1) - (\overline{q_1} - q_1) \geq (\hat{q_1} - q_1) - (i - 1) \\ &= (Z(\hat{q_1}) - q_1) - (Z(\hat{q_1}) - \hat{q_1}) - (i - 1) \geq (Z(\hat{q_1}) - q_1) - 2(i - 1) \\ &\geq 2n - 2i + 2 \geq 2. \end{aligned}$$ We conclude that $$\hat{q_1} - q_1' = (\hat{q_1} - \overline{q_1}) - (q_1' - \overline{q_1}) \geq (\hat{q_1} - \overline{q_1}) - 1 \geq 2 - 1 = 1 > 0.$$ An analogous calculation shows that $q_2' - \hat{q_2} > 0$. Thus $w_1'$ and $w_2'$ are convex vertices of $G_i'$. Because the region $\F(G_{i - 1}')$ is projectively convex by $\cP(i - 1, 3)$, we conclude that $\F(G_i')$ is projectively convex. By $\cP(i - 1, 3)$, the sequence $(a_1', \ldots, a_{i - 1}')$ is a convex shedding sequence for $G_{i - 1}'$, hence $(a_1', \ldots, a_i')$ is a convex shedding sequence for $G_i'$. Thus $\cP(i, 3)$ holds. We have now established $\cP(i)$ in the case that $d_i(a_i) = 2$. This completes the induction, and we conclude that $\cP(i)$ holds for all $3 \leq i \leq n$. Thus the triangulation $G' = G_n'$ is a sequentially convex embedding of $G$, with convex shedding sequence $\ba' = (a_1', \ldots, a_n')$. We have immediately that the $x$ dimension of $G'$ is $$\alpha2(n - 2) = (2n^2 + n + 1)(2n - 4) = 4 n^3 - 6 n^2 - 2n - 4 \leq 4n^3.$$ Since $\cP(n, 2)$ holds, we conclude that the largest absolute value of a boundary slope of $G'$ is at most $M + n
{'source': 'arXiv_out/1311'}