Drawing Planar Graphs with Few Segments on a Polynomial Grid

Abstract

The visual complexity of a graph drawing can be measured by the number of geometric objects used for the representation of its elements. In this paper, we study planar graph drawings where edges are represented by few segments. In such a drawing, one segment may represent multiple edges forming a path. Drawings of planar graphs with few segments were intensively studied in the past years. However, the area requirements were only considered for limited subclasses of planar graphs. In this paper, we show that trees have drawings with $3n/4-1$ segments and $n^2$ area, improving the previous result of $O(n^{3.58})$. We also show that 3-connected planar graphs and biconnected outerplanar graphs have a drawing with $8n/3-O(1)$ and $3n/2-O(1)$ segments, respectively, and $O(n^3)$ area.

This work was initiated at the Workshop on Graph and Network Visualization 2017. The work of P. Kindermann was partially supported by DFG grant SCHU 2458/4-1.

1 Introduction

The quality of a graph drawing can be assessed in a variety of ways: area, crossing number, bends, angular resolution, and many more. All these measures have their justification, but in general it is challenging to optimize all of them in a single drawing. Recently, the visual complexity was suggested as another quality measure for drawings [22]. The visual complexity denotes the number of simple geometric entities used in the drawing.

The visual complexity of a straight-line graph drawing can be formalized as the number of segments formed by its edges, which we refer to as segment complexity. Notice that edges constituting a single segment form a path in the graph. The idea of representing graphs with fewer segments complies with the Gestalt principles of perception, which are rules for the organization of perceptual scenes introduced in the area of psychology in the 19th century [16]. According to the law of continuation, the edges forming a segment may be easier grouped by our perception into a single entity. Therefore, drawing graphs with fewer segments may ease their perceptual processing. A recent user study [15] suggests that lowering the segment complexity may positively influence aesthetics, depending on the background of the observer, as long as it does not introduce unnecessarily sharp corners. From the theoretical perspective, it is natural to ask for a drawing of a graph with the smallest segment complexity. It is not surprising that it is $\mathsf{NP}$-hard to determine whether a graph has a drawing with segment complexity k [9]. However, we can still expect to prove bounds for certain graph classes.

Dujmović et al. [7] were the first to study drawings with few segments and provided upper and lower bounds for several planar graph classes. Since then, several new results have been provided ([8, 12, 13, 19, 20], refer also to Table 1). These results shed only a little light on the area requirements of the drawings. In particular, in his thesis, Mondal [19] gives an algorithm for triangulations that produces drawings with $8n/3-O(1)$ segments on a grid of size $2^{O(n\log n)}$ in general and $2^{O(n)}$ for triangulations of bounded degree. Even with this large grid, the algorithm uses substantially more segments than the best-known algorithm for triangulations without the grid requirement by Durocher and Mondal [8], which uses $7n/3-O(1)$ segments. Recently, Hültenschmidt et al. [12] presented algorithms that produce drawings with 3n/4 segments and $O(n^{3.58})$ area for trees, and 3n/2 and 8n/3 segments for outerplanar graphs and 3-trees, respectively, and $O(n^{3})$ area. Igamberdiev et al. [13] have provided an algorithm to construct drawings of planar cubic 3-connected graphs with n/2 segments and $O(n^2)$ area.

Our Contribution. In this paper, we concentrate on finding drawings with low segment complexity on a small grid. Our contribution is summarized in Table 1. In Sect. 2, we show that every tree has a drawing with at most $3n/4-1$ segments on the $n\times n$ grid, improving the area bound by Hültenschmidt et al. [12]. We then focus on drawing 3-connected planar graphs in Sect. 3. Using a combination of Schnyder realizers and orderly spanning trees, we show that every 3-connected planar graph can be drawn with $m-(n-4)/3\le (8n-14)/3$ segments on an $O(n)\times O(n^2)$ grid. Finally, in Sect. 4, we use this result to draw on an $O(n)\times O(n^2)$ grid maximal 4-connected graphs with $5n/2-4$ segments, biconnected outerplanar graphs with $(3n-3)/2$ segments, connected outerplanar graphs with $(7n-9)/4$ segments, and connected planar graphs with $(17n-38)/6$ segments. All our proofs are constructive and yield algorithms to obtain such drawings in O(n) time. As a side result, we also prove that the total number of leaves in every Schnyder realizer of a 3-connected planar graph is at most $2n+1$, which was only known for maximal planar graphs [2, 18]. For the results on biconnected outerplanar 3- and 4-connected graphs, we use techniques that have been used to construct monotone drawings; thus, as a side result, these drawings are also monotone¹.

We note that there are three trivial lower bounds for the segment complexity of a general graph $G=(V,E)$ with n vertices and m edges:(i) $\vartheta /2$, where $\vartheta$ is the number of odd-degree vertices, (ii) $\max _{v\in V} \lceil \deg (v)/2\rceil$, and (iii) $\lceil m/(n-1)\rceil$. These trivial lower bounds are the same as for the slope number of graphs [23], that is, the minimum number of slopes required to draw all edges, and the slope number is upper bounded by the number of segments required.

Relevant to segment complexity are the studies by Chaplick et al. [3, 4] who consider drawings where all edges are to be covered by few lines (or planes); the difference to our problem is that collinear segments are counted only once in their model. In the same fashion, Kryven et al. [17] aim to cover all edges by few circles (or spheres).

Table 1. Upper and lower bounds on the visual complexity of segment drawings. Here, n is the number of vertices, m is the number of edges, $\vartheta$ is the number of odd-degree vertices, and b is the number of maximal biconnected components. Constant-term additions or subtractions have been omitted. Entries marked by a * are monotone drawings. FV corresponds to the full version [14].

2 Trees

Let $T=(V,E)$ be a tree with n vertices. In this section, we describe an algorithm to draw T with at most $3n/4-1$ segments on an $n\times n$ grid in O(n) time.

If T consist only of vertices of degree 1 and 2, then it is a path and we can draw it with 1 segment and $n \times 1$ area. So, we will assume that there is at least one vertex with higher degree. We choose such a vertex as the root of T. Denote the number of degree-2 vertices by $\beta$ and the number of leaves by $\alpha$. In the first step, we create another tree $T'$ with $n-\beta$ vertices by contracting all edges incident to a degree-2 vertex. We say that a degree-2 vertex u belongs to a vertex v if v is the first descendent of u in T that has degree greater than 2. Note that $T'$ has the same number of leaves as T. In the next step, we remove all leaves from $T'$ and obtain a tree $T''$ with $n-\beta -\alpha$ vertices; see Fig. 1.

Fig. 1.

(a) A tree T. Degree-2 vertices are squared, leaves are filled. (b) The tree $T'$ obtained from T by contracting the degree-2 vertices. (c) The tree $T''$ obtained from $T'$ by removing all leaves. (d) The drawing of our algorithm.

The main idea of our algorithm is as follows. We draw $T''$ with $n-\beta -\alpha -1$ segments. Then, we add the $\alpha$ leaves in such a way that they either extend the segment of an edge, or that two of them share a segment, which results in at most $\alpha /2$ new segments. Finally, we place the $\beta$ degree-2 vertices onto the segments without increasing the number of segments. This way, we get a drawing with at most $n-\beta -\alpha /2$ segments. Since $T'$ has no degree-2 vertices, more than half of its vertices are leaves, so $\alpha > (n-\beta )/2$. Hence, the drawing has at most $3(n-\beta )/4< 3n/4$ segments. Unfortunately, there are a few more details we have to take care of to achieve this bound.

Let v be a vertex in $T''$, and let T[v] be the subtree of T rooted at v. Let $n_v$ denote the number of vertices in T[v]. Let $v_1,\ldots ,v_k$ be the children of v in $T''$. As induction hypotheses, we assume that each $T[v_i]$ is drawn inside a polygon $B_i$ of dimensions (edge lengths) $\ell _i,r_i,t_i,b_i, w_i,h_i$ as indicated in Fig. 2a such that

• $(\mathcal{I}_{1})$ no vertex of $T[v_i]$ lies to the top-left of $v_i$, and

• $(\mathcal{I}_{2})$ $B_i$ has area $n_i\times n_i$.

Using three steps, we describe how to draw T[v] inside a polygon $B_v$ of dimensions $\ell _v,r_v,t_v,b_v, w_v,h_v$ such that v lies at coordinate (0, 0). First, we place $T[v_1],\ldots ,T[v_k]$. Second, we add the degree-2 vertices that belong to $v_1,\dots ,v_k$. Finally, we add the leaf-children of v and the degree-2 vertices belonging to them.

Step 1. We aim at placing $v_1$ directly below v, and each polygon $B_{i},i\ge 2,$ to the right of polygon $B_{i-1}$, aligning $v_i$ with the top boundary of $B_{i-1}$; see Fig. 2b. We place $v_1$ at coordinate $(0,-1-\sum _{i=1}^k t_i)$, and each $v_i$ at coordinate $(x(v_{i-1})+r_{i-1}+\ell _i+1,y(v_{i-1})+t_{i-1})$, where x(v) and y(v) are the x- and y-coordinates of v, respectively. By invariant $(\mathcal{I}_{2})$, the total width and height of the drawings of $B_1,\dots ,B_k$ are both at most $\sum _{i=1}^k n_{v_i}$.

Step 2. Let $\beta _i$ be the number of degree-2 vertices that belong to $v_i$. We move each polygon $B_i$ downwards by $\beta _i$, and place the degree-2 vertices above $v_i$; see Fig. 2c. This does not change the placement of any edge of v, the polygons are only moved downwards and are still disjoint, so the drawing remains planar. The height of the drawing increases by at most $\max _{i=1}^k\beta _i\le \sum _{i=1}^k\beta _i$ to $\sum _{i=1}^k (n_{v_i}+\beta _i)$, while the width remains $\sum _{i=1}^k n_{v_i}$.

Step 3. Let $C_v$ the subtree of T[v] that consists of v, its leaf-children in $T'$, and the degree-2 vertices belonging to them. Let $u_1,\ldots ,u_a$ be the leaves of $C_v$ and let $\gamma _1,\ldots ,\gamma _a$ be the number of degree-2 vertices that belong to them. Without lost of generality, assume that $\gamma _1\ge \ldots \ge \gamma _a$. We first consider the case where a is even. We place the leaves alternatively to the bottom-left and to the top-right of v with as many rows between them and v as degree-2 vertices belong to them; we draw each $u_{2i-1}$ and $u_{2i}$ on a segment through v with slope 1/i. To this end, we place $u_{2i-1}$ at coordinate $(-(\gamma _{2i-1}+1)\cdot i,-\gamma _{2i-1}-1)$ and $u_{2i}$ at coordinate $((\gamma _{2i}+1)\cdot i,\gamma _{2i}+1)$ (recall that u is placed at (0, 0)). We are able to place the degree-2 vertices that belong to these leaves between them and v; see Fig. 2d.

Fig. 2.

Drawing of T[v] with $k=4$. (a) $B_v$; (b) the children of v in $T''$; (c) the degree-2 vertices belonging to these children; and (d) the remaining vertices of T[v] which form $C_v$.

If a is odd, then we apply the procedure described above for $u_1,\dots ,u_{a-1}$. Vertex $u_a$ is placed as follows. If v is a leaf in $T''$, then we place $u_a$ below v at coordinate $(0,-\gamma _a-1)$. If v is not a leaf in $T''$, and no degree-2 vertex belongs to v, and v is not the first child of its parent in $T''$ (that is, there will be no edge that leaves v vertically above), then we place $u_a$ above v at coordinate $(0,\gamma _a+1)$ such that it shares a segment with $(v,v_1)$. Otherwise, we place $u_a$ as every other vertex $u_i$ with odd index at coordinate $(-(\gamma _{a}+1)\cdot i,-\gamma _{a}-1)$.

By construction, the segments through v drawn at step 3 cannot intersect $B_2,\ldots ,B_k$, but there might be an intersection between the segment from $u_1$ to v and $B_1$. In this case, we move $B_1$ downwards until the crossing disappears, which makes the drawing planar again. We call this action Step 4. Thus, we have created a drawing of T[v] inside the polygon $B_v$ that complies with invariant $(\mathcal{I}_{1})$. In the following, we show that $B_v$ satisfies invariant $(\mathcal{I}_{2})$.

We analyze the width and height of the part of the drawing of $C_v$. Let $\gamma ^\mathrm {L}=\sum _{i=1}^{\lceil a/2\rceil } \gamma _{2i-1}$ and $\gamma ^\mathrm {R}=\sum _{i=1}^{\lfloor a/2\rfloor } \gamma _{2i}$ be the number of degree-2 vertices drawn to the left and right of v, respectively, and let $\gamma =\gamma ^\mathrm {L}+\gamma ^\mathrm {R}$.

Recall that $\gamma _1\ge \ldots \ge \gamma _a$ and leaf $u_i$ was placed at y-coordinate $\pm (\gamma _i+1)$. Hence, the vertices with the lowest and highest y-coordinate are $u_1$ at $y(u_1)=-\gamma _1-1$ and $u_2$ at $y(u_2)=\gamma _2+1$, respectively. Thus, the height of the drawing of $C_v$ is $1=1\,+\,a\,+\,\gamma$ if $a=0$; $2\,+\,\gamma _1=1\,+\,a\,+\,\gamma$ if $a=1$; and $3\,+\,\gamma _1\,+\,\gamma _2\le 1\,+\,a\,+\,\gamma$ if $a\ge 2$, so at most $1\,+\,a\,+\,\gamma$ in total.

For analyzing the width of the drawing of $C_v$, we first consider those vertices that are drawn to the right of v. Let r be such that $u_{2r}$ is the rightmost vertex at x-coordinate $(\gamma _{2r}+1)\cdot r$. Since $\gamma _1\ge \ldots \ge \gamma _a$, we have that

$$ \gamma ^\mathrm {R}=\sum _{i=1}^{\lfloor a/2\rfloor } \gamma _{2i}\ge \sum _{i=1}^{r} \gamma _{2i} \ge r \cdot \gamma _{2r}.$$

Symmetrically, let $\ell$ be such that $u_{2\ell -1}$ is the leftmost vertex at x-coordinate $-(\gamma _{2\ell -1}+1)\cdot \ell$. We have that

$$\gamma ^\mathrm {L}=\sum _{i=1}^{\lceil a/2\rceil } \gamma _{2i-1}\ge \sum _{i=1}^{\ell } \gamma _{2i-1} \ge \ell \cdot \gamma _{2\ell -1}.$$

Hence, the total width of this part of the drawing is at most

$$\begin{aligned} 1+(\gamma _{2r}+1)\cdot r + (\gamma _{2\ell -1}+1)\cdot \ell \le 1+\ell +r+\gamma ^\mathrm {L}+\gamma ^\mathrm {R}\le 1+a+\gamma . \end{aligned}$$

Recall that before step 3 the width of the drawing of T[v] was $\sum _{i=1}^k{n_{v_i}}$ and the height was at most $\sum _{i=1}^k(n_{v_i}+\beta _i)$. In step 3, the width increases by at most $1+a+\gamma$. In step 4, we move the drawing of $T[v_1]$ downwards if it is crossed by the segment between $u_1$ and v until this crossing is resolved. There cannot be a crossing if $y(u_1)>y(v_1)$, so we move it by at most $|y(u_1)|$ downwards, which is exactly the height of the part of the drawing of $C_v$ that lies below v. Hence, the height in Steps 3 and 4 increases by at most the height of the drawing of $C_v$, which is $1+a+\gamma$. Since $n_v=1+\sum _{i=1}^k (n_{v_i}+\beta _i)+a+\gamma$, the width and the height of $B_v$ is at most $n_v$. With this we complete the proof of invariant $(\mathcal{I}_{2})$.

We will now discuss the number of segments in T. Let r be the root of T, and let $v\in T''\setminus \{r\}$. We need a few definitions; see Fig. 3. Let $p_v$ be the parent of v in $T''$. Let $P_v$ be the path between v and $p_v$ in T; let $T^+[v] = T[v] \cup P_v$; let $n_v^+$ be the number of vertices in $T^+[v] \setminus \{p_v\}$;let $e_v$ be the edge of $P_v$ incident to $p_v$; and let $s_v$ be the number of segments used in the drawing of $T^+[v]$.

Lemma 1

For any vertex $v\ne r$ of $T''$, if $e_v$ is drawn vertical, then $s_v\le (3n^+_v-1)/4$, otherwise $s_v\le 3n^+_v/4$.

Fig. 3.

Illustration of $T^+[v]$ in the proof of Lemma 1.

Proof

We prove the lemma by induction on the height of $T''$, so we can assume that the bound holds for all children of v in $T''$. Recall that $u_1,\ldots ,u_a$ are the leaf-children of v in $T'$, $v_1,\ldots ,v_k$ are the children of v in $T''$, and $v_1$ is connected to v by a vertical segment. Let b be the number of degree-2 vertices that belong to v. Let $n'=\sum _{i=1}^k n^+_{v_i}$; then, $n_v^+\ge n'+a+b+1$. (There might be degree-2 vertices between v and its leaf-children in $T'$ which we do not count.) By induction, $s_{v_1}\le 3(n^+_{v_1}-1)/4$ and $s_{v_i}\le 3n^+_{v_i}/4$ for $2\le i\le k$, so $\sum _{i=1}^k s_{v_i}\le (3n'-1)/4$. It remains to analyze the number of segments for $C_v$ and for the path $P_v$.

Case 1. v is a leaf in $T''$ and $b=0$. Then, $n^+_v\ge a+1$. Since v is a leaf in $T''$, it has at least two children in T, so $a\ge 2$.

Case 1.1. a is even. We use a/2 for $C_v$ plus one for the edge $e_v$. Thus, $s_v \le a/2+1 \le (n^+_v-1)/2+1 =(3n^+_v-n^+_v+2)/4 \le (3n^+_v-1)/4$ since $n^+_v\ge 3$.

Case 1.2. a is odd and $e_v$ is vertical, so $a\ge 3$ and $n^+_v\ge 4$. We use $(a-1)/2$ segments for $u_1,\ldots ,u_{a-1}$ and one segment for $u_a$ and $e_v$. Thus, $s_v \le (a-1)/2\,+\,1 \le n^+_v/2 \le 3n^+_v/4-1$.

Case 1.3. a is odd and $e_v$ is not vertical. We use one more segment than in Case 1.2, so $s_v \le 3n^+_v/4$.

Case 2. v is a leaf in $T''$ and $b>0$. Then, $a\ge 2$ and $n^+_v\ge a+b+1\ge a+2\ge 4$

Case 2.1. a is even and $e_v$ is vertical. We use a/2 segments for $u_1,\ldots ,u_2$, and the degree-2 vertices that belong to v lie on a vertical segment with $e_v$. Hence, we have $s_v\le a/2+1\le n^+_v/2\le 3n^+_v/4-1$.

Case 2.2. a is even and $e_v$ is not vertical. We again have $n^+_v\ge 4$. The degree-2 vertices that belong to v now lie on a different segment than $e_v$, so we have one more segment than in Case 2.1, so $s_v\le 3n/4$.

Case 2.3. a is odd. We have $a\ge 3$ and thus $n^+_v\ge 5$. We have drawn $u_1,\ldots ,u_{a-1}$ paired up. We have drawn $u_a$ on a vertical segment with the degree-2 vertices that belong to v, and we have possibly one more segment for $e_v$. Hence, we have $s_v\le (a-1)/2+2\le (n^+_v+1)/2 = (3n_v^+ -n_v^+ +2)/4 \le (3n_v^+ -3)/4$.

Case 3. v is not a leaf in $T''$ and $b=0$. We have $n^+_v\ge n'\,+\,a\,+\,1$, so $n'\le n^+_v-a-1$.

Case 3.1. $a=0$ and $e_v$ is vertical. Then, $n_v^+=n'+1$ and $e_v$ lies on a vertical segment with the edge $e_{v_1}$. Hence, $s_v\le (3n'-1)/4=(3n^+_v-4)/4$.

Case 3.2. $a=0$ and $e_v$ is not vertical. Again, $n^+_v=n'+1$. We use one segment for $e_v$, so we have $s_v\le (3n'-1)/4+1=3n^+_v/4$.

Case 3.3. $a\ge 2$ is even. We use a/2 segments for $C_v$ and one more for $e_v$. Hence, $s_v \le (3n'-1)/4+a/2+1 =(3n'+2a+3)/4 \le (3n^+_v-a)/4 \le (3n^+_v-2)/4$.

Case 3.4. a is odd and $e_v$ is vertical. We use $(a+1)/2$ segments for $u_1,\ldots ,u_a$, but $e_v$ shares its vertical segment with $e_{v_1}$. Hence, $s_v \le (3n'-1)/4+(a+1)/2 = (3n'+2a+1)/4) \le (3n^+_v-a-2)/4 \le (3n^+_v-3)/4$.

Case 3.5. a is odd and $e_v$ is not vertical. In this case, we place $u_a$ above v such that it lies on a segment with $e_{v_1}$. We use $(a-1)/2$ segments for $u_1,\ldots ,u_{a-1}$ and one segment for $e_v$, so we have the same number of segments as in Case 3.4.

Case 4. v is not a leaf in $T''$ and $b>0$. We have $n^+_v\ge n'+a+b+1\ge n'+a+2$.

Case 4.1. a is even. We use a/2 segments for $u_1,\ldots ,u_a$. The edges of the path $P_v$ share a vertical segment with $e_{v_1}$. We use at most one more segment for $e_v$, so $s_v \le (3n'-1)/4+a/2+1 =(3n'+2a+3)/4 \le (3n^+_v-a-3)/4 \le (3n^+_v-3)/4$.

Case 4.2. a is odd and $e_v$ is vertical. We use the exact same number of segments as in Case 3.4, so $s_v\le (3n^+_v-3)/4$.

Case 4.3. a is odd and $e_v$ is not vertical. We use $(a+1)/2$ segments for $u_1,\ldots ,u_a$. The edges of the path $P_v$ share a vertical segment with $e_{v_1}$, and we need one more segment for $e_v$. Hence, $s_v \le (3n'-1)/4+(a+1)/2+1 =(3n'+2a+5)/4 \le (3n^+_v-a-1)/4 \le (3n^+_v-2)/4$.    $\square$

Now we can bound the total number of segments in the drawing of T.

Lemma 2

Our algorithm draws T with at most $3n/4-1$ segments if $n\ge 3$.

Proof

If T is a path with $n\ge 3$, then the bound trivially holds. If T is a subdivision of a star, then the bound also clearly holds. Otherwise, $T''$ consists of more than one vertex. Let $v_1,\ldots ,v_k$ be the children of the root r of $T''$ such that $v_1$ is connected by a vertical edge. Recall that $n'=\sum _{i=1}^k n^+_{v_i}$. By Lemma 1, the subtrees $T[v_i]^+$, $i=1,\dots , k$ contribute at most $(3n'-1)/4$ segments to the drawing of T. Let a be the number of leaf children of r in $T'$. If a is even, then we use a/2 segments to draw them. If a is odd, then we align one of them with the vertical segment of $v_1$, and draw the remaining with $(a-1)/2$ segments. Since $n\ge n'\,+\,a\,+\,1$, the total number of segments is at most $(3n'-1)/4\,+\,a/2\le 3n/4-a/4-1\le 3n/4-1$.    $\square$

All steps of the algorithm work in linear time. Sorting the leaf-children by the number of degree-2 vertices belonging to them can also be done in linear time with, e.g., CountingSort, as the numbers are bounded by n. Thus, Theorem 1 follows. Figure 1d shows the result of our algorithm for the tree of Fig. 1a.

Theorem 1

Any tree with $n\ge 3$ vertices can be drawn planar on an $n\times n$ grid with $3n/4-1$ segments in O(n) time.

3 3-Connected Planar Graphs

In this section, we present an algorithm to compute planar drawings with at most $(8n-14)/3$ segments for 3-connected planar graphs.

Fig. 4.

Edges in a Schnyder realizer.

Fig. 5.

Definition of orderly spanning tree (bold).

Fig. 6.

Definition of slope-disjointness.

Let G be a triangulation. Let $v_1,v_2,v_3$ be the vertices of the outer face. We decompose the interior edges into three Schnyder trees $T_1$, $T_2$, and $T_3$ rooted at $v_1$, $v_2$, and $v_3$, respectively. The edges of the trees are oriented towards their roots. For $k\in \{1,2,3\}$, we call each edge in $T_k$ a k-edge and the parent of a vertex in $T_k$ its k-parent. The decomposition is a Schnyder realizer [21] if at every interior vertex the edges are counter-clockwise ordered as: outgoing 1-edge, incoming 3-edges, outgoing 2-edge, incoming 1-edges, outgoing 3-edge, and incoming 2-edges; see Fig. 4. A Schnyder tree $T_k$ also contains the exterior edges of $v_k$, so each exterior edges lies in two Schnyder trees and each $v_k$ is a leaf in the other two Schnyder trees; hence, each Schnyder tree is a spanning tree.

For 3-connected planar graphs, Schnyder realizers also exist [6, 10], but the interior edges can be bidirected: an edge (u, v) is bidirected if it is an outgoing i-edge at u and an outgoing j-edge at v with $i\ne j$. All other edges are unidirected, that is, they are an outgoing i-edge at u and an incoming i-edge at v (or vice-versa). The restriction on the cyclic ordering around each vertex remains the same, but now the Schnyder trees are not necessarily edge-disjoint.

Chiang et al. [5] have introduced the notion of orderly spanning trees. Recently, orderly spanning trees were redefined by Hossain and Rahman [11] as good spanning trees. We will use the definition by Chiang et al., but note that these two definitions are equivalent. Two vertices in a rooted spanning tree are unrelated if neither of them is an ancestor of the other one. A tree is ordered if the circular order of the edges around each vertex is fixed. Let $G=(V,E)$ be a plane graph and let $r\in V$ lie on the outer face. Let T be an ordered spanning tree of G rooted at r that respects the embedding of G. Let $v_1,\ldots ,v_n$ be the vertices of T as encountered in a counter-clockwise pre-order traversal. For any vertex $v_i$, let $p(v_i)$ be its parent in T, let $C(v_i)$ be the children of v in T, let $N(v_i)$ be the neighbors of $v_i$ in G that are unrelated to $v_i$; see Fig. 5. Further, let $N^-(v_i)=\{v_j\in N(v_i)\mid j<i\}$ and $N^+(v_i)=\{v_j\in N(v_i) \mid j>i\}$. Then, T is called orderly if the neighbors around every vertex $v_i$ are in counter-clockwise order $p(v_i)$, $N^-(v_i)$, $C(v_i)$, $N^+(v_i)$. In particular, this means that there is no edge in G between $v_i$ and an ancestor in T that is not its parent and there is no edge in G between $v_i$ and a descendent in T that is not its child. This fact is crucial, as it allows us to draw a path in an orderly spanning tree on a single segment without introducing overlapping edges.

Angelini et al. [1] have introduced the notion of a slope-disjoint drawing of a rooted tree T, which is defined as follows; see Fig. 6.

• (S1) For every vertex u in T, there exist two slopes $\alpha _1(u)$ and $\alpha _2(u)$ with $0<\alpha _1(u)<\alpha _2(u)<\pi$, such that, for every edge e that is either (p(u), u) or lies in T[u], it holds that $\alpha _1(u)<{{\,\mathrm{slope}\,}}(e)<\alpha _2(u)$;

• (S2) for every directed edge (v, u) in T, it holds that $\alpha _1(u)<\alpha _1(v)<\alpha _2(v)<\alpha _2(u)$ (recall that edges are directed towards the root); and

• (S3) for every two vertices u, v in T with $p(u)=p(v)$, it holds that either $\alpha _1(u)<\alpha _2(u)<\alpha _1(v)<\alpha _2(v)$ or $\alpha _1(v)<\alpha _2(v)<\alpha _1(u)<\alpha _2(u)$.

Lemma 3

([1]). Every slope-disjoint drawing of a tree is planar and monotone.

We will now create a special slope-disjoint drawing for rooted orderly trees.

Lemma 4

Let $T=(V,E)$ be an ordered tree rooted at a vertex r with $\lambda$ leaves. Then, T admits a slope-disjoint drawing with $\lambda$ segments on an $O(n)\times O(n^2)$ grid such that all slopes are integer. Such a drawing can be found in O(n) time.

Proof sketch

Let $v_1,\ldots ,v_n = r$ be the vertices of T as encountered in a counter-clockwise post-order traversal. Let $e_i=(v_i,p(v_i)),1\le i<n$. We assign the slopes to the edges of T in the order $e_1,\ldots ,e_{n-1}$. We start with assigning slope $s_1=1$ to $e_1$. For any other edge $e_i,1<i<n$, if $v_i$ is a leaf in T, then we assign the slope $s_i=s_{i-1}+1$ to $e_i$. Otherwise, since we traverse the vertices in a post-order, $p(v_{i-1})=v_i$ and we assign the slope $s_i=s_{i-1}$ to $e_i$.

We create a drawing $\Gamma$ of T as follows. We place $r=v_n$ at coordinate (0, 0). For every other vertex v with parent p that is drawn at coordinate (x, y), we place v at coordinate $(x+1,y+{{\,\mathrm{slope}\,}}(v))$.

We now analyze the number of segments used in $\Gamma$; slope-disjointness, area, and running time are proven in the full version [14]. The root r is an endpoint of $\deg (r)$ segments and every leaf is an endpoint of exactly 1 segment. For every other vertex v, its incoming edge and one of its outgoing edges lie on the same segment, so it is an endpoint of $\deg (v)-2$ segments. Since every segment has two endpoints, the total number of segments is

$$\begin{aligned}&\frac{1}{2}\left( \deg (r)+\sum _{v\text { not leaf},v\ne r}(\deg (v)-2)+\sum _{v\text { leaf}}\deg (v)\right) \\ =\,&\frac{1}{2}\left( \sum _{v}\deg (v)-2(n-\lambda -1)\right) =\frac{1}{2}\left( 2n-2-2n+2\lambda +2\right) =\lambda . \end{aligned}$$

   $\square$

Lemma 5

Let $G=(V,E)$ be a planar graph and let T be an orderly spanning tree of G with $\lambda$ leaves. Then, G admits a planar monotone drawing with at most $m-n+1+\lambda$ segments on an $O(n)\times O(n^2)$ grid in O(n) time.

Proof

We first create a drawing of T according to Lemma 4. Now, we will plug this tree drawing into the algorithm by Hossain and Rahman [11].

This algorithm takes a slope-disjoint drawing of an orderly spanning tree T of G and stretches the edges of T such that the remaining edges of G can be inserted without crossings. In this stretching operation, the slopes of the edges of T are not changed. Further, the total width of the drawing only increases by a constant factor. Since T is drawn slope-disjoint, this produces a planar monotone drawing of G on an $O(n)\times O(n^2)$ grid. The algorithm runs in O(n) time.

To count the number of segments, assume that every edge of G that does not lie on T is drawn with its own segment. We have drawn T with $\lambda$ segments and the slopes of the edges of T. Hence, our algorithm draws G with $\lambda$ segments for T and with $m-n+1$ segments for the remaining edges.    $\square$

Both Chiang et al. [5] and Hossain and Rahman [11] have shown that every planar graph has an embedding that admits an orderly spanning tree. However, we do not know anything about the number of leaves in an orderly spanning tree. Miura et al. [18] have shown that Schnyder trees are orderly spanning trees, and it is known that every 3-connected planar graph has a Schnyder realizer.

Lemma 6

([18]). Let $G=(V,E)$ be a 3-connected planar graph and let $T_1$, $T_2$, and $T_3$ be the Schnyder trees of a Schnyder realizer of G. Then, $T_1$, $T_2$, and $T_3$ are orderly spanning trees of G.

Bonichon et al. [2] showed that there is a Schnyder realizer for every triangulated graph such that the total number of leaves in $T_1$, $T_2$, and $T_3$ is at most $2n+1$, which already gives us a good bound on the number of segments for triangulations. We will now show that the same holds for every Schnyder realizer of a 3-connected graph. Let v be a leaf in one of the Schnyder trees $T_k$, $k\in \{1,2,3\}$, that is not the root of a Schnyder tree, so v has no incoming k-edge. Hence, the outgoing $(k+1)$-edge (v, u) and the outgoing $(k-1)$-edge (v, w) are consecutive in the cyclical ordering around v, so they lie on a common face f. We assign the pair (v, k) to f. We first show two lemmas.

Lemma 7

Let $u_1,\ldots ,u_p$ be the vertices on an interior face f in ccw order. If $(u_1,k)$ and $(u_2,i)$ are assigned to f for some $i,k\in \{1,2,3\}$, then $i=k$.

Proof

Refer to Fig. 7. By definition, $(u_1,u_2)$ is an outgoing $(k+1)$-edge at $u_1$. Since $u_1$ is a leaf in $T_k$, $(u_1,u_2)$ cannot be an outgoing k-edge at $u_2$. Hence, $(u_1,u_2)$ is either an incoming $(k+1)$-edge at $u_2$ (if it is unidirected), or an outgoing $(k-1)$-edge at $u_2$ (if it is bidirected); it cannot be an outgoing $(k+1)$-edge since bidirected edges have to belong to two different Schnyder trees. For $(u_2,i)$ to be assigned to f, $u_2$ must have two outgoing edges at f, so we are in the latter case. Hence, $(u_2,u_3)$ is outgoing at $u_2$, and by the cyclical ordering of the edges around $u_2$, it is an outgoing $(k+1)$-edge. Thus, $u_2$ has an outgoing $(k+1)$-edge and an outgoing $(k-1)$-edge at f, so $i=k$.    $\square$

Fig. 7.

(Left) Proof of Lemma 7 and (right) proof of Lemma 8.

Lemma 8

Let $u_1,u_2,\ldots ,u_p$ be vertices on an interior face f in counter-clockwise order. If $u_3,\ldots ,u_p$ are assigned to f, then neither $u_1$ nor $u_2$ are.

Proof sketch

From Lemma 7, it follows that $(u_3,k),\ldots ,(u_p,k)$ are assigned to f for some $k\in \{1,2,3\}$, so $(u_1,u_p)$ is an outgoing $(k+1)$-edge at $u_p$ and $(u_2,u_3)$ is an outgoing $(k-1)$-edge at $u_3$; since $u_1$ and $u_p$ are leaves in $T_k$, $(u_1,u_p)$ is either an incoming $(k+1)$-edge or an outgoing $(k-1)$-edge at $u_1$ and $(u_2,u_3)$ is either an incoming $(k-1)$-edge or an outgoing $(k+1)$-edge at $u_2$. However, each of the four possible configurations violates the properties of a Schnyder realizer, as illustrated in Fig. 7. The full proof is given in the full version [14].    $\square$

Now we prove the bound on the number of leaves in a Schnyder realizer.

Lemma 9

Let $T_1,T_2,T_3$ be a Schnyder realizer of a 3-connected planar graph $G=(V,E)$. Then, there are at most $2n+1$ leaves in total in $T_1$, $T_2$, and $T_3$.

Proof

Consider any interior face f of G. By definition of the assignment, no vertex can be assigned to f twice. By Lemma 8, at least two vertices on f are not assigned to f, so we assign at most $\deg (f)-2$ leaves to f. At the outer face $f^*$, every vertex that is not the root of a Schnyder tree can be assigned as a leaf at most once. However, the root of each of the Schnyder trees has no outgoing edges, but it can be a leaf in both the other two Schnyder trees. Hence, we assign at most $\deg (f^*)+3$ leaves to the outer face. Let F be the faces in G. Since, for every Schnyder tree, each of its leaves gets assigned to exactly one face, the total number of leaves in $T_1$, $T_2$, and $T_3$ is at most

$$\begin{aligned} \sum _{f\in F}\left( \deg (f)-2\right) +5= 2m-2|F|+5=2m+2n-2m-4+5=2n+1. \end{aligned}$$

   $\square$

Now we have the tools to prove the main result of this section.

Theorem 2

Any 3-connected planar graph can be drawn planar monotone on an $O(n)\times O(n^2)$ grid with $m-(n-4)/3$ segments in O(n) time.

Proof

Let $G=(V,E)$ be a 3-connected planar graph. We compute a Schnyder realizer of G, which is possible in O(n) time. By Lemma 9, the Schnyder trees have at most $2n+1$ leaves in total, so one of them, say $T_1$, has at most $(2n+1)/3$ leaves. By Lemma 6, $T_1$ is an orderly spanning tree, so we can use Lemma 5 to obtain a planar monotone drawing of G on an $O(n)\times O(n^2)$ grid with at most $m-n+1+(2n+1)/3= m-n/3+4/3$ segments in O(n) time.    $\square$

Since a planar graph has at most $m\le 3n-6$ edges, we have the following.

Corollary 1

Any 3-connected planar graph can be drawn planar monotone on an $O(n)\times O(n^2)$ grid with $(8n-14)/3$ segments in O(n) time.

4 Other Planar Graph Classes

We can use the results of Sect. 3 to obtain grid drawings with few segments for other planar graph classes on an $O(n)\times O(n^2)$ grid in O(n) time. In particular, we can draw (i) 4-connected triangulations with $5n/2 - 4$ segments; (ii) biconnected outerplanar graphs with $m - (n - 3)/2\le (3n-3)/2$ segments; (iii) outerplanar graphs with $(7n-9)/4$ segments, or with $(3n - 5)/2 + b$ segments, where b is its number of maximal biconnected components; and (iv) planar graphs with $(17n\,-\,38)/3-m$ or $(17n-38)/6$ segments. Details are given in the full version [14].