Internally-Convex Drawings of
Outerplanar Graphs in Small Area

Our main result is an algorithm that constructs an internally-convex grid drawing with $O(n^{1.5})$ area for $n$-vertex outerplanar graphs (Section 3). We employ some ideas and tools from a recent paper [6]. The main geometric component of our algorithm consists of constructing a “leveled” drawing, where consecutive levels are drawn on consecutive horizontal grid lines, up to a level where there are sufficiently few vertices so that the drawing can “make a turn” and extend horizontally rather than vertically. We remark that ours is the first algorithm that constructs outerplanar straight-line grid drawings in sub-quadratic area by drawing directly the outerplanar graph, without passing through a star-shaped drawing of its weak dual tree. This aspect might be of independent interest.

For internally-strictly-convex grid drawings, the same arguments as in the strictly-convex setting prove that $\mathrm{\Theta }(n^3)$ is a tight bound for the area requirements. However, the natural question to consider here is how the area relates not only to the number $n$ of vertices but also to the maximum size $k$ of an internal face. We show that there exist outerplanar graphs requiring $\mathrm{\Omega }(n{k}^2)$ area in any internally-strictly-convex grid drawing and that the lower bound can be matched by a corresponding upper bound for outerpaths, that is, biconnected outerplanar graphs whose weak dual is a path (Section 4).

We conclude in Section 5 with several open problems. Full proofs of statements marked with a ($\star$) can be found in the extended version of the paper [3].

Let $G$ be the $n$-vertex biconnected outerplanar graph obtained from a cycle $𝒞$ with $n/2$ vertices by attaching a degree-$2$ vertex incident to the end-vertices of each edge of $𝒞$. First, every convex drawing of $G$ respects the unique outerplanar embedding of $G$, as moving a degree-$2$ vertex inside $𝒞$ would create an angle larger than ${180}^{\circ }$ in an internal face at that vertex. Second, in every outerplanar convex drawing of $G$, the drawing of $𝒞$ is strictly-convex, as the angle at each vertex $v$ of $𝒞$ in the interior of the cycle delimiting the outer face of $G$ is at most ${180}^{\circ }$ and part of this angle is used by the two triangular faces incident to $v$. Since every strictly-convex drawing of a cycle requires cubic area [1], the lower bound follows. $◀$

Let $G$ be a biconnected outerplane graph with $n\ge 3$ vertices; refer to Fig.˜1. Note that $G$ has at least one internal face. The weak dual of $G$, denoted by $T^{\ast }$, is the tree having a vertex for each internal face of $G$ and an edge between any two vertices corresponding to internal faces sharing an edge. For simplicity, we use the same label to denote a vertex of $T^{\ast }$ and the corresponding face of $G$. If $T^{\ast }$ is a path, then $G$ is an outerpath. Let $(u,v)$ be an external edge of $G$ such that $v$ immediately precedes $u$ in counter-clockwise order along the outer face of $G$. The outerplane graph $G$ with the designated edge $(u,v)$, denoted by $G[u,v]$, is said to be rooted at $(u,v)$. Let $(x,y)$ be an internal edge of $G[u,v]$ such that $u,x,y,v$ appear in this counter-clockwise order along the outer face of $G$ (possibly $u=x$ or $y=v$ may hold). Consider the outerplane subgraph $G^{\prime }$ of $G$ induced by the vertices $x$, $y$, and the vertices that are encountered when traversing the outer face of $G$ in counter-clockwise direction from $x$ to $y$. Observe that the edge $(x,y)$ is an external edge of $G^{\prime }$ such that $y$ immediately precedes $x$ in counter-clockwise order along the outer face of $G^{\prime }$. Then we denote by $G[x,y]$ the outerplanar graph $G^{\prime }$ rooted at the edge $(x,y)$.

Let $G$ be rooted at $(u,v)$ and let $f_1$ be the internal face of $G$ incident to $(u,v)$. The extended weak dual tree $T$ of $G[u,v]$ is the tree with root $f_1$ obtained from the weak-dual tree $T^{\ast }$ of $G$ by inserting a new leaf ${\mathrm{\ell }}_e$ for each external edge $e$ of $G$ different from $(u,v)$ and an edge $(f,{\mathrm{\ell }}_e)$ if $f$ is the internal face of $G$ incident to $e$. Let $d$ be the number of vertices of $T$. Note that $d\ge n$, as $T$ contains the root $f_1$ plus one leaf for each of the $n-1$ external edges of $G$ different from $(u,v)$. Also, $d\le 2n-3$, since $G$ has $n-1$ external edges different from $(u,v)$ and at most $n-2$ internal faces. Let $\pi =(f_1,f_2,\mathrm{\dots },f_p)$ be a root-to-leaf path in $T$. We denote by $G[\pi ]$ the outerpath induced by the vertices incident to the faces $f_1,f_2,\mathrm{\dots },f_{p-1}$. We call $G[\pi ]$ the outerpath dual to $\pi$. Denote by $e_p$ the edge of $G$ dual to $(f_{p-1},f_p)$. Let $u=z_1,z_2,\mathrm{\dots },z_a,z_{a+1},\mathrm{\dots },z_m=v$ be the counter-clockwise order of the vertices along the outer face of $G[\pi ]$, where $e_p=(z_a,z_{a+1})$. We call the rooted outerplanar graphs $G[z_1,z_2],\mathrm{\dots },G[z_{a-1},z_a]$ left subgraphs of $G$ at $\pi$ and the rooted outerplanar graphs $G[z_{a+1},z_{a+2}],\mathrm{\dots },G[z_{m-1},z_m]$ right subgraphs of $G$ at $\pi$.

Since the sets $V_2,V_3,\mathrm{\dots },V_{1+\sqrt{n}}$ are disjoint and since there are $\sqrt{n}$ of them, the smallest among them contains at most $\sqrt{n}$ vertices. $◀$

The construction for Case 2 proceeds in three steps. In Step 1, we construct a drawing ${\mathrm{\Gamma }}_t^{\ast }$ of $G_t^{\ast }$; in Step 2, we augment ${\mathrm{\Gamma }}_t^{\ast }$ to a drawing ${\mathrm{\Gamma }}_{t-1}^{\ast }$ of $G_{t-1}^{\ast }$; finally, in Step 3, we augment ${\mathrm{\Gamma }}_{t-1}^{\ast }$ to the desired drawing $\mathrm{\Gamma }$ of $G$.

We construct a drawing ${\mathrm{\Gamma }}_t^{\ast }$ of $G_t^{\ast }$; refer to Fig.˜4. Recall that the transition edge $e_t^{\ast }$ has end-vertices $v_{s_t}^t$ and $v_{s_t+1}^t$ and that $G_t^{\ast }$ is the graph $G[v_{s_t}^t,v_{s_t+1}^t]$. Let $(f_j,f_{j+1})$ be the edge of $\pi$ dual to $e_t^{\ast }$, let ${\pi }^{\prime }$ be the subpath $(f_{j+1},f_{j+2},\mathrm{\dots },f_p)$ of $\pi$, and let $(u_0=v_{s_t}^t,u_1,\mathrm{\dots },u_x,w_y,w_{y-1},\mathrm{\dots },w_1,w_0=v_{s_t+1}^t)$ be the counter-clockwise order of the vertices along the outer face of $G[{\pi }^{\prime }]$, where $(u_x,w_y)$ is the edge $e_p$. We initialize ${\mathrm{\Gamma }}_t^{\ast }$ by drawing $e_t^{\ast }$ as a vertical segment of height $1$. For $j=1,\mathrm{\dots },x$, we recursively construct a drawing ${\mathrm{\Lambda }}_j^u$ of $G[u_{j-1},u_j]$. We place the drawings ${\mathrm{\Lambda }}_1^u,\mathrm{\dots },{\mathrm{\Lambda }}_x^u$ side by side, so that the placement of a vertex $u_j$ coincides in the drawings ${\mathrm{\Lambda }}_j^u$ and ${\mathrm{\Lambda }}_{j+1}^u$ where it appears, for $j=1,\mathrm{\dots },x-1$, and so that the placement of $u_0$ coincides in ${\mathrm{\Lambda }}_1^u$ and in the drawing of $e_t^{\ast }$. Analogously, for $j=1,\mathrm{\dots },y$, we recursively construct a drawing ${\mathrm{\Lambda }}_j^w$ of $G[w_j,w_{j-1}]$. Unlike for ${\mathrm{\Lambda }}_1^u,\mathrm{\dots },{\mathrm{\Lambda }}_x^u$, we rotate the drawings ${\mathrm{\Lambda }}_1^w,\mathrm{\dots },{\mathrm{\Lambda }}_y^w$ by ${180}^{\circ }$, and place them side by side, so that the placement of a vertex $w_j$ coincides in ${\mathrm{\Lambda }}_j^w$ and ${\mathrm{\Lambda }}_{j+1}^w$, for $j=1,\mathrm{\dots },y-1$, and so that the placement of $w_0$ coincides in ${\mathrm{\Lambda }}_1^w$ and in the drawing of $e_t^{\ast }$. This completes the construction of ${\mathrm{\Gamma }}_t^{\ast }$.

We now augment ${\mathrm{\Gamma }}_t^{\ast }$ to a drawing ${\mathrm{\Gamma }}_{t-1}^{\ast }$ of $G_{t-1}^{\ast }$; refer to Fig.˜5. Recall that the path $P_t$ has vertices $(v_1^t,v_2^t,\mathrm{\dots },v_{s_t}^t,v_{s_t+1}^t,\mathrm{\dots },v_{{\mathrm{\ell }}_t}^t)$. For $j=1,\mathrm{\dots },{\mathrm{\ell }}_t-1$ with $j\ne s_t$, we recursively construct a $v_j^t{v}_{j+1}^t$-separated drawing ${\mathrm{\Gamma }}_j^t$ of $G[v_j^t,v_{j+1}^t]$. We place the recursively constructed drawings ${\mathrm{\Gamma }}_1^t,\mathrm{\dots },{\mathrm{\Gamma }}_{s_t-1}^t$ side by side, so that the placement of a vertex $v_j^t$ coincides in ${\mathrm{\Gamma }}_{j-1}^t$ and ${\mathrm{\Gamma }}_j^t$, for $j=2,\mathrm{\dots },s_t-1$, and so that the placement of $v_{s_t}^t$ coincides in ${\mathrm{\Gamma }}_{s_t-1}^t$ and in ${\mathrm{\Gamma }}_t^{\ast }$. Next, we rotate the drawings ${\mathrm{\Gamma }}_{s_t+1}^t,\mathrm{\dots },{\mathrm{\Gamma }}_{{\mathrm{\ell }}_t-1}^t$ in counter-clockwise direction by ${90}^{\circ }$, and we stack them one on top of the other, so that the placement of a vertex $v_j^t$ coincides in ${\mathrm{\Gamma }}_{j-1}^t$ and ${\mathrm{\Gamma }}_j^t$, for $j=s_t+2,\mathrm{\dots },{\mathrm{\ell }}_t-1$, and so that the placement of $v_{s_t+1}^t$ in ${\mathrm{\Gamma }}_{s_t+1}^t$ is on the same vertical line as in ${\mathrm{\Gamma }}_t^{\ast }$ and on the same horizontal line as the highest vertex in ${\mathrm{\Gamma }}_t^{\ast }$ (refer to the left side of Fig.˜6).

This might provide a double placement for $v_{s_t+1}^t$ (unless $v_{s_t+1}^t$ is the highest vertex in ${\mathrm{\Gamma }}_t^{\ast }$). The issue is resolved by keeping for $v_{s_t+1}^t$ the position it has in ${\mathrm{\Gamma }}_t^{\ast }$; note that, in ${\mathrm{\Gamma }}_{s_t+1}^t$, this amounts to shifting $v_{s_t+1}^t$ downwards (refer to the right side of Fig.˜6). The drawing of ${\mathrm{\Gamma }}_{t-1}^{\ast }$ is completed by placing $v_{s_{t-1}}^{t-1}$ and $v_{s_{t-1}+1}^{t-1}$ on the same horizontal line, one unit higher than the highest vertex in ${\mathrm{\Gamma }}_{t-1}^{\ast }$ so far (this is either $v_{{\mathrm{\ell }}_t}^t$ if $s_t\le {\mathrm{\ell }}_t-2$ or the highest vertex in ${\mathrm{\Gamma }}_t^{\ast }$ otherwise), so that $v_{s_{t-1}+1}^{t-1}$ is one unit to the left of the vertical line through $e_t^{\ast }$ and $v_{s_{t-1}}^{t-1}$ is one unit to the left of the leftmost vertex in ${\mathrm{\Gamma }}_{t-1}^{\ast }$ so far (this is either $v_1^t$ if $s_t\ge 2$ or $v_{s_{t-1}+1}^{t-1}$ otherwise).

Finally, we show how to augment ${\mathrm{\Gamma }}_{t-1}^{\ast }$ to a $uv$-separated drawing of $G[u,v]$. This is done similarly to Case 1. Namely, we construct, for $i=t-2,t-3,\mathrm{\dots },0$, a $v_{s_i}^i{v}_{s_i+1}^i$-separated drawing ${\mathrm{\Gamma }}_i^{\ast }$ of $G[v_{s_i}^i,v_{s_i+1}^i]$ from an already constructed $v_{s_{i+1}}^{i+1}{v}_{s_{i+1}+1}^{i+1}$-separated drawing ${\mathrm{\Gamma }}_{i+1}^{\ast }$ of $G[v_{s_{i+1}}^{i+1},v_{s_{i+1}+1}^{i+1}]$. Recall that, in Step 2, we constructed ${\mathrm{\Gamma }}_{t-1}^{\ast }$. As in Case 1, we place the recursively constructed drawings ${\mathrm{\Gamma }}_j^{i+1}$ with $j=1,\mathrm{\dots },{\mathrm{\ell }}_{i+1}-1$ with $j\ne s_{i+1}$, as well as the drawing ${\mathrm{\Gamma }}_{i+1}^{\ast }$, side by side, so that the placement of a vertex $v_j^{i+1}$ coincides in two drawings it belongs to, with one exception in the case $i=t-2$; refer to Fig.˜7. Namely, the drawing ${\mathrm{\Gamma }}_{s_{t-1}+1}^{t-1}$ of $G_{s_{t-1}+1}^{t-1}$ is embedded so that $v_{s_{t-1}+1}^{t-1}$ is on the same horizontal line as in ${\mathrm{\Gamma }}_{t-1}^{\ast }$ and on the same vertical line as the rightmost vertex in ${\mathrm{\Gamma }}_{t-1}^{\ast }$. This provides a double placement for $v_{s_{t-1}+1}^{t-1}$. The issue is resolved by keeping for $v_{s_{t-1}+1}^{t-1}$ the position it has in ${\mathrm{\Gamma }}_{t-1}^{\ast }$; note that, in ${\mathrm{\Gamma }}_{s_{t-1}+1}^{t-1}$, this amounts to shifting $v_{s_{t-1}+1}^{t-1}$ leftwards. The desired $v_{s_i}^i{v}_{s_i+1}^i$-separated drawing ${\mathrm{\Gamma }}_i^{\ast }$ of $G[v_{s_i}^i,v_{s_i+1}^i]$ is completed by placing $v_{s_i}^i$ one unit above and one unit to the left of the leftmost vertex of $P_{i+1}$, and $v_{s_i+1}^i$ one unit above and one unit to the right of the rightmost vertex of $P_{i+1}$. When $i=0$, the obtained drawing $\mathrm{\Gamma }:={\mathrm{\Gamma }}_0^{\ast }$ is a $uv$-separated drawing of $G[u,v]$, as proved in the following.

First, it trivially comes from the construction that $\mathrm{\Gamma }$ is a straight-line grid drawing.

Most of the arguments used to prove that $\mathrm{\Gamma }$ is planar and satisfies Properties P.1, P.2, P.3, and P.4 of a $uv$-separated drawing are easy geometric considerations. For example, each graph $G[u_i,u_{i+1}]$ does not cross any graph $G[u_j,u_{j+1}]$, as it is horizontally disjoint from it, does not cross any subgraph $G[w_j,w_{j+1}]$ as it is vertically disjoint from it, and does not cross $G[{\pi }^{\prime }]$ as it is vertically disjoint from it, except for the edge $(u_i,u_{i+1})$ which is shared by the two graphs. The most interesting part in the proof of the planarity of $\mathrm{\Gamma }$ consists of showing that the drawings ${\mathrm{\Gamma }}_{s_t+1}^t$ and ${\mathrm{\Gamma }}_t^{\ast }$ do not cross each other. This proof uses the fact that ${\mathrm{\Gamma }}_{s_t+1}^t$ satisfies the properties of a $v_{s_t+1}^t{v}_{s_t+2}^t$-separated drawing. In fact, the avoidance of crossings between ${\mathrm{\Gamma }}_{s_t+1}^t$ and ${\mathrm{\Gamma }}_t^{\ast }$ is the driving force behind the definition of our drawing invariant. Namely, by Property P.4 and by the ${90}^{\circ }$ counter-clockwise rotation of ${\mathrm{\Gamma }}_{s_t+1}^t$, we have that $v_{s_t+1}^t$ is the lowest vertex in ${\mathrm{\Gamma }}_{s_t+1}^t$. Since $v_{s_t+1}^t$ is on the same horizontal line as the highest vertex in ${\mathrm{\Gamma }}_t^{\ast }$, the only edges of $G_{s_t+1}^t$ that might cross $G_t^{\ast }$ in $\mathrm{\Gamma }$ are those incident to $v_{s_t+1}^t$. However, since all the vertices of $G_{s_t+1}^t$ different from $v_{s_t+1}^t$ lie above ${\mathrm{\Gamma }}_t^{\ast }$ and all the neighbors of $v_{s_t+1}^t$ in $G_{s_t+1}^t$ lie on the vertical line one unit to the right of $v_{s_t+1}^t$, by Property P.2 and by the rotation of ${\mathrm{\Gamma }}_{s_t+1}^t$, it follows that the edges of $G_{s_t+1}^t$ incident to $v_{s_t+1}^t$ lie above every edge of $G_t^{\ast }$ with which they have a horizontal overlap. Note that, by Property 1, placing $v_{s_t+1}^t$ at the point where it is placed in ${\mathrm{\Gamma }}_t^{\ast }$ maintains the planarity of ${\mathrm{\Gamma }}_{s_t+1}^t$.

The convexity of each internal face $f$ of $G$ in $\mathrm{\Gamma }$ follows by induction if $f$ is internal to some recursively drawn subgraph $G_j^i$ of $G$. If $f$ is an internal face of $G[{\pi }^{\prime }]$ or has vertices on two distinct paths among $P_0,P_1,\mathrm{\dots },P_{t-1}$, then $f$ is drawn as a triangle or a trapezoid in $\mathrm{\Gamma }$, hence it is convex. The only faces that do not fit in any of these two categories are those incident to $v_{s_{t-1}}^{t-1}$ and/or $v_{s_{t-1}+1}^{t-1}$ and incident to at least one vertex in $P_t$. The convexity of these faces follows from two facts. First, the polygon $Q$ delimited by the edge $(v_{s_{t-1}}^{t-1},v_{s_{t-1}+1}^{t-1})$ and by the path $P_t$ is a convex pentagon $(v_{s_{t-1}}^{t-1},v_{s_{t-1}+1}^{t-1},v_{{\mathrm{\ell }}_t}^t,v_{s_t}^t,v_1^t)$ (if $s_t>1$) or a convex quadrilateral $(v_{s_{t-1}}^{t-1},v_{s_{t-1}+1}^{t-1},v_{{\mathrm{\ell }}_t}^t,v_1^t)$ (if $s_t=1$). Second, the faces incident to $v_{s_{t-1}}^{t-1}$ and/or $v_{s_{t-1}+1}^{t-1}$ and incident to at least one vertex in $P_t$ form a convex subdivision of $Q$.

Property W follows by induction and since every vertical grid line intersecting $\mathrm{\Gamma }$ intersects a recursively constructed drawing or a vertex directly placed by the algorithm.

Concerning Property H, we prove that $h(\mathrm{\Gamma })$ is at most $t$, plus $\sqrt{n}$, plus the maximum height of a recursively constructed drawing of a subgraph of a left subgraph of $G$ at $\pi$, plus the maximum height of a recursively constructed drawing of a subgraph of a right subgraph of $G$ at $\pi$. The first term accounts for the horizontal grid lines $h_0,h_1,\mathrm{\dots },h_{t-1}$ on which $P_0,P_1,\mathrm{\dots },P_{t-1}$ are placed. The $\sqrt{n}$ term accounts for the horizontal grid lines between the highest line intersecting ${\mathrm{\Gamma }}_{{\mathrm{\ell }}_t-1}^t$ (which is one unit below $h_{t-1}$) and the lowest line intersecting ${\mathrm{\Gamma }}_{s_t+1}^t$ before $v_{s_t+1}^t$ is moved to the position it has in ${\mathrm{\Gamma }}_t^{\ast }$. Indeed, since the drawings ${\mathrm{\Gamma }}_{s_t+1}^t,{\mathrm{\Gamma }}_{s_t+2}^t,\mathrm{\dots },{\mathrm{\Gamma }}_{{\mathrm{\ell }}_t-1}^t$ are constructed recursively, and hence satisfy Property W, and are rotated by ${90}^{\circ }$, and since the graphs $G_{s_t+1}^t,G_{s_t+2}^t,\mathrm{\dots },G_{{\mathrm{\ell }}_t-1}^t$ have a total of at most $\sqrt{n}$ vertices, by Lemma 6, it follows that the drawings ${\mathrm{\Gamma }}_{s_t+1}^t,{\mathrm{\Gamma }}_{s_t+2}^t,\mathrm{\dots },{\mathrm{\Gamma }}_{{\mathrm{\ell }}_t-1}^t$ intersect, before moving $v_{s_t+1}^t$, at most $\sqrt{n}$ grid lines. The third and fourth terms in the upper bound for $h(\mathrm{\Gamma })$ account for the total height of the recursively drawn subgraphs different from $G_{s_t+1}^t,G_{s_t+2}^t,\mathrm{\dots },G_{{\mathrm{\ell }}_t-1}^t$. The key observation here is that, apart for the drawings of ${\mathrm{\Gamma }}_{s_t+1}^t,{\mathrm{\Gamma }}_{s_t+2}^t,\mathrm{\dots },{\mathrm{\Gamma }}_{{\mathrm{\ell }}_t-1}^t$, which are already accounted for, any two recursively constructed drawings which are stacked one on top of the other are drawings of subgraphs of a left subgraph of $G$ at $\pi$ and of a right subgraph of $G$ at $\pi$ (and not of two left subgraphs or of two right subgraphs); in fact, only the right subgraphs $G[w_j,w_{j+1}]$ of $G$ at $\pi$ are forced to be stacked on top of the left subgraphs $G[u_j,u_{j+1}]$ of $G$ at $\pi$ (and on top of the graphs $G[v_j^t,v_{j+1}^t]$ with which are also subgraphs of left subgraphs of $G$ at $\pi$).

Note that $t\le \sqrt{n}$ by construction and hence $t\le \sqrt{d}$, given that $d\ge n$. Assume that $i$ and $j$ are indices such that $G_j^i$ is a recursively drawn subgraph of a left subgraph of $G$ at $\pi$ and $h({\mathrm{\Gamma }}_j^i)$ is maximum. Indices $i^{\prime }$ and $j^{\prime }$ are defined analogously for the right subgraphs of $G$ at $\pi$. Let $d_j^i$ and $d_{j^{\prime }}^{i^{\prime }}$ be the number of vertices in the extended weak dual trees of $G_j^i$ and $G_{j^{\prime }}^{i^{\prime }}$, respectively. By the upper bound proved above, we have $h(\mathrm{\Gamma })\le 2\sqrt{d}+h({\mathrm{\Gamma }}_j^i)+h({\mathrm{\Gamma }}_{j^{\prime }}^{i^{\prime }})$ and thus, by induction, $h(\mathrm{\Gamma })\le 2\sqrt{d}+f(d_j^i)+f(d_{j^{\prime }}^{i^{\prime }})$. By Theorem 3, it holds true that ${(d_j^i)}^p+{(d_{j^{\prime }}^{i^{\prime }})}^p\le (1-\delta )d^p$. By the definition of $f(d)$ in Lemma 4 (with $d_a=d_j^i$ and $d_b=d_{j^{\prime }}^{i^{\prime }}$), we have that $2\sqrt{d}+f(d_j^i)+f(d_{j^{\prime }}^{i^{\prime }})\le f(d)$, hence $h(\mathrm{\Gamma })\le f(d)$, which proves Property H. $◀$

Let $G$ be an $n$-vertex outerplane graph with $\mathrm{\Omega }(\frac{n}{k})$ internal faces of size $k$. First, note that any internally-strictly-convex grid drawing of $G$ must be outerplanar. Indeed, any embedding of an outerplanar graph which is not an outerplanar embedding contains a degree-$2$ vertex as an internal vertex. However, such a vertex would create an angle larger than or equal to ${180}^{\circ }$ in an internal face. The area lower bound is obtained by a simple packing argument. Since any internally-strictly-convex grid drawing of $G$ is outerplanar, it contains $\mathrm{\Omega }(\frac{n}{k})$ internal faces of size $k$. Each of these faces occupies $\mathrm{\Omega }(k^3)$ area [1], hence the total area of the drawing is $\mathrm{\Omega }(\frac{n}{k}\cdot k^3)$, which gives the bound claimed by the theorem. $◀$

In the rest of the section, we prove a matching upper bound for the case of outerpaths. Note that there exist $n$-vertex outerpaths with $\mathrm{\Omega }(\frac{n}{k})$ internal faces of size $k$, hence the lower bound of Theorem 8 applies to outerpaths as well. We introduce some notation and definitions. Let $G$ be an outerpath and let $\pi =(f_1,f_2,\mathrm{\dots },f_{p-1})$ be the weak-dual of $G$, which is a path; refer to Fig.˜8. Let $\widehat{e}$ be the edge of $G$ dual to the edge $(f_1,f_2)$ of $\pi$ and let $\tilde{e}$ be the edge of $G$ dual to the edge $(f_{p-2},f_{p-1})$ of $\pi$. Moreover, let $\widehat{g}=(u_0,v_0)$ be any of the two external edges incident to $\widehat{e}$ that belong to the face $f_1$ of $G$, where $u_0$ immediately follows $v_0$ when traversing the outer face of $G$ in counter-clockwise order. Also, let $\tilde{g}$ be any of the two external edges incident to $\tilde{e}$ that belong to the face $f_{p-1}$ of $G$. We augment $\pi$ with two new vertices $f_0$ and $f_p$, and edges $(f_0,f_1)$ and $(f_{p-1},f_p)$. We interpret $(f_0,f_1)$ and $(f_{p-1},f_p)$ as edges dual to $\widehat{g}$ and $\tilde{g}$, respectively.

We now describe a decomposition of $G$ into a sequence of smaller outerpaths such that any two consecutive outerpaths in the sequence share exactly one internal edge of $G$. We let $e_0^{\ast }$ be the edge $\widehat{g}$. Let $G_0$ be the plane graph induced by the vertices delimiting the internal faces of $G$ incident to the end-vertex common to $e_0^{\ast }$ and $\widehat{e}$ (see the vertex $u_0$ in Fig.˜8). Let $e_1^{\ast }$ be the external edge of $G_0$, other than $e_0^{\ast }$, dual to an edge of $\pi$. We call $G_0$ a fan graph with gate edges $e_0^{\ast }$ and $e_1^{\ast }$. Suppose that, for some $i\ge 1$, a fan graph $G_{i-1}$ with gate edges $e_{i-1}^{\ast }$ and $e_i^{\ast }$ has been defined. Let $u_i$ and $v_i$ be the end-vertices of $e_i^{\ast }$, where $u_i$ is encountered before $v_i$ when traversing the outer face of $G$ in counter-clockwise direction from $u_0$ to $v_0$. We define the fan graph $G_i$ as follows. Let $V_{i-1}$ be defined as ${\bigcup }_{j=0}^{i-1}V(G_j)\setminus \{u_i,v_i\}$. Then $G_i$ is the outerplane graph induced by the vertices that do not belong to $V_{i-1}$ and that are incident to faces that have $u_i$ or $v_i$ on their boundary. Let $e_{i+1}^{\ast }$ be the external edge of $G_i$, other than $e_i^{\ast }$, dual to an edge of $\pi$. The edges $e_i^{\ast }$ and $e_{i+1}^{\ast }$ are the gate edges of $G_i$. Eventually, the decomposition defines a fan graph $G_r$ with gate edges $e_r^{\ast }$ and $e_{r+1}^{\ast }$ such that $e_{r+1}^{\ast }=\tilde{g}$.

We will show that each fan graph $G_i$ with gate edges $e_i^{\ast }$ and $e_{i+1}^{\ast }$ admits a block-drawing. This is an outerplanar internally-strictly-convex grid drawing ${\mathrm{\Gamma }}_i$ of $G_i$ satisfying the following properties:

1. B.1

   The two gate edges $e_i^{\ast }$ and $e_{i+1}^{\ast }$ are drawn as vertical segments of unit length such that $y(u_i)=y(u_{i+1})=0$ and $y(v_i)=y(v_{i+1})=1$;

2. B.2

   the vertices $u_i$ and $v_i$ are the leftmost vertices of ${\mathrm{\Gamma }}_i$ and no other vertex of $G_i$ has the same $x$-coordinate as these vertices; and

3. B.3

   the vertices $u_{i+1}$ and $v_{i+1}$ are the rightmost vertices of ${\mathrm{\Gamma }}_i$ and no other vertex of $G_i$ has the same $x$-coordinate as these vertices.

We proceed as follows. Lemmas 9 and 10 are two technical lemmas that yield special internally-strictly-convex grid drawings of cycles. We use these two lemmas to compute a block-drawing ${\mathrm{\Gamma }}_i$ of each fan graph $G_i$ with appropriate area bounds. We do so by drawing each of its faces using either Lemma 9 or Lemma 10, and we appropriately “merge” them together (Lemma 11). The final drawing $\mathrm{\Gamma }$ of $G$ is obtained by “gluing” the block-drawings ${\mathrm{\Gamma }}_0,\mathrm{\dots },{\mathrm{\Gamma }}_r$ (Theorem 12) at their shared gate edges.

In the following, by half-plane of a line we mean an open half-plane bounded by the line.

The drawing ${\mathrm{\Gamma }}_C$ can be obtained as follows; see Fig.˜9. Vertices $v_1$ and $v_2$ are at $(0,0)$ and $(x(v_2),1)$ in ${\mathrm{\Gamma }}_C$. For $j=3,\mathrm{\dots },h-1$, we place $v_j$ at $(x(v_2)\cdot (j-1)+\frac{(j-2)(j-1)}{2},j-1)$. Finally, we place vertex $v_h$ at $(x(v_2)+h-2,1)$. This completes the construction of ${\mathrm{\Gamma }}_C$. We defer the proof that ${\mathrm{\Gamma }}_C$ satisfies Properties I.1, I.2, I.3, I.4, and I.5 to the full version [3]. $◀$

The following property is a consequence of the constraints of the drawings of Lemma 9.

We show how to construct the drawing ${\mathrm{\Gamma }}_C$; refer to Fig.˜10. First, we define two cycles $C_1=(v_1,v_2,\mathrm{\dots },v_i)$ and $C_2=(v_1,v_h,v_{h-1},\mathrm{\dots },v_{i+1})$. We apply Lemma 9 to obtain a drawing ${\mathrm{\Gamma }}_{C_1}$ of $C_1$ in which the edge $(v_1,v_2)$ is represented by $s_1$ and to obtain a drawing ${\mathrm{\Gamma }}_{C_2}$ of $C_2$ in which the edge $(v_1,v_h)$ is represented by the segment connecting points $(0,0)$ and $(1,1)$. Let $M$ be the maximum $x$-coordinate of a vertex in ${\mathrm{\Gamma }}_{C_1}$ and ${\mathrm{\Gamma }}_{C_2}$. We leverage Property 2 to obtain a drawing ${\mathrm{\Gamma }}_{C_1}^{\prime }$ of $C_1$ by shifting the vertex $v_i$ horizontally and rightward in ${\mathrm{\Gamma }}_{C_1}$ so that its $x$-coordinate is $1+M$. Analogously, we leverage Property 2 to obtain a drawing ${\mathrm{\Gamma }}_{C_2}^{\prime }$ of $C_2$ by shifting the vertex $v_{i+1}$ downward and rightward in ${\mathrm{\Gamma }}_{C_2}$ so that its $x$-coordinate is $1+M$ and its $y$-coordinate is $0$. To obtain the drawing ${\mathrm{\Gamma }}_C$ we then proceed as follows. We first initialize ${\mathrm{\Gamma }}_C$ to ${\mathrm{\Gamma }}_{C_1}^{\prime }$. Then we construct a vertically-mirrored copy ${\mathrm{\Gamma }}_{C_2}^{\prime \prime }$ of ${\mathrm{\Gamma }}_{C_2}^{\prime }$, that is, we flip the sign of the $y$-coordinate of each vertex, and we insert ${\mathrm{\Gamma }}_{C_2}^{\prime \prime }$ in ${\mathrm{\Gamma }}_C$ so that the placement of $v_1$ is the same in both drawings. Finally, we remove from ${\mathrm{\Gamma }}_C$ the drawing of the edges $(v_1,v_i)$ and $(v_1,v_{i+1})$ and draw the edge $(v_i,v_{i+1})$ as a vertical segment of unit length. This concludes the construction of ${\mathrm{\Gamma }}_C$. We defer the proof that ${\mathrm{\Gamma }}_C$ satisfies Properties J.1, J.2, J.3, and J.4 to the full version [3]. $◀$