How Many Slopes Does Polynomial Area Cost?

In this work, we identify and close a critical gap in the literature. While almost all aforementioned algorithms for planar graphs of small fixed degree produce drawings of polynomial area [3, 5, 17, 12, 40] (and are therefore practically applicable), the corresponding algorithms that have been proposed for planar graphs of higher maximum degree require super-polynomial area [1, 25, 32], which limits significantly their practical applicability. Thus, in this paper, we study for first time the interplay between the number of slopes, the number of bends per edge, and the corresponding area requirements; see Table 1. Our focus is on algorithms that produce planar drawings with few bends per edge on polynomial-size grids while only slightly increasing the number of slopes used. More precisely:

• $\mathrm{■}$

  In Section 3, we prove that every 3-connected $n$-vertex planar graph of maximum degree $\mathrm{\Delta }$ admits a planar grid drawing with at most one bend per edge, using at most $3\mathrm{\Delta }-8$ slopes on a $O(\mathrm{\Delta }{n}^2)\times O(\mathrm{\Delta }{n}^3)$ grid. Our approach builds upon the incremental construction by Angelini, Bekos, Liotta and Montecchiani [1], which produces such drawings on arbitrary sets of $\mathrm{\Delta }-1$ slopes. In contrast, we fix the slope set in advance and increase its size from $\mathrm{\Delta }-1$ to $3\mathrm{\Delta }-8$ in order to guarantee polynomial area. As a consequence, for general planar graphs (i.e., not necessarily $3$-connected) the number of slopes becomes $\lceil \frac{9}{2}\mathrm{\Delta }\rceil +1$.

• $\mathrm{■}$

  For the special case of planar graphs of maximum degree $5$, we decrease the number of required slopes from $3\mathrm{\Delta }-8=7$ to $5$ at the cost of increasing the drawing area by a factor of $O(n^2)$; see Theorem 3. Compared with the best-known algorithm in [3], our construction achieves polynomial-area while increasing the number of slopes by one.

• $\mathrm{■}$

  In Section 4, we prove that every planar graph $G$ of maximum degree $\mathrm{\Delta }\ge 3$ admits a 2-bend planar drawing on a $O(n)\times O(\mathrm{\Delta }{n}^2)$ grid using at most $\lceil \mathrm{\Delta }/2\rceil$ slopes if $G$ is biconnected, and at most $\lceil \mathrm{\Delta }/2\rceil +1$ slopes otherwise. In contrast to the algorithm by Keszegh, Pach, and Pálvölgyi [25], which uses equidistant slopes to support rotations and scalings of biconnected components around cut vertices, our algorithm uses a different slope set to guarantee polynomial-drawing area. However, it requires one additional slope for general (i.e., non-biconnected) planar graphs, as it can rely neither on rotations (because of the non-equidistant slopes) nor on scaling (because of the area requirement).

• $\mathrm{■}$

  In Section 5, we prove that, regardless of the maximum degree $\mathrm{\Delta }$ of the input planar graph, quadratic area in the number of vertices of the graph suffices to obtain a planar drawing with at most $\mathrm{\Delta }$ slopes, where each edge has at most four bends. If the graph is additionally subhamiltonian, then three bends suffice.

Note that a fundamental requirement of our grid drawings is that both vertices and edge bends lie on grid points. Furthermore, we stress that the algorithms that we present in this work can be implemented to run in time linear in the size of the input graphs.

The slope set $S$ used by our algorithm is defined with respect to a parameter $k>\mathrm{\Delta }{n}^2$ that we will specify later, and is the union of the following sets. $S_{\mathrm{v}}$ consists only of the vertical slope. $S_{\mathrm{h}}$ consists only of the horizontal slope. $S_{\mathrm{ls}}$ consists of $\mathrm{\Delta }-3$ left steep slopes $-\frac{k}{1},\mathrm{\dots },-\frac{k}{\mathrm{\Delta }-3}$ (green in Figure 2(a)). $S_{\mathrm{rs}}$ consists of $\mathrm{\Delta }-3$ right steep slopes $\frac{k}{1},\mathrm{\dots },\frac{k}{\mathrm{\Delta }-3}$ (blue in Figure 2(a)). Finally, $S_{\mathrm{f}}$ consists of $\mathrm{\Delta }-4$ flat slopes $\frac{1}{\mathrm{\Delta }-3},\mathrm{\dots },\frac{\mathrm{\Delta }-4}{\mathrm{\Delta }-3}$ (red in Figure 2(a)). Hence, the cardinality of $S$ is $3\mathrm{\Delta }-8$, as desired.

Let $\mathrm{\Pi }=(P_0,\mathrm{\dots },P_m)$ be a canonical order of $G$. For the drawing algorithm, we first remove the edge $(v_1,v_2)$ from the graph and color the edges incident to $v_1$ and $v_2$ in $G_1$ black. After the drawing algorithm is completed, we will insert the edge $(v_1,v_2)$ below the constructed drawing with a vertical segment incident to $v_1$ and a segment with slope $\frac{1}{\mathrm{\Delta }-3}\in$ $S_{\mathrm{f}}$ incident to $v_2$ (see Figure 2(b)). For now, we also assume that $v_n$ has degree strictly less than $\mathrm{\Delta }$ (note that if $\mathrm{\Delta }\ge 6$, then this assumption is w.l.o.g.  since we can choose $v_n$ such that its degree is at most $5$). We will describe how to handle the other case later.

Assume that for , we have already constructed a $1$-bend planar grid drawing ${\mathrm{\Gamma }}_{i-1}$ of $G_{i-1}$ on $S$ that satisfies the following invariants.

1. I.1

   The contour $C_{i-1}$ of ${\mathrm{\Gamma }}_{i-1}$ is drawn strictly $x$-monotone.

2. I.2

   There exists a cut at every edge belonging to the contour $C_{i-1}$ of ${\mathrm{\Gamma }}_{i-1}$.

3. I.3

   Every vertex of $C_{i-1}$ has at least as many unoccupied top ports in each of $S_{\mathrm{rs}}$ and $S_{\mathrm{ls}}$ incident to the outer face of ${\mathrm{\Gamma }}_{i-1}$ as it has neighbors in $G\setminus G_{i-1}$ minus one, and the port corresponding to $S_{\mathrm{v}}$ is unoccupied if the vertex has at least one neighbor in $G\setminus G_{i-1}$ or its degree is strictly less than $\mathrm{\Delta }$.

4. I.4

   All vertices of $G_{i-1}$ are at $y$-coordinates that are multiples of $k$ in ${\mathrm{\Gamma }}_{i-1}$.

5. I.5

   Based on their colors, the edges of $G_{i-1}$ have been drawn as follows in ${\mathrm{\Gamma }}_{i-1}$:

   1. a.

      Each black edge of $G_{i-1}$ consists of a single horizontal segment (i.e., its slope is in $S_{\mathrm{h}}$).

   2. b.

      Each blue edge of $G_{i-1}$ consists of two segments; the one incident to its source has a slope in $S_{\mathrm{v}}$$\cup$$S_{\mathrm{rs}}$, while the one incident to its target is in $S_{\mathrm{h}}$.

   3. c.

      Each red edge of $G_{i-1}$ consists of at most two segments; the one incident to its source is vertical (i.e., its slope is in $S_{\mathrm{v}}$), while the one incident to its target has a slope in $S_{\mathrm{f}}$$\cup$$S_{\mathrm{v}}$, i.e, if the slope of the second segment is in $S_{\mathrm{v}}$, then the edge consists of one segment.

   4. d.

      Each green edge of $G_{i-1}$ consists of two segments; the one incident to its source has a slope in $S_{\mathrm{v}}$$\cup$$S_{\mathrm{ls}}$, while the one incident to its target is in $S_{\mathrm{h}}$.

Note that Invariants I.1 and I.2 are inherited from [1]; Invariant I.3 is adapted to our setting, and Invariants I.4 and I.5 are specific to our construction. The base case of our recursive algorithm is the graph $G_1$, which consists of the vertices $v_1$, $v_2$, and all vertices in $P_1$. We place these vertices on a horizontal line: $v_1$ is positioned at $(0,0)$, $v_2$ at $(|P_1|+1,0)$, and the vertices of $P_1$ are placed between them at unit distance. All edges are then drawn as horizontal segments. This obviously satisfies the invariants. So, we may assume that $i>1$. To derive a drawing ${\mathrm{\Gamma }}_i$ of $G_i$ maintaining Invariants I.1–I.5, we introduce the vertices of path $P_i$ into the drawing ${\mathrm{\Gamma }}_{i-1}$ by distinguish two cases depending on whether $P_i$ is a chain or a singleton of degree 2 (Case 1) and a singleton of degree greater than 2 (Case 2). At a high level, Invariant I.4 will allow us to determine a grid point for each vertex of $P_i$ and for each bend of the blue and green edges incident to it, while Invariant I.2 will support stretching the drawing ${\mathrm{\Gamma }}_{i-1}$ to create additional space to accomplish this placement, if needed.

Suppose that $P_i=\{v_g,\mathrm{\dots },v_h\}$ is a chain or a singleton of degree $2$ in $G_i$. Note that in the latter case, $g=h$ holds. Let $v_{\mathrm{\ell }}$ and $v_r$ be the neighbors of $v_g$ and $v_h$ in $G_{i-1}$, respectively. Refer to Figure 3(a). W.l.o.g., we may assume that $v_{\mathrm{\ell }}$ appears before $v_r$ along the contour $C_{i-1}$ in a traversal of it from $v_1$ to $v_2$. Let also ${\rho }_{\mathrm{\ell }}$ (${\rho }_r$) be the first unoccupied port at $v_{\mathrm{\ell }}$ ($v_r$) encountered in a counter-clockwise (clockwise) traversal of its top ports in $S_{\mathrm{rs}}$ $\cup$ $S_{\mathrm{v}}$ ($S_{\mathrm{ls}}$ $\cup$ $S_{\mathrm{v}}$) starting from the rightward (leftward) horizontal port, which exist by Invariant I.3. To satisfy Invariant I.4, we set the $y$-coordinate of each of $v_g,\mathrm{\dots },v_h$ to $H({\mathrm{\Gamma }}_{i-1})+k$. The $x$-coordinates of $v_g,\mathrm{\dots },v_h$ will be determined by the constraints arising from the way that $(v_{\mathrm{\ell }},v_g),(v_g,v_{g+1}),\mathrm{\dots },(v_{h-1},v_h),(v_h,v_r)$ must be drawn. Since $(v_{\mathrm{\ell }},v_g)$ and $(v_r,v_h)$ are incoming edges to $v_g$ and $v_h$ in $G_i$, we satisfy Invariants I.5b. and I.5d. by drawing $(v_{\mathrm{\ell }},v_g)$ and $(v_r,v_h)$ with a horizontal segment incident to $v_g$ and $v_h$ and a second segment attached to ${\rho }_{\mathrm{\ell }}$ and ${\rho }_r$, respectively, which maintains Invariant I.3 for $v_{\mathrm{\ell }}$ and $v_r$. The remaining edges of $P_i$ (if any) will be drawn as unit-length horizontal segments satisfying Invariant I.5a.. Each of the vertices $v_g,\mathrm{\dots },v_h$ has at most $\mathrm{\Delta }-2$ neighbors in $G\setminus G_i$ and all $\mathrm{\Delta }-3$ ports unoccupied in each of $S_{\mathrm{rs}}$ and $S_{\mathrm{ls}}$ that are incident to the outer face of ${\mathrm{\Gamma }}_i$, which ensures Invariant I.3 for them.

Let $p_{\mathrm{\ell }}$ and $p_r$ be the points where the rays that correspond to ${\rho }_{\mathrm{\ell }}$ and ${\rho }_r$ intersect the horizontal line $L$ through $v_g$; see Figure 4. We have to ensure that $p_{\mathrm{\ell }}$ lies at least $h-g+2$ units to the left of $p_r$ such that $v_g,\mathrm{\dots },v_h$ can be placed between them in ${\mathrm{\Gamma }}_i$. Furthermore, the rays at ${\rho }_{\mathrm{\ell }}$ and ${\rho }_r$ are not allowed to cross any part of ${\mathrm{\Gamma }}_{i-1}$. To guarantee these conditions, we horizontally stretch ${\mathrm{\Gamma }}_{i-1}$ as follows. Let $(v_{\mathrm{\ell }},v_{{\mathrm{\ell }}^{\prime }})$ be the first edge of $C_{i-1}$ that is encountered when traversing $C_{i-1}$ from $v_{\mathrm{\ell }}$ to $v_2$. Analogously, $(v_r,v_{r^{\prime }})$ is the first edge of $C_{i-1}$ that is encountered when traversing $C_{i-1}$ from $v_r$ to $v_1$. (Note that $v_{{\mathrm{\ell }}^{\prime }}=v_r$ and $v_{r^{\prime }}=v_{\mathrm{\ell }}$ is possible.) Since both these edges lie on $C_{i-1}$, by Invariant I.2 there is a cut at each of them. This allows us to stretch $(v_{\mathrm{\ell }},v_{{\mathrm{\ell }}^{\prime }})$ until $p_{\mathrm{\ell }}$ lies to the left of $v_{{\mathrm{\ell }}^{\prime }}$, and symmetrically, stretch $(v_r,v_{r^{\prime }})$ until $p_r$ lies to the right of $v_{r^{\prime }}$. This further guarantees that the horizontal distance between $p_{\mathrm{\ell }}$ and $p_r$ is at least $2$. If needed, we further stretch one of the edges $(v_{\mathrm{\ell }},v_{{\mathrm{\ell }}^{\prime }})$ and $(v_{r^{\prime }},v_r)$, say w.l.o.g. the former, by up to $h-g$ additional units, so as to ensure that the horizontal distance between $p_{\mathrm{\ell }}$ and $p_r$ is at least $h-g+2$. Hence, it is possible to place each of $v_g,\mathrm{\dots },v_h$ at a grid point along $L$ that lies between $p_{\mathrm{\ell }}$ and $p_r$, and draw the edges $(v_{\mathrm{\ell }},v_g)$ and $(v_r,v_h)$ with one bend each at $p_{\mathrm{\ell }}$ and $p_r$, respectively. The remaining edges of $P_i$ are drawn as unit-length horizontal edge segments, as we initially sought; see Figure 3. This completes the drawing of ${\mathrm{\Gamma }}_i$.

It remains to show that ${\mathrm{\Gamma }}_i$ is planar and satisfies Invariant I.1. For the former, observe that the introduction of $v_g,\mathrm{\dots },v_h$ into ${\mathrm{\Gamma }}_{i-1}$ yields $h-g+4$ new edge segments in ${\mathrm{\Gamma }}_i$. The two segments connecting $p_{\mathrm{\ell }}$ with $v_g$ and $p_r$ with $v_h$, as well as all edge segments connecting internal vertices of $P_i$ (if any) lie completely above ${\mathrm{\Gamma }}_{i-1}$. So they cannot cross any edge of ${\mathrm{\Gamma }}_{i-1}$. The port ${\rho }_{\mathrm{\ell }}$ that is used by the edge segment connecting $v_{\mathrm{\ell }}$ with $p_{\mathrm{\ell }}$ is the next available port in $S_{\mathrm{rs}}$, i.e., the one that follows the corresponding port used by the edge $(v_{\mathrm{\ell }},v_{{\mathrm{\ell }}^{\prime }})$. Furthermore, the only edge of $C_{i-1}$ that lies between the x-coordinates of $v_{\mathrm{\ell }}$ and $p_{\mathrm{\ell }}$ is the edge $(v_{\mathrm{\ell }},v_{{\mathrm{\ell }}^{\prime }})$. So no edge of $C_{i-1}$ and thus no edge of ${\mathrm{\Gamma }}_{i-1}$ can be crossed by the edge segment connecting $v_{\mathrm{\ell }}$ and $p_{\mathrm{\ell }}$. A symmetric argument applies to the edge segment connecting $v_r$ and $p_r$. Since these two edge segments cannot cross each other, it follows that ${\mathrm{\Gamma }}_i$ is planar, as desired. Having ensured this property, the fact that the contour $C_i$ of ${\mathrm{\Gamma }}_i$ is $x$-monotone is implied by the choice of ${\rho }_{\mathrm{\ell }}$ and ${\rho }_r$ and by the fact that ${\rho }_{\mathrm{\ell }}\in$$S_{\mathrm{rs}}$ and ${\rho }_r\in$$S_{\mathrm{ls}}$. Hence, ${\mathrm{\Gamma }}_i$ satisfies Invariant I.1.

Before considering the case where $P_i$ is a singleton of degree greater than $2$ in $G_i$, we establish an upper bound on how much the drawing ${\mathrm{\Gamma }}_{i-1}$ must be stretched horizontally to accommodate $v_g,\mathrm{\dots },v_h$ in ${\mathrm{\Gamma }}_i$. To this end, consider the edge $(v_{\mathrm{\ell }},v_g)$. Let $x_{\mathrm{\ell }}$ be the $x$-coordinate of $p_{\mathrm{\ell }}$ before applying any stretching. Let also $s_{\mathrm{\ell }}\in$$S_{\mathrm{rs}}$ be the slope of the edge segment connecting $v_{\mathrm{\ell }}$ with $p_{\mathrm{\ell }}$; symmetrically, $s_r\in$$S_{\mathrm{ls}}$ is defined. It follows that $x_{\mathrm{\ell }}=x(v_{\mathrm{\ell }})+\frac{y(v_g)-y(v_{\mathrm{\ell }})}{s_{\mathrm{\ell }}}\le x(v_{\mathrm{\ell }})+\frac{y(v_g)}{s_{\mathrm{\ell }}}$. After the stretching of the edge $(v_{\mathrm{\ell }},v_{{\mathrm{\ell }}^{\prime }})$, the $x$-coordinate of $p_{\mathrm{\ell }}$ should be at most $x(v_{{\mathrm{\ell }}^{\prime }})-1$. To achieve this, the edge $(v_{\mathrm{\ell }},v_{{\mathrm{\ell }}^{\prime }})$ must be stretched by at most $x_{\mathrm{\ell }}-(x(v_{{\mathrm{\ell }}^{\prime }})-1)\le x(v_{\mathrm{\ell }})+\frac{y(v_g)}{s_{\mathrm{\ell }}}-x(v_{\mathrm{\ell }})=\frac{y(v_g)}{s_{\mathrm{\ell }}}$ units of length. Symmetrically, the edge $(v_r,v_{r^{\prime }})$ must be stretched by at most $\frac{y(v_g)}{|s_r|}$ units of length. Now the $x$-coordinate of $p_{\mathrm{\ell }}$ is at most the old $x$-coordinate of $v_{\mathrm{\ell }}$ and the $x$-coordinate of $p_r$ is at least the old $x$-coordinate of $v_r$, so $p_{\mathrm{\ell }}$ and $p_r$ are at least one unit apart. To make space for $v_g,\mathrm{\dots },v_h$ between them, we might have to stretch the edge $(v_{\mathrm{\ell }},v_{{\mathrm{\ell }}^{\prime }})$ by $h-g+1$ more units. Since $|P_i|=h-g+1$, it follows that the total stretch applied is at most

Suppose that $P_i=\{v_g\}$ is a singleton of degree greater than $2$ in $G_i$. Let $v_{\mathrm{\ell }},w_1,\mathrm{\dots },w_q,v_r$, with $q\ge 1$, be the neighbors of $v_g$ in ${\mathrm{\Gamma }}_{i-1}$ as they appear from left to right along $C_{i-1}$. We will place $v_g$ above $w_q$, such that the edge connecting them is vertical; see Figure 3(b). Equivalently, this corresponds to setting the $x$-coordinate of $v_g$ to the one of $w_q$. The $y$-coordinates of $v_g$ will be determined by the constraints arising from the way that $(v_{\mathrm{\ell }},v_g),(v_g,w_1),\mathrm{\dots },(v_g,w_q),(v_g,v_r)$ must be drawn (see Invariants I.5b., I.5c. and I.5d.). More precisely, each edge $(w_j,v_g),1\le j\le q$ will be drawn with a vertical segment incident to $w_j$, which is unoccupied by Invariant I.3, and, if $j\ne q$, with a second segment of slope $s_j=\frac{j}{\mathrm{\Delta }-4}\in \text{<a href="\#S3.I1.ix5" title="item Sf ‣ Proof. ‣ 3 1-bend planar drawings of 𝟑-connected degree-𝚫 planar graphs ‣ How Many Slopes Does Polynomial Area Cost?" class="ltx\_ref"><span class="ltx\_text ltx\_ref\_tag"><xmath xmlns="http://dlmf.nist.gov/LaTeXML"><xmapp><xmtok role="SUBSCRIPTOP" scriptpos="post1"></xmtok><xmtok role="UNKNOWN" font="italic">S</xmtok><xmtok role="UNKNOWN" fontsize="70\%">f</xmtok></xmapp></xmath></span></a>}$. Clearly, if $q\le \mathrm{\Delta }-3$, then Invariant I.5c. is satisfied. This condition always holds when $i\ne m$, or when $i=m$ and the degree of $v_n$ is strictly less than $\mathrm{\Delta }$. We will discuss the remaining case later. Furthermore, the edges $(v_{\mathrm{\ell }},v_g)$ and $(v_g,v_r)$ will be drawn afterwards as in Case 1, thereby satisfying Invariants I.2, I.3, I.5b., and I.5d..

To ensure that the bend point of each edge lies on a grid point, we first ensure that the horizontal distance between $w_j$ and $v_g$ is a multiple of $\mathrm{\Delta }-3$. To this end, let $(w_j,w_j^{\prime })$ be the first edge of $C_{i-1}$ that is encountered when traversing $C_{i-1}$ from $w_j$ to $v_2$ (possibly $w_j^{\prime }=w_{j+1}$). We leverage Invariant I.2 to stretch $(w_j,w_j^{\prime })$ by at most $\mathrm{\Delta }-4$ units so as to guarantee the required distance between $w_j$ and $v_g$. Overall, this increases the width by at most $(q-1)\cdot (\mathrm{\Delta }-4)$ units. To satisfy Invariant I.4, we set the $y$-coordinate of $v_g$ to $H({\mathrm{\Gamma }}_{i-1})+\alpha k$, where $\alpha \in {\mathbb{N}}^{\ast }$ is a parameter that is chosen such that, for every neighbor $w_j$ of $v_g$, the bend point of the edge $(w_j,v_g)$ lies above ${\mathrm{\Gamma }}_{i-1}$; see Figure 3(b). Since the height of the flat segment of the edge $(w_j,v_g)$ is $s_j\cdot (x(v_g)-x(w_j))$, where $x(v_g)-x(w_j)$ is its width, the $y$-coordinate of $v_g$ must be at least $H({\mathrm{\Gamma }}_{i-1})+s_j\cdot (x(v_g)-x(w_j))$. We choose $y(v_g)$ as the smallest multiple of $k$ that fulfills all these bounds. Thus, we have

Having determined the $x$- and $y$-coordinates of $v_g$, the drawing ${\mathrm{\Gamma }}_i$ is completed by drawing each edge incident to $v_g$ in $G_i$ as described above, thereby guaranteeing Invariants I.2-I.5. By an argument analogous to that of Case 1, the edges $(v_{\mathrm{\ell }},v_g)$ and $(v_g,v_r)$ are crossing-free in ${\mathrm{\Gamma }}_i$. We still have to argue that the edges $(w_j,v_g)$ are also crossing free in ${\mathrm{\Gamma }}_i$. The flat slopes of the edges $(w_j,v_g)$, with , have been assigned in counterclockwise order around $v_g$. Also, the left-to-right order of the bend points of these edges matches the left-to-right order of $w_1,\mathrm{\dots },w_{q-1}$ along the contour $C_{i-1}$; see Figure 3(b). Therefore, no two edges $(w_j,v_g)$ and $(w_{j^{\prime }},v_g)$ with can cross each other. Furthermore, the horizontal segments of the edges $(v_{\mathrm{\ell }},v_g)$ and $(v_r,v_g)$ lie above the flat segments of the edges $(w_j,v_g)$, while the stretching performed along the edge $(v_{\mathrm{\ell }},v_{{\mathrm{\ell }}^{\prime }})$ and $(v_r,v_{r^{\prime }})$ ensures that the steep segments of $(v_{\mathrm{\ell }},v_g)$ and $(v_r,v_g)$ lie completely to the left and to the right of these flat segments; see Figure 4. Since the flat segments of the edges $(w_i,v_g)$ are drawn completely above ${\mathrm{\Gamma }}_{i-1}$, they cannot cross any edge of $G_{i-1}$, thereby implying that ${\mathrm{\Gamma }}_i$ is planar, as desired. Having ensured this property, the fact that the contour $C_i$ of ${\mathrm{\Gamma }}_i$ is $x$-monotone is implied by the fact that the slopes of the two segments of the edge $(v_{\mathrm{\ell }},v_g)$ are in $S_{\mathrm{rs}}$$\cup$$S_{\mathrm{h}}$, while the ones of $(v_g,v_r)$ in $S_{\mathrm{h}}$$\cup$$S_{\mathrm{ls}}$ (i.e., symmetrically to Case 1). Hence, ${\mathrm{\Gamma }}_i$ also satisfies Invariant I.1.

We now establish an upper bound on how much the drawing ${\mathrm{\Gamma }}_{i-1}$ must be stretched horizontally to accommodate $v_g$ in ${\mathrm{\Gamma }}_i$. As in Case 1, the edges $(v_{\mathrm{\ell }},v_{{\mathrm{\ell }}^{\prime }})$ and $(v_r,v_{r^{\prime }})$ have been stretched by at most $\frac{y(v_g)}{s_{\mathrm{\ell }}}$ and $\frac{y(v_g)}{|s_r|}$ units, respectively. Furthermore, the edges $(w_j,w_j^{\prime })$ have been stretched by at most $(q-1)\cdot (\mathrm{\Delta }-4)$ unit in total. Thus, the total stretch applied is at most

To complete the description of our drawing algorithm, it remains to consider the case in which $v_n$ is of degree exactly $\mathrm{\Delta }$. Let $w_1,\mathrm{\dots },w_{\mathrm{\Delta }}$ be the neighbors of $v_n$ as they appear along $C_{m-1}$ from $v_1$ to $v_2$. Before applying our drawing algorithm as described so far, we remove the edge $(w_{\mathrm{\Delta }},v_n)$ from the graph and recolor the edge $(w_{\mathrm{\Delta }-1},v_n)$ green. After the last step of the drawing algorithm, we reinsert the edge $(w_{\mathrm{\Delta }},v_n)$. Since $w_{\mathrm{\Delta }}$ lies on $C_m$ and its degree is strictly less than $\mathrm{\Delta }$ (in the absence of $(w_{\mathrm{\Delta }-1},v_n)$), the vertical top port of $w_{\mathrm{\Delta }}$ is unoccupied by Invariant I.3. By Invariant I.1, we can draw the edge $(w_{\mathrm{\Delta }-1},v_n)$ with a vertical segment at $w_{\mathrm{\Delta }}$ and a segment of slope $\frac{1}{\mathrm{\Delta }-3}$ at $v_n$ (see Figure 2(b)). This completes the drawing of the input graph $G$.

It remains to analyze the width and the height of the drawing. For ease of notation, we denote by $W_i$ and $H_i$, $0\le i\le m$ the width and height of the drawing ${\mathrm{\Gamma }}_i$, that is, $W_i=W({\mathrm{\Gamma }}_i)$ and $H_i=H({\mathrm{\Gamma }}_i)$. In the base of our recursive algorithm, it holds that $W_0=1$ and $H_0=0$. By Equation 2, we obtain $H_i\le H_{i-1}+W_{i-1}+k$. So,

By Section 3 and Section 3, we obtain

By series expansion, we obtain

If we choose $k=4\mathrm{\Delta }{n}^2$, then we have ${\left(1+\frac{2\mathrm{\Delta }}{k}\right)}^n={\left(1+\frac{1}{2n^2}\right)}^n$. Since $\ln (1+x)\le x$ for , we obtain , so

Plugging Equation 5 into Equation 4, we obtain

Plugging this back into Equation 5, we can bound the width by

Reinserting $(v_1,v_2)$ and $(w_{\mathrm{\Delta }},v_n)$ at the end increases the height by at most $2W_m/(\mathrm{\Delta }-3)\le 11.76\mathrm{\Delta }{n}^2\le 1.96\mathrm{\Delta }{n}^3$, since $\mathrm{\Delta }\ge 5$ and $n\ge 6$. Thus, our drawing has area $O({\mathrm{\Delta }}^2{n}^5)$. $◀$ Using the algorithms in [20, 22] (see Section 2), we can augment any planar graph with maximum degree $\mathrm{\Delta }\ge 5$ to a triconnected planar graph of maximum degree at most $\lceil 3\mathrm{\Delta }/2\rceil +3$.

For the special case of planar graphs of maximum degree $5$, we can slightly improve the number of slopes while increasing the required area by a factor of $O(n^2)$.

To reduce the number of slopes, we relax the requirement that the contour of the drawing is $x$-monotone. Instead, at vertices which do not have remaining outgoing edges non-monotone parts are allowed. This allows to construct a drawing using only five slopes, namely, $\{0,\mathrm{\infty },1,k,-k\}$, where $k=5n^2$. The horizontal stretch needed at each step increases to $O(k)+O(W/k)+O(H/k)$, while the height to $O(k)+O(W)+O(H/k)$. Solving the resulting recurrences yields width $O(n^3)$ and height $O(n^4)$. $◀$

Without loss of generality, we may assume that $\mathrm{\Delta }$ is even. Since planar graphs with $\mathrm{\Delta }=4$ always admit an orthogonal drawing with at most two bends per edge on a grid of size $O(n)\times O(n)$ [5, 37], we may further assume $\mathrm{\Delta }\ge 6$. We choose a vertex $v_n$ of $G$ with degree at most $5$ (which exists in every planar graph) and consider a planar embedding $ℰ$ of $G$ with $v_n$ on its outer face. The fact that $G$ is biconnected implies that it admits an $st$-ordering $v_1,\mathrm{\dots },v_n$, such that $(v_1,v_2)$ is an edge of the outer face of $ℰ$. We will use this $st$-ordering to construct incrementally a $2$-bend planar drawing $\mathrm{\Gamma }$ of $G$ on the following set of $\frac{\mathrm{\Delta }}{2}$ slopes: $S=\{-\lfloor \frac{\mathrm{\Delta }}{4}\rfloor +1,\mathrm{\dots },0,\mathrm{\dots },\lceil \frac{\mathrm{\Delta }}{4}\rceil -1,\mathrm{\infty }\}$; see Figure 5(a). In particular, each edge $(v_i,v_j)$ with will be drawn with a first non-vertical segment incident to $v_i$ (of possibly zero length), followed by a vertical segment (of non-zero length) and a last non-vertical segment incident to $v_j$ (of possibly zero length); see Figure 5(b).

We first compute a sketch drawing ${\mathrm{\Gamma }}^{\prime }$ of $G$ using the algorithm of [24, 25] and taking $v_1,\mathrm{\dots },v_n$ as the input $st$-ordering. In the resulting drawing ${\mathrm{\Gamma }}^{\prime }$, each edge is drawn with at most two bends and contains a vertical segment. These vertical segments lie in consecutive columns of ${\mathrm{\Gamma }}^{\prime }$ that also contain the vertices of $G$. Given a vertex $v$ of $G$, we denote by $x(v)$ the index of the column of ${\mathrm{\Gamma }}^{\prime }$ that contains $v$ in the left-to-right ordering of the columns of ${\mathrm{\Gamma }}^{\prime }$. Accordingly, given an edge $e$, with slight abuse of notation, we denote by $x(e)$ the index of the column of ${\mathrm{\Gamma }}^{\prime }$ that contains the vertical segment of $e$ in the left-to-right ordering of the columns of ${\mathrm{\Gamma }}^{\prime }$; see Figure 5(a). Let $S^{\prime }=\{s_{-\lfloor \mathrm{\Delta }/4\rfloor +1}^{\prime },\mathrm{\dots },s_0^{\prime },\mathrm{\dots },s_{\lceil \mathrm{\Delta }/4\rceil -1}^{\prime },s_{\mathrm{\infty }}^{\prime }\}$ be the slopes used in ${\mathrm{\Gamma }}^{\prime }$ such that $s_{\mathrm{\infty }}^{\prime }$ is the vertical slope and if . We produce a drawing $\mathrm{\Gamma }$ of $G$ on a grid of size $O(n)\times O(n^2\mathrm{\Delta })$ such that every edge segment that is drawn with slope $s_i^{\prime }$ in ${\mathrm{\Gamma }}^{\prime }$ is drawn with slope $i$ in $\mathrm{\Gamma }$. Hence, $\mathrm{\Gamma }$ and ${\mathrm{\Gamma }}^{\prime }$ share the same planar embedding. Furthermore, the $x$-coordinate of each vertex $v$ of $G$ will be $x(v)$ in $\mathrm{\Gamma }$, while the $x$-coordinate of the vertical segment of each edge $e$ of $G$ will be $x(e)$. Hence, the width of $\mathrm{\Gamma }$ will be $O(n)$.

Let $G_i$ with $1\le i\le n$ be the subgraph of $G$ induced by $\{v_1,\mathrm{\dots },v_i\}$, and let ${ℰ}_i$ be the restriction of $ℰ$ to $G_i$. We say that an edge $(v_j,v_k)$ of $G$ is a pending edge of $G_i$ if and only if . For $2\le i\le n$, we denote by ${\mathrm{\Gamma }}_i$ a drawing of $G_i$ which additionally contains the first non-vertical segment (if any) of each pending edge of $G_i$. In the following, we will first describe how to compute drawing ${\mathrm{\Gamma }}_2$. Then, assuming that we have recursively computed a drawing ${\mathrm{\Gamma }}_{i-1}$ with , we describe how to compute drawing ${\mathrm{\Gamma }}_i$.

To obtain drawing ${\mathrm{\Gamma }}_2$, we begin by placing $v_1$ at $(0,0)$ and $v_2$ at $(x(v_2),0)$, as in the original algorithm. We connect $v_1$ to $v_2$ with a $2$-bend edge drawn below both vertices. This edge consists of two vertical segments, each of length $\lfloor \frac{\mathrm{\Delta }}{4}\rfloor (2m-n)+1$, incident to $v_1$ and $v_2$, and a horizontal segment connecting their lower endpoints; see Figure 5(c). To complete drawing ${\mathrm{\Gamma }}_2$, we next draw the first non-vertical segment of each pending edge that is incident to $v_1$ and $v_2$ preserving ${ℰ}_2$ as follows. For $j\in \{1,2\}$, consider a pending edge $e=(v_j,v_k)$ with $k>2$ and suppose that this edge has a non-vertical segment incident to $v_j$ in ${\mathrm{\Gamma }}^{\prime }$. Let $s_{\mathrm{\ell }}^{\prime }$ be the slope of this segment in ${\mathrm{\Gamma }}^{\prime }$. We draw a segment starting at $v_j$ with slope $\mathrm{\ell }$ until its $x$-coordinate equals $x(e)$. This point serves as the first bend of $e$ and is a grid point, since $S$ consists of integer slopes. Furthermore, the vertical extent of this segment is at most $\lfloor \mathrm{\Delta }/4\rfloor \cdot |x(e)-x(v_j)|$. This guarantees that this segment does not cross $(v_1,v_2)$, since the width of the drawing is bounded by $2m-n$, as we will shortly show, and thus, $|x(e)-x(v_j)|\le 2m-n$.

We now describe how to compute drawing ${\mathrm{\Gamma }}_i$, assuming that we have recursively constructed drawing ${\mathrm{\Gamma }}_{i-1}$. We place $v_i$ at $x$-coordinate $x(v_i)$ and $y$-coordinate $(i-1)\cdot (\mathrm{\Delta }/2\cdot (2m-n)+1)$, such that $v_i$ lies above one of its median predecessors in $G_i$, as in the original algorithm. Then, we complete the drawing of the edges connecting $v_i$ to its neighbors in $G_{i-1}$ while preserving ${ℰ}_i$. Consider such an edge $e=(v_j,v_i)$ with $i>j$ and assume that $s_{\mathrm{\ell }}^{\prime }$ is the slope of its last non-vertical segment in ${\mathrm{\Gamma }}^{\prime }$. In drawing ${\mathrm{\Gamma }}_i$, we draw a segment starting at $v_i$ with slope $\mathrm{\ell }$ until its $x$-coordinate equals $x(e)$ followed by a vertical segment that connects it to the endpoint of the first non-vertical segment of the edge $e$ (which has already been drawn, when ${\mathrm{\Gamma }}_j$ was computed). To complete the drawing of ${\mathrm{\Gamma }}_i$, we draw the first non-vertical segments of the pending edges incident to $v_i$ in the same way as described for ${\mathrm{\Gamma }}_2$. It follows that the vertical extent of any non-vertical segment incident to $v_i$ belonging to edge $e$ is bounded by $\lfloor \mathrm{\Delta }/4\rfloor \cdot |x(e)-x(v_i)|$.

Since each vertex $v_i$ and its incident edges occupy at most $\mathrm{deg}(v_i)-1$ columns, the total width of the resulting drawing $\mathrm{\Gamma }$ of $G$ is bounded by ${\sum }_{i=1}^n(\mathrm{deg}(v_i)-1)=2m-n\in O(n)$. To estimate the height of $\mathrm{\Gamma }$, let $H_i$ be the maximum $y$-coordinate in ${\mathrm{\Gamma }}_i$. For each $i>2$, $H_i$ is determined by the $y$-coordinate of $v_i$ plus the vertical extent of the first non-vertical segment of each of the pending edges of $v_i$ plus the vertical extent of edge $(v_1,v_2)$. Thus,