Layered Polyline Drawings of Planar Graphs

Every $n$-vertex planar graph admits a straight-line grid drawing with $O(n^2)$ area [11, 25]. Many algorithms have appeared in the literature that compute straight-line drawings [8, 9] and polyline drawings [6, 29] of planar graphs, where one dimension of the drawing (equivalently, number of layers) is bounded by $2n/3$. To provide an upper bound on area, drawing algorithms are typically presented on maximal planar graphs or planar triangulations, where each face of the given embedding is a cycle of three vertices. Similarly, throughout the paper, we will consider the input to be a planar triangulation. This upper bound on the number of layers is tight, that is, every polyline drawing of an $n$-vertex nested triangles graph requires at least $\lfloor 2(n-1)/3\rfloor$ layers [6].

The upper bound of $2n/3$ layers implied by the results in the fixed embedding setting [8, 6, 28] applies also to the variable embedding setting. To the best of our knowledge, it is not known whether a better bound can be achieved for arbitrary planar graphs in the variable embedding setting. However, better upper bounds are known in the variable embedding setting for several subclasses of planar graphs (e.g., outerplanar graphs [3], series-parallel graphs [31, 30], planar graphs with small maximum degree or small cycle separator [17], planar 3-trees [21, 20], and nested triangles graphs [18]). The best known lower bound on layers in the variable embedding setting is $\lfloor n/3-1\rfloor$ [18]. The large gap between the upper and lower bounds motivates this paper.

We develop an algorithm that can draw arbitrary $n$-vertex planar graphs on $14n/27+O(\sqrt{n})$ layers in the variable embedding setting. The idea is to use a balanced cycle separator of size $O(\sqrt{n})$ to decompose the input planar graph into two subgraphs. We draw these subgraphs separately such that they can be merged without adding too many additional layers. The main challenge appears to be computing careful positions of the separator vertices in both drawings such that during the merge step, the vertices can be aligned with small modification. We tackle this by designing a drawing method that allows flexible positioning of separator vertices with necessary visibilities.

Note that the technique of using a separator to decompose a graph into subgraphs and then to merge the drawing of the subgraphs to obtain a drawing has previously been used in the literature [31, 15]. In particular, Durocher and Mondal [15] used a cycle separator of size $\lambda \in O(\sqrt{n})$ to draw an $n$-vertex planar graph in $4n/9+O(\lambda \mathrm{\Delta })$ layers, where $\mathrm{\Delta }$ is the maximum degree in the graph. If $\mathrm{\Delta }\in o(\sqrt{n})$, the bound becomes $4n/9+o(n)$ layers, but for $\mathrm{\Delta }\ge \sqrt{n}$, it can become larger than $n$ layers. When drawing each subgraph in $4n/9$ layers, their strategy was to contract the rest of the graph into a single vertex. However, the merge step required rerouting the edges incident to the separator vertices, which added an additional $O(\lambda \mathrm{\Delta })$ layers. Later, they used an edge separator of size ${\lambda }^{\prime }\in O(\sqrt{n\mathrm{\Delta }})$ instead of a cycle separator to improve the bound to $4n/9+O({\lambda }^{\prime })$ [17]. However, both these additive terms $O(\lambda \mathrm{\Delta })$ and $O({\lambda }^{\prime })$ can sometimes be large (e.g., consider a wheel graph), and the total layer count may exceed $n$.

Let $G$ be a planar triangulation, and let $w_1,w_2$ and $w_n$ be the outer vertices of $G$ in counter-clockwise order. Let $\sigma =(w_1,w_2,\mathrm{\dots },w_n)$ be an ordering of all vertices of $G$. We denote by $G_k$, $3\le k\le n$, the subgraph of $G$ induced by $\{w_1,w_2,\mathrm{\dots },w_k\}$, and by $P_k$, the clockwise path on the outer face of $G_k$ that starts at $w_1$ and ends at $w_2$. The ordering $\sigma$ is called a canonical ordering of $G$ with respect to the outer edge $(w_1,w_2)$ if for each $k$, $3\le k\le n$, the following two conditions are satisfied [11]:

1. (a)

   $G_k$ is $2$-connected and internally triangulated.

2. (b)

   If $k+1\le n$, then $w_{k+1}$ is an outer vertex of $G_{k+1}$ and the neighbors of $w_{k+1}$ in $G_k$ appear consecutively on $P_k$.

For a vertex $w_{k+1}$, let $P_k$ be the outer path $w_1,\mathrm{\dots },$ $w_l,\mathrm{\dots },w_r,\mathrm{\dots },w_2$ of $G_k$, where $w_l$ and $w_r$ are the leftmost and rightmost neighbors of $w_{k+1}$, respectively. We call the edges $(w_l,w_{k+1})$ and $(w_{k+1},w_r)$ the $l$-edge and the $r$-edge of $w_{k+1}$, respectively. The other edges incident to $w_{k+1}$ in $G_k$ are called the $m$-edges of $w_{k+1}$. For example, in Figure 1(a), the edges $(w_{12},w_{10}),(w_{12},w_2)$ are respectively the $l$-edge and $r$-edge of $w_{12}$. The $m$-edges of $w_{12}$ are $(w_{12},w_{11}),(w_{12},w_9)$ and $(w_{12},w_6)$. The set of all $m$-edges in $G$ corresponds to a tree $T_m$, which is rooted at $w_n$ and spans all the inner vertices. Figure 1(b) illustrates $T_m$ in thin solid lines. Similarly, the set of $l$-edges in $G$ except $(w_1,w_n)$ and $(w_1,w_2)$ corresponds to a tree rooted at $w_1$, and the set of $r$-edges except $(w_2,w_n)$ and $(w_1,w_n)$ is a tree rooted at $w_2$. Figure 1(b) depicts the trees $T_l$ and $T_r$ in thick black and thick gray edges, respectively. The trees $\{T_l,T_r,T_m\}$ form the Schnyder realizer [25] of $G$. Each of $T_l,T_r$ and $T_m$ corresponds to a canonical ordering of $G$. Let $\mathrm{leaf}(T_l),\mathrm{leaf}(T_r)$ and $\mathrm{leaf}(T_m)$ be the number of leaves in $T_l,T_r$ and $T_m$, respectively.

The notions of canonical ordering and Schnyder realizer have been extended to other classes of planar graphs that are not necessarily triangulated [1, 2]. However, to describe our algorithm in this paper, we only need to consider the 2-connected and internally triangulated graphs. Let $H$ be a 2-connected and internally triangulated graph with the outer vertices $v_1,\mathrm{\dots },v_k,v_n$ in counter-clockwise order. If $k>2$, then consider a dummy edge $(v_1,v_k)$ and triangulate the face $v_1,\mathrm{\dots },v_k,v_1$. We can now order the inner vertices of $H$ satisfying properties (a) and (b) of a canonical ordering. We can define the $l$- and $r$-edges in the same way as we defined for canonical ordering. Observe that the set of $m$-edges corresponds to a tree $T_m$, which is rooted at $v_n$, but the $l$-edges and $r$-edges may no longer form the trees $T_l$ and $T_r$. To form the trees $T_l$ and $T_r$, we assume the edges on the outer path $v_1,v_2,\mathrm{\dots },v_k$ to belong to both these trees, e.g., Figure 1(c). Let $\mathrm{\Gamma }$ be a drawing of $H$. We call a vertex $v$ of $H$ to have top visibility in $\mathrm{\Gamma }$ if the vertically upward ray starting at $v$ does not intersect $\mathrm{\Gamma }$ except at $v$.

We now have the following lemma, which will be used later to describe our drawing algorithm.

Here we show that $H$ admits a drawing on a $(\mathrm{leaf}(T_m)+k)\times \mathrm{leaf}(T_l)$ grid where the path $v_1,\mathrm{\dots },v_k$ is drawn on the bottommost layer and $v_1,v_k$ has top visibility. This will correspond to the type-(a) drawing of the lemma, whereas the type-(c) drawing can be obtained by rotating the drawing ${90}^{\circ }$. To obtain the drawing of type-(b), one can construct drawing on a $(\mathrm{leaf}(T_m)+k)\times \mathrm{leaf}(T_r)$ grid symmetrically.

We assume familiarity with the “shift algorithm” to compute grid drawings for planar graphs [11]. We treat the vertex $v_n$ as a leaf of $T_l$. Let $z_1(=v_1),\mathrm{\dots },z_k(=v_k),$ $z_{k+1},\mathrm{\dots },$ $z_n(=v_n)$ be the vertices listed according to a preorder traversal of $T_l$, where the children are visited in counter-clockwise order. Then the ordering $\sigma =(z_{k+1},\mathrm{\dots },z_n)$ is another canonical ordering of $G$ [10, Lemma 3.5]. Let ${\mathrm{\ell }}_1(=z_k),{\mathrm{\ell }}_2,\mathrm{\dots },{\mathrm{\ell }}_s(=z_n)$ be the leaves of $T_l$ according to the preorder traversal of $T_l$, where $s$ is the number of leaves in $T_l$. We assign each leaf of $T_l$ a path called pseudo-segment, as follows. The first pseudo-segment ${𝒮}_1$ assigned to ${\mathrm{\ell }}_1$ is the unique path from $z_1$ to $l_1(=z_k)$. The pseudo-segment ${𝒮}_j$ assigned to ${\mathrm{\ell }}_j$, where , is the shortest path in $T_l$ that starts at ${\mathrm{\ell }}_j$ and ends at a vertex which is adjacent to some previous pseudo-segment. Figure 2(a)–(b) illustrates such a pseudo-segment decomposition of $T_l$. Let $H_q$ be the subgraph of $H$ induced by the vertices $z_1,\mathrm{\dots },z_q$, where $1\le q\le n$. We now show that $H_q$ admits a drawing ${\mathrm{\Gamma }}_q$ satisfying the following properties.

$I_1$.

${\mathrm{\Gamma }}_q$ is a polyline drawing on $(\delta +k)\times j$ layers, where $\delta$ is the number of leaves of $T_m$ in $H_q$ and $z_q$ belongs to the pseudo-segment ${𝒮}_j$.

$I_2$.

The y-coordinates of the vertices of a pseudo-segment ${𝒮}_i$ is $i$, where $1\le i\le j$.

$I_3$.

The clockwise path $P_q$ on the outer face of $H_q$ is drawn as a strictly x-monotone polygonal chain in ${\mathrm{\Gamma }}_q$, i.e., the vertices on $P_q$ have top visibility.

We first draw the path $z_1(=v_1),\mathrm{\dots },z_k(=v_k)$ by placing each $z_i$, where $1\le i\le k$, at $(i,1)$ (Figure 2(c)). It is straightforward to verify $I_1$–$I_3$ for ${\mathrm{\Gamma }}_k$. We now add the remaining vertices in the order they appear in $\sigma$. While inserting a new vertex $z_t$, where $t>k$, we consider two cases depending on whether $z_t$ is a leaf or an internal vertex in $T_m$. Let $P_t=(z_1,\mathrm{\dots },z_t^l,z_t,z_t^r,\mathrm{\dots },z_k)$ be the clockwise path on the outer face of $H_t$. Let ${𝒮}_{j^{\prime }}$ be the pseudo-segment that contains $z_t$.

If $z_t$ is a leaf of $T_m$, then we shift the vertices $z_t^r,\mathrm{\dots },z_k$ and their descendants in $T_m$ one unit to the right, e.g., see the vertex insertions in Figure 2(d)–(f). Then we place $z_t$ at $(x(z_t^r)-1,j^{\prime })$. Note that $z_t^l$ and $z_t^r$ have top visibility in ${\mathrm{\Gamma }}_{t-1}$ and retain this visibility even after the shift. Since $j^{\prime }$ is the highest y-coordinate in the current drawing and since $x(z_t)=x(z_t^r)-1$, we can draw the edge $(z_t^r,z_t)$ with a straight line segment without introducing any edge crossing. If $z_t^l$ belongs to ${𝒮}_{j^{\prime }}$ or if $x(z_t)=x(z_t^l)+1$, then we can draw $(z_t,z_t^r)$ with a straight line segment. Otherwise, we use a bend point at $(x(z_t^l)+1,j^{\prime })$.

We now show that ${\mathrm{\Gamma }}_t$ satisfies properties $I_1$–$I_3$. Here $I_1$ holds as the drawing width increases by one unit due to the insertion of a new leaf and the height of the drawing becomes $j^{\prime }$. The shift operation keeps the resulting drawing planar, does not change the y-coordinates of the vertices, and does not affect the x-monotonicity of the edges [11]. Therefore, the drawing of the $l$- and $r$-edges of $z_t$ ensures that the path $(z_t^l,z_t,z_t^r)$ is drawn as an x-monotone polygonal chain where the vertices $z_t^l,z_t,z_t^r$ have top visibility. Consequently, the drawing ${\mathrm{\Gamma }}_t$ satisfies $I_2$ and $I_3$.

If $z_t$ is an internal vertex of $T_m$, then we place $z_t$ at $(x(z_t^r)-1,j^{\prime })$. Let $(z_t,z^{\prime })$ be the first $m$-edge of $z_t$ in clockwise order. Since $P_{t-1}$ is strictly $x$-monotone in ${\mathrm{\Gamma }}_{t-1}$, the other vertices on the pseudo-segment ${𝒮}_{j^{\prime }}$ before $z_t$ lie to the left of the line $x=x(z^{\prime })$. Since $z^{\prime }$ is a child of $v$ in $T_m$, it cannot belong to ${𝒮}_{j^{\prime }}$ and hence its y-coordinate is smaller than $j^{\prime }$. Hence the grid point $(x(z_t^r)-1,j^{\prime })$ is empty.

Since $x(z_t)=x(z_t^r)-1$, we can draw $(z_t,z_t^r)$ with a straight line segment (e.g., insertion of $z_{14}$ in Figure 2(g)). If $z_t^l$ belongs to ${𝒮}_{j^{\prime }}$ or if $x(z_t)=x(z_t^l)+1$, then we can draw $(z_t,z_t^l)$ with a straight line segment. Otherwise, we use a bend point at $(x(z_t^l)+1,j^{\prime })$ (Figure 2(g)). We now consider the drawing of the $m$-edges. To draw an $m$-edge $(z_t,w)$, we first check whether $y(w)=j^{\prime }-1$. If so, then we can draw the edge with a straight line segment. Otherwise, we create a bend point at $(x(w),j^{\prime }-1)$. This is possible because $w$ appears in a pseudo-segment ${𝒮}_{j^{\prime \prime }}$ where , and thus the grid point $(x(w),j^{\prime }-1)$ is empty. Here $I_1$ holds as we do not change the width of the current drawing and the height increases only when we start adding a new pseudo-segment. $I_2$–$I_4$ hold by the drawing of the $l$- and $r$-edges of $z_t$ ensuring the top visibility for $z_t^l,z_t,z_t^r$, and by the property of the shift algorithm that it preserves the y-coordinates of the vertices and the x-monotonicity of the edges [11]. $◀$

Let $G$ be a planar triangulation with a simple cycle separator $C=(v_1,\mathrm{\dots },v_k)$ of size $k=O(\sqrt{n})$, as shown in bold in Figure 3(a). Let $\mathrm{\Gamma }$ be a planar embedding of $G$ and let $(a,b,c)$ be an inner face in $\mathrm{\Gamma }$ such that $(a,b)=(v_1,v_k)$ is an edge of $C$ and $c$ is an inner vertex in $\mathrm{\Gamma }$. We then create a new planar embedding ${\mathrm{\Gamma }}^{\prime }$ by choosing $(a,b,c)$ as the outer face (Figure 3(b)). We then add a subdivision vertex $d$ on the edge $(a,b)$ (Figure 3(c)), and triangulate the inner face incident to $d$. Finally, for each pair of vertices $v_i,v_j$ in $C$, where , if the edge $(v_i,v_j)$ exists in $G$, then we add a subdivision vertex on $(v_i,v_j)$ and triangulate the graph. Let $G^{\prime }$ be the resulting drawing. By $G_i$ ($G_o$) we refer to the subgraph of $G^{\prime }$ that lies in the closed interior (exterior) of $C$. By $n_o$ and $n_i$ we refer to the number of vertices of $G_o$ and $G_i$, respectively. Since we added at most $O(\sqrt{n})$ division vertices, $n_o,n_i\le 2n/3+O(\sqrt{n})$.

Let $T_l^o,T_r^o,T_m^o$ be the trees of a minimum Schnyder realizer of $G_o$ rooted at $a,b,c$, respectively. Similarly, let $T_l^i,T_r^i,T_m^i$ be the trees of a minimum Schnyder realizer of $G_i$ rooted at $b,a,d$, respectively. Let $\alpha \in (0,2/3]$ be a positive constant to be determined later. We now consider two cases depending on whether the following condition holds: $\min \{\mathrm{leaf}(T_l^o),\mathrm{leaf}(T_r^o)\}\le \alpha n$ and $\min \{\mathrm{leaf}(T_l^i),\mathrm{leaf}(T_r^i)\}\le \alpha n$.

In this case we construct a drawing of $G^{\prime }$ on $\alpha n+O(\sqrt{n})$ layers, as follows. By Lemma 2, $G_o$ admits a drawing on $\min \{\mathrm{leaf}(T_l^o),\mathrm{leaf}(T_r^o)\}\le \alpha n$ layers with the path $v_1(=a),v_2,\mathrm{\dots },v_k(=b)$ of the cycle separator drawn on the bottommost layer (Figure 3(d)–(e)). Let $l_0$ be the bottommost layer and let $l_1$ be the layer above $l_0$. We consider a horizontal line $l^{\prime }$ between these two layers (i.e., the blue line in Figure 3(h)) and add a bend point at each intersection point between $l^{\prime }$ and the edges. We insert $k-1$ layers below $l_0$ and move the vertices $v_{k-1},\mathrm{\dots },v_2,v_1(=a)$ on these newly inserted layers consecutively below $b$, as shown in Figure 3(h)–(i). We redraw the edges and part of the edges below $l^{\prime }$ with straight line segments. Since the ordering of the bend points on $l^{\prime }$ corresponds to the ordering of the vertices $a,\mathrm{\dots },b$ in the newly inserted layers, the resulting drawing remains planar. Since $k+1=O(\sqrt{n})$, the drawing takes at most $\alpha n+O(\sqrt{n})$ layers. We draw $G_i$ using Lemma 2 on $\min \{\mathrm{leaf}(T_l^i),\mathrm{leaf}(T_r^i)\}\le \alpha n$ layers with the path $v_1(=a),v_2,\mathrm{\dots },v_k(=b)$ of the cycle separator drawn on the bottommost layer (Figure 3(f)–(g)). We then modify the drawing to bring the vertices $v_{k-1},\mathrm{\dots },v_1(=a)$ on a set of $(k-1)$ consecutive bottommost layers of the drawing below $b$. To obtain the final drawing of $G^{\prime }$, we bring the drawings of $G_o$ and $G_i$ close together such that they coincide on the path $a,\mathrm{\dots },b$ (Figure 3(j)). The top visibility of $b$ ensures planarity, i.e., the polylines representing $(c,b)$ and $(d,b)$ do not overlap. Since these drawings share a common set of layers, the number of layers is bounded by $\alpha n+O(\sqrt{n})$.

Without loss of generality assume that $\min \{\mathrm{leaf}(T_l^o),\mathrm{leaf}(T_r^o)\}>\alpha n$. Then by Lemma 1, we have $\mathrm{leaf}(T_m^o)\le 2n_o-2\alpha n$. In this scenario, we consider two subcases depending on whether $\mathrm{leaf}(T_m^i)\le 2n_i/3$ or not, and in both cases we construct a drawing of $G^{\prime }$ on $2n_o-2\alpha n+O(\sqrt{n})+2n_i/3$ layers.

We first draw $G_o$ using Lemma 2 in $\mathrm{leaf}(T_m^o)+k\le 2n_o-2\alpha n+O(\sqrt{n})$ layers where the path $v_1,\mathrm{\dots },v_k$ is drawn along a vertical line $L$ (perpendicular to the layers) and the drawing lies to the left half-plane of $L$ (Figure 4(a)–(b)). We now draw $G_i$ on the right half-plane of $L$ taking the drawing of $v_1,\mathrm{\dots },v_k$ as input, and inserting the remaining vertices of $G_i$ following the method described in the proof of Lemma 2. This inserts new layers within the drawing of $G_o$. Since $\mathrm{leaf}(T_m^i)\le 2n_i/3$, the total number of layers remains bounded by $2n_o-2\alpha n+O(\sqrt{n})+2n_i/3$ (Figure 4(c)–(d)).

We draw $G_o$ in the same way as in Case 2.1 on $2n_o-2\alpha n+O(\sqrt{n})$ layers. By Lemma 1, either $\mathrm{leaf}(T_l^i)$ or $\mathrm{leaf}(T_r^i)$ is at most $2n_i/3$. By Lemma 2, $G_i$ admits a drawing on $2n_i/3$ layers with the path $v_1(=a),v_2,\mathrm{\dots },v_k(=b)$ drawn on the bottommost layer $l_0$ (Figure 4(e)–(f)). We modify the drawing similar to Case 1 by inserting new layers below $l_0$ and moving the vertices $v_{k-1},\mathrm{\dots },v_1(=a)$ below $b$. However, instead of placing these vertices on consecutive layers, we move them to their corresponding layers in the drawing of $G_o$. Hence the total number of layers after merging the drawings of $G_o$ and $G_i$ is bounded by $2n_o-2\alpha n+O(\sqrt{n})+2n_i/3$ (Figure 4(g)–(h)).

The algorithm produces a drawing on $\max \{\alpha n+O(\sqrt{n}),2n_o-2\alpha n+O(\sqrt{n})+2n_i/3\}$ layers. Since $n_o+n_i=n+O(\sqrt{n})$ and $n_o\le 2n/3+O(\sqrt{n})$, we have

Hence the number of layers is bounded by $\max \{\alpha n+O(\sqrt{n}),14n/9-2\alpha n+O(\sqrt{n})\}$ layers, which is minimized when $\alpha =14/27$. We thus have the following theorem.