Universal Slope Sets for Upward Planar Drawings
Michael A. Bekos Emilio Di Giacomo Walter Didimo Giuseppe Liotta Fabrizio Montecchiani

Exact eigenvalue assignment of linear scalar systems with single delay using Lambert W function
    [
    March 15, 2018
===============================================================================================



arabic


 
We prove that every set  of Δ slopes containing the horizontal slope is universal for 1-bend upward planar drawings of bitonic st-graphs with maximum vertex degree Δ, i.e., every such digraph admits a 1-bend upward planar drawing whose edge segments use only slopes in . This result is worst-case optimal in terms of the number of slopes, and, for a suitable choice of , it gives rise to drawings with worst-case optimal angular resolution. In addition, we prove that every such set  can be used to construct 2-bend upward planar drawings of n-vertex planar st-graphs with at most 4n-9 bends in total. Our main tool is a constructive technique that runs in linear time.  






§ INTRODUCTION


Let G be a graph with maximum vertex degree Δ. The k-bend planar slope number of G is the minimum number of slopes for the edge segments needed to construct a k-bend planar drawing of G, i.e., a planar drawing where each edge is a polyline with at most k ≥ 0 bends. Since no more than two edge segments incident to the same vertex can use the same slope, ⌈Δ/2 ⌉ is a trivial lower bound for the k-bend planar slope number of G,  irrespectively of k. Besides its theoretical interest, this problem forms a natural extension of two well-established graph drawing models: The orthogonal <cit.> and the octilinear drawing models <cit.>, which both have several applications, such as in VLSI and floor-planning <cit.>, and in metro-maps and map-schematization <cit.>. Orthogonal drawings use only 2 slopes for the edge segments (0 and π/2), while octilinear drawings use no more than 4 slopes (0, π/4, π/2, and 3π/4); consequently, they are limited to graphs with Δ≤ 4 and Δ≤ 8, respectively.

These two drawing models have been generalized to graphs with arbitrary maximum vertex degree Δ by Keszegh et al. <cit.>, who proved that every planar graph admits a 2-bend planar drawing with ⌈Δ/2 ⌉ equispaced slopes. As a witness of the tight connection between the two problems, the result by Keszegh et al. was built upon an older result for orthogonal drawings of degree-4 planar graphs by Biedl and Kant <cit.>. In the same paper, Keszegh et al. also studied the 1-bend planar slope number and showed an upper bound of 2 Δ and a lower bound of 3/4(Δ - 1) for this parameter. The upper bound has been recently improved, initially by Knauer and Walczak <cit.> to 3/2(Δ - 1) and subsequently by Angelini et al. <cit.> to Δ-1. Angelini et al. actually proved a stronger result: Given any set  of Δ-1 slopes, every planar graph with maximum vertex degree Δ admits a 1-bend planar drawing whose edge segments use only slopes in . Any such slope set is hence called universal for 1-bend planar drawings. This result simultaneously establishes the best-known upper bound on the 1-bend planar slope number of planar graphs and the best-known lower bound on the angular resolution of 1-bend planar drawings, i.e., on the minimum angle between any two edge segments incident to the same vertex. Indeed, if the slopes in  are equispaced, the resulting drawings have angular resolution at least π/Δ-1. 


In this paper we study slope sets that are universal for k-bend upward planar drawings of directed graphs (or digraphs for short). Recall that in an upward drawing of a digraph G, every edge (u,v) is drawn as a y-monotone non-decreasing curve from u to v. Also, G admits an upward planar drawing if and only if it is a subgraph of a planar st-graph <cit.>. As such drawings are common for representing planar digraphs, they have been extensively studied in the literature  (see, e.g., <cit.>). A preliminary result for this setting is due to Di Giacomo et al. <cit.>, who proved that every series-parallel digraph with maximum vertex degree Δ admits a  1-bend upward planar drawing that uses at most Δ slopes, and this bound on the number of slopes is worst-case optimal. Notably, their construction gives rise to drawings with optimal angular resolution π/Δ (but it uses a predefined set of slopes). Upward drawings with one bend per edge and few slopes have also been studied for posets by Czyzowicz et al. <cit.>.



Contribution. We extend the study of universal sets of slopes to upward planar drawings, and present the first constructive technique that works for all planar st-graphs. This technique exploits a linear ordering of the vertices of a planar digraph introduced by Gronemann <cit.>, called bitonic st-ordering (see also Section <ref>). We show that any set  of Δ slopes containing the horizontal slope is universal for 1-bend upward planar drawings of  degree-Δ planar digraphs having a bitonic st-ordering (Section <ref>). We remark that the size of  is worst-case optimal <cit.> and, if the slopes of  are chosen to be equispaced, the angular resolution of the resulting drawing is at least π/Δ (also optimal); see Fig. <ref> for an illustration. We then extend our construction to all planar st-graphs by using two bends on a restricted number of edges (Section <ref>). More precisely, we show that, given a set  of Δ slopes containing the horizontal slope, every n-vertex upward planar digraph with maximum vertex degree Δ has a 2-bend upward planar drawing that uses only slopes in  and with at most 4n-9 bends in total; see  Fig. <ref> for an illustration. 

For space reasons some proofs are in appendix.








§ PRELIMINARIES



We assume familiarity with common notation and definitions about graphs, drawings, and planarity (see, e.g., <cit.>). 



 

An upward planar drawing of a directed simple graph (or digraph for short) G is a planar drawing such that each edge of G is drawn as a curve monotonically non-decreasing in the y-direction. An upward drawing is strict if its edge curves are monotonically increasing. A digraph is upward planar if it admits an upward planar drawing. Note that if a digraph admits an upward drawing then it also admits a strict upward drawing.  A digraph is upward planar if and only if it is a subgraph of a planar st-graph <cit.>. Let G=(V,E) be an n-vertex planar st-graph, i.e., G is a plane acyclic digraph with a single source s and a single sink t, such that s and t belong to the boundary of the outer face and the edge (s,t) ∈ E <cit.>. (Other works do not explicitly require the edge (s,t) to be part of G, see, e.g., <cit.>.) An st-ordering of G is a numbering : V →{1,2,…,n} such that for each edge (u,v) ∈ E, it holds (u) < (v) (which implies (s)=1 and (t)=n). Every planar st-graph has an st-ordering, which can be computed in O(n) time (see, e.g., <cit.>).
If u and v are two adjacent vertices of G such that (u)<(v), we say that v is a successor of u, and u is a predecessor of v. Denote by S(u) = {v_1,v_2,…,v_q} the sequence of successors of v ordered according to the clockwise circular order of the edges incident to u in the planar embedding of G. The sequence S(u) is bitonic if there exists an integer 1 ≤ h ≤ q such that (v_1) <  … < (v_h-1) < (v_h) > (v_h+1) > … > (v_q); see Fig. <ref> for an illustration. Notice that when h=1 or h=q, S(u) is actually a monotonic decreasing or increasing sequence. A bitonic st-ordering of G is an st-ordering such that, for every vertex u ∈ V, S(u) is bitonic <cit.>. A planar st-graph G is a bitonic st-graph if it admits a bitonic st-ordering. Deciding whether G is bitonic can be done in linear time both in the fixed <cit.> and in the variable <cit.> embedding settings. If G is not bitonic, every st-ordering  of G contains a forbidden configuration defined as follows. A sequence of successors S(u) of a vertex u forms a forbidden configuration if there exist two indices i and j, with i<j, such that (v_i) > (v_i+1) and (v_j) < (v_j+1), i.e. there is a path from v_i+1 to v_i and a path from v_j to v_j+1; see Fig. <ref>.

Let G=(V,E) be an n-vertex maximal plane graph with vertices u, v, and w on the boundary of the outer face. A canonical ordering <cit.> of G is a linear ordering = {v_1=u,v_2=v,…,v_n=w} of V, such that for every 3 ≤ i ≤ n:

[C1:]


  *  The subgraph G_i induced by {v_1,v_2,…,v_i} is 2-connected and internally triangulated, while the boundary of its outer face C_i is a cycle containing (v_1,v_2);


  *  If i+1≤ n, v_i+1 belongs to C_i+1 and its neighbors in G_i form a subpath of the path obtained by removing (v_1,v_2) from C_i.


Computing  takes O(n) time <cit.>. Also,  is upward if for every edge (u,v) of a digraph G u precedes v in .

The slope of a line ℓ is the angle α that a horizontal line needs to be rotated counter-clockwise in order to make it overlap with ℓ. If α=0 we say that the slope of ℓ is horizontal. The slope of a segment is the slope of the line containing it. Let ={α_1,…,α_h} be a set of h slopes such that α_i < α_i+1. The slope set  is equispaced if α_i+1 - α_i = π/h, for i=1,…,h-1.  

Consider a k-bend planar drawing Γ of a graph G, i.e., a planar drawing in which every edge is mapped to a polyline containing at most k+1 segments. For a vertex v in Γ each slope α∈ defines two different rays that emanate from v and have slope α. If α is horizontal these rays are called left horizontal ray and right horizontal ray. Otherwise, one of them is the top and the other one is the bottom ray of v. We say that a ray r_v of a vertex v is free if there is no edge attached to v through r_v in Γ. We also say that r_v is outer if it is free and the first face encountered when moving from v along r_v is the outer face of Γ. 

The slope number of a k-bend drawing Γ is the number of distinct slopes used for the edge segments of Γ. The k-bend upward planar slope number of an upward planar digraph G is the minimum slope number over all k-bend upward planar drawings of G. 






§ 1-BEND UPWARD PLANAR DRAWINGS

  
Let G=(V,E) be an n-vertex planar st-graph with a bitonic st-ordering ={v_1,v_2,…,v_n}; see, e.g., Fig. <ref>. We begin by describing an augmentation technique to “transform”  into an upward canonical ordering of a suitable supergraph  of G. We start from a result by Gronemann <cit.>, whose properties are summarized in the following lemma; see, e.g., Fig. <ref>.


	Let G=(V,E) be an n-vertex planar st-graph that admits a bitonic st-ordering ={v_1,v_2,…,v_n}. There exists a planar st-graph G'=(V',E') with an st-ordering ={v_L,v_R,v_1,v_2,…,v_n} such that:

[(i)]

  * V'=V∪{v_L,v_R}; 


  * E ⊂ E' and (v_L,v_R) ∈ E'; 


  * v_L and v_R are on the boundary of the outer face of G'; 


  *  Every vertex of G with less than two predecessors in  has exactly two predecessors in .



Also, G' and  are computed in O(n) time.


We call G' a canonical augmentation of G. Observe that G' always contains the edges (v_L,v_1) and (v_R,v_1) because of (<ref>). We also insert the edge (v_L,v_n), which is required according to our definition of st-graph; this addition is always possible because v_L and v_n are both on the boundary of the outer face. The next lemma shows that any planar st-graph obtained by triangulating G' admits an upward canonical ordering; see, e.g., Fig. <ref>.  





Let G' be a canonical augmentation of an n-vertex bitonic st-graph G. Every planar st-graph  obtained by triangulating G' has the following properties:

[(a)]

  *  it has no parallel edges;


  *  ={v_L,v_R,v_1,v_2,…,v_n} is an upward canonical ordering. 

 


Concerning Property (<ref>), suppose for a contradiction that  has two parallel edges e_1 and e_2 connecting u with v. Let 𝒞 be the 2-cycle formed by e_1 and e_2 and let V_𝒞 be the set of vertices distinct from u and v that are inside 𝒞 in the embedding of . V_𝒞 is not empty, as otherwise 𝒞 would be a non-triangular face of . Let w be the vertex with the lowest number in  among those in V_𝒞. Since  is planar (in particular e_1 and e_2 are not crossed) and has a single source, it contains a directed path from u to every vertex in V_𝒞. Hence, it has an edge from u to w. Also, by assumption, there is no vertex z in V_𝒞 such that (z) < (w), which implies that u is the only predecessor of w in , a contradiction to Lemma <ref>(<ref>). Concerning Property (<ref>), if  is a canonical ordering of , then  is actually an upward canonical ordering because it is also an st-ordering. To see that  is a canonical ordering, observe first that v_L, v_R and v_n are on the boundary of the outer face of  by construction. Denote by _i the subgraph of  induced by {v_L,v_R,v_1,…,v_i} and let _i be the boundary of its outer face. We first prove by induction on i (for i=1,2,…,n) that _i is 2-connected. In the base case i=1, _1 is a 3-cycle and therefore it is 2-connected. In the case i>1, _i-1 is 2-connected by induction and v_i has at least two predecessors in _i-1 by Lemma <ref>(<ref>), thus _i is 2-connected. We now prove that each _i, for i=1,2,…,n, is internally triangulated, which concludes the proof of condition C<ref> of canonical ordering. Suppose, for a contradiction, that there exists an inner face f that is not a triangle. Since  is triangulated, there exists a vertex v_j, with j > i, that is embedded inside f in _j. Since  is an st-ordering, there is no directed path from v_j to any vertex of f. On the other hand, either v_j=v_n or there is a directed path from v_j to v_n. Both cases contradict the fact that v_n belongs to the boundary of the outer face of . We finally show that v_i belongs to C_i, for i=1,2,…,n. Since we already proved that _i is triangulated, this is enough to prove C<ref>. By the planarity of _i, there is a face f in _i-1 such that all the neighbors of v_i in _i-1 belong to the boundary of f. We claim that f is the outer face of _i. If it was an inner face, then v_i would be embedded inside f in _i and, by the same argument used above,  v_n would not belong to the boundary of the outer face of .


We now show that any set of Δ slopes  that contains the horizontal slope is universal for 1-bend upward planar drawings of bitonic st-graphs. The algorithm is inspired by a technique of Angelini et al. <cit.>. We will use important additional tools with respect to <cit.>, such as the construction of a triangulated canonical augmentation,  extra slopes to draw the edges inserted by the augmentation procedure, and different geometric invariants.

Let G be an n-vertex bitonic st-graph with maximum vertex degree Δ; see Fig. <ref>. The algorithm first computes a triangulated canonical augmentation  of G; see Figs. <ref>–<ref>. We call dummy edges all edges that are in  but not in G and real edges the edges in  that are also in G. By Lemma <ref>,  admits an upward canonical ordering ={v_L,v_R,v_1,v_2,…,v_n}, where  is an st-ordering such that each vertex distinct from v_L and v_R has at least two predecessors. Let ={ρ_1,…,ρ_Δ} be any set of Δ slopes, which we call real slopes. Let ρ^* be the smallest angle between two slopes in  and let Δ^* be the maximum number of dummy edges incident to a vertex of . For each slope ρ_i (1 ≤ i ≤Δ), we add Δ^* dummy slopes {δ^i_1,…,δ^i_Δ^*} such that δ^i_j = ρ_i + j ·ρ^*/Δ^*+1, for j=1,2,…, Δ^*. Hence, there are Δ^* dummy slopes between any two consecutive real slopes. We will use the real slopes for the real edges and the dummy slopes for the dummy ones. 

Let _i be the subgraph of  induced by {v_L,v_R,v_1,v_2,…,v_i}. The algorithm  constructs the drawing by adding the vertices according to . More precisely, it computes a drawing _i of the digraph ^-_i obtained from _i by removing the dummy edges  (v_L,v_R) and (v_1,v_R), which exist by construction, and (v_R,v_2) if it exists. Let _i be the boundary of the outer face of _i, and let _i be the path obtained by removing (v_L,v_R) from _i.
For a vertex v of _i, we denote by vi (resp. vi) the number of real (resp. dummy) edges incident to v that are not in _i and by j(v,i) (resp. j(v,i)) the j-th outer real top ray in _i encountered in clockwise (resp. counterclockwise) order around v starting from the left (resp. right) horizontal ray.
For dummy top rays, we define analogously j(v,i) and j(v,i).



_i  satisfies the following invariants:


	
  I1 _i is a 1-bend upward planar drawing whose real edges use only slopes in .
	
	
  I2 Every edge of _i contains a horizontal segment.
	
	
  I3 Every vertex v of _i has at least vi outer real top rays; see Fig. <ref>.
	
	
  I4 Every vertex v of _i has at least vi outer dummy top rays between 1(v,i) and 1(v,i) (resp. 1(v,i) and 1(v,i)), including 1(v,i) (resp. 1(v,i)); see Fig. <ref>.   
	
  I5 Let ℓ be any horizontal line and let p and p' be any two intersection points between ℓ and the polyline representing _i in _i; walking along ℓ  from left to right, p and p' are encountered in the same order as when walking along _i from v_L to v_R; see Fig. <ref>.


The last vertex v_n is added to _n-1 in a slightly different way and the resulting drawing will satisfy I1. 

The next two lemmas state  important properties of any 1-bend upward planar drawing satisfying I1–I5. Similar lemmas are proven in <cit.>, but for drawings that satisfy different invariants. 



	Let _i be a drawing of ^-_i that satisfies Invariants I1–I5. Let (u,v) be any edge of _i such that u is encountered before v  along _i when going from v_L to v_R, and let λ be a positive number. There exists a drawing '_i of ^-_i that satisfies Invariants I1–I5 and such that: (i) the horizontal distance between u and v is increased by λ; (ii) the horizontal distance between any two other consecutive vertices along _i is the same as in _i.





The next lemma can be proven by suitably applying Lemma <ref>; see Figs. <ref>-<ref>.


	Let _i be a drawing of ^-_i that satisfies Invariants I1–I5. Let u be a vertex of _i, and let t_u be any outer top ray of u that crosses an edge of ^-_i in _i. There exists a drawing '_i of ^-_i that satisfies Invariants I1–I5 in which t_u does not cross any edge of ^-_i.
























We now describe our drawing algorithm starting with the computation of _2. We aim at drawing both v_1 and v_2 horizontally aligned between v_L and v_R. Note that v_1 is the source of G, and, by the definition of a canonical augmentation, v_1 is adjacent to both v_L and v_R, while v_2 is adjacent to v_1 and to at least one of v_L and v_R. We remove the dummy edges (v_1,v_R) and (v_L,v_R), and the dummy edge (v_R,v_2) if it exists. The resulting graph is either the path ⟨ v_L, v_1, v_2, v_R ⟩ or the path ⟨ v_L, v_2, v_1, v_R ⟩, which we draw along a horizontal segment. 


	Drawing _2 satisfies Invariants I1–I5.





Assume now that we have constructed drawing _i-1 of _i-1 satisfying I1–I5 (3 ≤ i < n). Let {u_1,…,u_q} be the neighbors of the next vertex v_i along _i-1. Let t_1 be either 1(u_1,i-1), if (u_1,v_i) is real, or 1(u_1,i-1), if (u_1,v_i) is dummy. Symmetrically, let t_q be either 1(u_q,i-1), if (u_q,v_i) is real, or 1(u_q,i-1), if (u_q,v_i) is dummy. 
Let t_j (for 1 < j < q) be any outer real (resp. dummy) top ray emanating from u_j if (u_j,v_i) is real (resp. dummy). By  I3 all such top rays exist and by Lemma <ref> we can assume that none of them crosses _i-1.



Let ℓ be a horizontal line above the topmost point of _i-1. Let p_j be the intersection point of t_j and ℓ. We can assume that, for j=1,2,…,q-1, p_j is to the left of p_j+1. If this is not the case, we can increase the distance between u_j and u_j+1 so to guarantee that p_j and p_j+1 appear in the desired order along ℓ; this can be done by applying Lemma <ref> with respect to each edge (u_j,u_j+1) for a suitable choice of λ; see Figs. <ref>-<ref> for an illustration.

We will place v_i above ℓ using q-2 bottom rays b_2,b_3,…,b_q-1  of v_i for the segments of the edges (u_j,v_i) (j=2,3,…,q-1) incident to v_i such that: (i) b_j (1 <j < q) is real (resp. dummy) if (u_j,v_i) is real (resp. dummy); (ii) b_j precedes b_j+1 in the counterclockwise order around v_i starting from b_2. This choice is possible for the real rays  because v_i has Δ-1 real bottom  rays and it has at least one incident real edge not in _i (otherwise it would be a sink of G, which is not possible because i < n). Concerning the dummy rays, we have at most Δ^* dummy edges incident to v_i and Δ^* dummy bottom rays between any two consecutive real rays.    

Consider the ray t_1 and choose a point p to the right of t_1 and above ℓ such that placing v_i on p guarantees that min_i=1 … q-2{x(p'_i+1)-x(p'_i)} > x(p_q)-x(p_1), where p'_1=p_1 and  p'_2,p'_3,…,p'_q-1 are the intersection points of the rays b_2,b_3,…,b_q-1 with the line ℓ (see Fig. <ref>). Observe that for a sufficiently large y-coordinate, point p can always be found. 

We now apply Lemma <ref> to each of the edges (u_1,u_2), (u_2,u_3), …, (u_q-2,u_q-1), in this order, choosing λ≥ 0 so that each p_j is translated to p'_j (for j=2,3,…,q-1). We finally apply again the same procedure to (u_q-1,u_q) so that the intersection point between t_q and the horizontal line ℓ_H passing through v_i is to the right of v_i (see Fig. <ref>). After this translation procedure, we can draw the edge (u_1,v_i) (resp. (u_q,v_i)) with a bend at the intersection point between t_1 (resp. t_q) and ℓ_H and therefore using the slope of t_1 (resp. t_q) and the horizontal slope (see Fig. <ref>). The edges (u_j,v_i) (j=2,3,…,q-1) are drawn with a bend point at p_j=p'_j and therefore using the slopes of t_j and b_j.


	Drawing _i, for i=3,4,…,n-1, satisfies Invariants I1–I5.


	The proof is by induction on i ≥ 3. _i-1 satisfies Invariants I1–I5 by Lemma <ref> when i=3, and by induction when i > 3. 
	
	Proof of I1. By construction, each (u_j,v_i) (j=1,2,…,q) is drawn as a chain of at most two segments that use real and dummy slopes. In particular, if (u_j,v_i)  is real, then it uses real slopes, i.e., slopes in . By the choice of ℓ, the bend point of (u_j,v_i) has y-coordinate strictly greater than that of u_j and smaller than or equal to that of v_i. Since each (u_j,v_i) is oriented from u_j to v_i (as  is an upward canonical ordering), the drawing is upward. Concerning planarity, we first observe that _i-1 is planar and it remains planar each time we apply Lemma <ref>. Also, by Lemma <ref> each (u_j,v_i) (j=1,2,…,q) does not intersect _i-1 (except at u_j). Further, the order of the bend points along ℓ guarantees that the edges incident to v_i do not cross each other. 
	
Proof of I2. The only edges of _i that are not in _i-1 are (u_1,v_i) and (u_q,v_i). For both these edges the segment incident to v_i is horizontal by construction.
	
Proof of I3. For each vertex of _i distinct from u_1, u_q and v_i, I3 holds by induction. Invariant I3 also holds for v_i because v_ii≤Δ-1 (as otherwise v_i would be a source of G, which is not possible because i>1) and all the real top rays of v_i, which are Δ-1, are outer. Consider now vertex u_1 (a symmetric argument applies to u_q). If (u_1,v_i) is real, then u_1i=u_1i-1-1; in this case t_1=1(u_1,i-1) and therefore all the other u_1i-1-1 outer real top rays of u_1 in _i-1 remain outer in _i. If (u_1,v_i) is dummy, then u_1i=u_1i-1; in this case t_1=1(u_1,i-1) and therefore all the u_1i-1 outer real top rays of u_1 in _i-1 remain outer in _i. 
	
	
Proof of I4. For each vertex of _i distinct from u_1, u_q and v_i, I4 holds by induction. I4 also holds for v_i because v_ii≤Δ^* and there are Δ^* dummy top rays between 1(v_i,i) and 1(v_i,i) including 1(v_i,i) (all the top rays of v_i are outer). Analogously, there are Δ^* outer dummy top rays between 1(v_i,i) and 1(v_i,i) including 1(v_i,i). Consider now u_1 (a symmetric argument applies to u_q). If (u_1,v_i) is real, then u_1i=u_1i-1; in this case t_1=1(u_1,i-1) and there are Δ^* outer dummy top rays between 1(u_1,i) and 1(u_1,i) including 1(u_1,i) (namely, all those between t_1=1(u_1,i-1) and 2(u_1,i-1)). If (u_1,v_i) is dummy, then u_1i=u_1i-1-1; in this case t_1=1(u_1,i-1) and therefore all the other u_1i-1-1 outer dummy top rays of u_1, which by induction were between 1(u_1,i-1) and 1(u_1,i-1), remain outer in _i. 	 
	
 Proof of I5. Notice that the various applications of Lemma <ref> to _i-1 preserve I5. Let p and p' be any two intersection points between a horizontal line ℓ and the polyline representing _i in _i, with p to the left of p' along ℓ. If p and p' belong to _i-1, I5 holds by induction. If both p and p' belong to the path ⟨ u_1, v_i, u_q ⟩, I5 holds by construction. If p belongs to _i-1 and p' belongs to ⟨ u_1, v_i, u_q ⟩, then p belongs to the subpath of _i-1 that goes from v_L to u_1 because the subpath from u_q to v_R is completely to the right of t_q, hence I5 holds also in this case. If p belongs to ⟨ u_1, v_i, u_q ⟩ and p' belongs to _i-1, the proof is symmetric.    



	G has a 1-bend upward planar drawing Γ using only slopes in .


	By Lemma <ref>, drawing _n-1 satisfies Invariant I1–I5. We explain how to add the last vertex v_n to obtain a drawing that satisfies Invariant I1. Let  {u_1,…,u_q} be the predecessors of v_n on _n-1. Notice that, in this case u_1=v_L and u_q=v_R. Vertex v_n is added to the drawing similarly to all the other vertices added in the previous steps of the algorithm. The only difference is that the number of real incoming edges incident to v_n in _n-1 can be up to Δ. If this is the case, since the real bottom rays are Δ-1, they are not enough to draw all the real edges incident to v_n. Let j be the smallest index such that (u_j,v_n) is a real edge. We ignore all the dummy edges (u_h,v_n), for h=1,2,…,j-1, and apply the construction used in the previous steps considering only {u_j,u_j+1,…,u_q} as predecessors of v_n (notice that such predecessors are at least two because v_n has at least two incident real edges). By ignoring these dummy edges, the segment of the real edge (u_j,v_n) incident to v_n will be drawn using the left horizontal slope. Denote by _n the resulting drawing. As in the proof of Lemma <ref>, we can prove that I1 holds for _n and therefore _n is a 1-bend upward planar drawing whose real edges use only slopes in . The drawing Γ of G is obtained from _n by removing all its dummy edges and the two dummy vertices v_L and v_R.



	Drawing Γ can be computed in O(n) time.

	
Lemmas <ref> and <ref> are summarized by Theorem <ref>. Corollary <ref> is a consequence of Theorem <ref> and of a result in <cit.>.


	Let  be any set of Δ≥ 2 slopes including the horizontal slope and let G be an n-vertex bitonic planar st-graph with maximum vertex degree Δ. Graph G has a 1-bend upward planar drawing Γ using only slopes in , which can be computed in O(n) time.























	Every bitonic st-graph with maximum vertex degree Δ≥ 2 has 1-bend upward planar slope number at most Δ, which is worst-case optimal.





If  is equispaced, Theorem <ref> implies a lower bound of π/Δ on the angular resolution of the computed drawing, which is worst-case optimal <cit.>. 

Also, Theorem <ref> can be extended to planar st-graphs with Δ≤ 3, as any such digraph can be made bitonic by only  rerouting the edge (s,t).


	Every planar st-graph with maximum vertex degree 3 has 1-bend upward planar slope number at most 3.





We conclude with the observation that an upward drawing constructed by the algorithm of Theorem <ref> can be transformed into a strict upward drawing that uses Δ+1 slopes rather than Δ. It suffices to replace every horizontal segment oriented from its leftmost (rightmost) endpoint to its rightmost (leftmost) one with a segment having slope ε (-ε), for a sufficiently small value of ε>0.



§ 2-BEND UPWARD PLANAR DRAWINGS




We now extend the result of Theorem <ref> to non-bitonic planar st-graphs. By adapting a technique of Keszegh et al. <cit.>, one can construct 2-bend upward planar drawings of planar st-graphs using at most Δ slopes. We improve upon this result in two ways: (i) The technique in <cit.> may lead to drawings with 5n-11 bends in total, while we prove that 4n-9 bends suffice; (ii) It uses a fixed set of Δ slopes (and it is not immediately clear whether it can work with any set of slopes), while we show that any set of Δ slopes with the horizontal one is universal. 

Let G be an n-vertex non-bitonic planar st-graph. All forbidden configurations of G can be removed in linear time by subdividing at most n-3 edges of G <cit.>. Let G_b be the resulting bitonic st-graph, called a bitonic subdivision of G. Let ⟨ u,d,v ⟩ be a directed path of G_b  obtained by subdividing the edge (u,v) of G with the dummy vertex d. We call (u,d) the lower stub, and (d,v) the upper stub of (u,v). We can prove the existence of an augmentation technique similar to that of Lemma <ref>, but with an additional property on the upper stubs.



	Let G=(V,E) be an n-vertex planar st-graph that is not bitonic. Let G_b=(V_b,E_b) be an N-vertex bitonic subdivision of G, with a bitonic st-ordering ={v_1,v_2,…,v_N}. There exists a planar st-graph G'=(V',E') with an st-ordering ={v_L,v_R,v_1,v_2,…,v_N} such that:
	
	[(i)]
		
  * V'=V_b∪{v_L,v_R}; 
	 	
	 	
  * E_b ⊂ E' and (v_L,v_R) ∈ E'; 
	 	
	 	
  * v_L and v_R are on the boundary of the outer face of G'; 
	 	
	 	
  *  Every vertex of G_b with less than two predecessors in  has exactly two predecessors in .
	 	
	 	
  *  There is no vertex in G' such that its leftmost or its rightmost incoming edge is an upper stub. 
	 	
	
	
	Also, G' and  are computed in O(n) time.




Let  be any set of Δ≥ 2 slopes including the horizontal slope and let G be an n-vertex planar st-graph with maximum vertex degree Δ. Graph G has a 2-bend upward planar drawing Γ using only slopes in , which has at most 4n-9 bends in total and which can be computed in O(n) time.


	We compute a triangulated canonical augmentation  of G by (1) applying Lemma <ref> and (2) triangulating the resulting digraph. By Lemma <ref>,  has an upward canonical ordering .  
	The algorithm of Theorem <ref> to  would lead to a 3-bend drawing of G (by interpreting every subdivision vertex as a bend). We explain how to modify it to construct a drawing  of  with at most 2 bends per edge and 4n-9 bends in total. 
	
	Let v_i the next vertex to be added according to  and let {u_1,u_2,…,u_q} its neighbors in _i-1. Suppose that u_j is a dummy vertex and that (u_j,v_i) is an upper stub. To save one bend along the edge subdivided by u_j, we draw (u_j,v_i) without bends. By Lemma <ref> (<ref>), we have that 1 < j < q. The ray t_j used to draw the segment of (u_j,v_i) incident to u_j can be any outer real top ray; we choose the ray with same slope as the real bottom  ray b_j used to draw the segment of (u_j,v_i) incident to v_i. This is possible because all real top rays of u_j are outer (since (u_j,v_i) is the only real outgoing edge of u_j). Hence, edge (u_j,v_i) has no bends. 
	
	The drawing Γ of G is obtained from  by removing dummy edges and replacing dummy vertices (except v_L and v_R, which are removed) with bends. Since the upper stubs of subdivided edges has 0 bends, each edge of Γ has at most 2 bends. Let m_1 and m_2 be the number of edges drawn with 1 and 2 bends, respectively; we have m_2 ≤ n-3 and m_1=m-m_2 ≤ 3n-6 -(n-3)=2n-3. Thus the total number of bends is at most 2n-3+2(n-3)=4n-9. Finally,  can be computed in O(n) time (Lemma <ref>) and the modified drawing algorithm still runs in linear time.



A planar st-graph with a source/sink of degree Δ requires at least Δ -1 slopes in any upward planar drawing; thus the gap with Theorem <ref> is one unit. Similarly to Theorem <ref>, Theorem <ref> implies a lower bound of π/Δ  on the angular resolution of Γ; an upper bound of π/Δ-1 can be proven with the same digraph used for the lower bound on the slope number.

Finally, Theorem <ref> extends the result of Theorem <ref> to every upward planar graph using an additional slope.




	Let  be any set of Δ+1 slopes including the horizontal slope and let G be an n-vertex upward planar graph with maximum vertex degree Δ≥ 2. Graph G has a 2-bend upward planar drawing using only slopes in .
 



§ OPEN PROBLEMS





[(i)] 
	
	
  * Can we draw every planar st-graph with at most one bend per edge (or less than 4n-9 in total) and Δ slopes?
	
	
  * What is the 2-bend upward planar slope number of planar st-graphs? Is Δ  a tight bound?
	
	
	
	
  * What is the straight-line upward planar slope number of upward planar digraphs?
	


Acknowledgments. Research partially supported by project: 
	“Algoritmi e 
	sistemi di analisi visuale di 
	reti complesse e di grandi dimensioni - Ricerca di Base 
	2018, Dipartimento di Ingegneria, Università degli Studi di  Perugia”.

splncs04









§ APPENDIX




§ MISSING PROOFS OF SECTION <REF>







	Let _i be a drawing of ^-_i that satisfies Invariants I1–I5. Let (u,v) be any edge of _i such that u is encountered before v  along _i when going from v_L to v_R, and let λ be a positive number. There exists a drawing '_i of ^-_i that satisfies Invariants I1–I5 and such that: (i) the horizontal distance between u and v is increased by λ; (ii) the horizontal distance between any two other consecutive vertices along _i is the same as in _i.


	We prove by induction on i that there exists a cut (L_i(u,v),R_i(u,v)) such that: (i) the vertices of the subpath of _i from v_L to u belong to L_i(u,v), while the vertices of the subpath of _i from v to v_R belong to R_i(u,v); (ii) every edge that crosses the cut has a horizontal segment (see Figure <ref>).  
	
	This is trivially true for each edge (u,v) in _2. Assume that it is true for _i-1 by induction (i > 2). Let u_1,u_2,…,u_q be the neighbors of v_i in _i-1; observe that _i is obtained from _i-1 by replacing the subpath ⟨ u_1, u_2,…, u_q ⟩ with ⟨ u_1, v_i, u_q ⟩. Consider an edge (u,v) of _i. If (u,v) also belongs to _i-1 then ⟨ u_1, u_2,…, u_q ⟩ all belong to either L_i-1(u,v) or to R_i-1(u,v), say to L_i-1(u,v) (see also Fig. <ref>). This implies that the cut (L_i(u,v),R_i(u,v)) with  L_i(u,v)=L_i-1(u,v) ∪{v_i} and  R_i(u,v)=R_i-1(u,v) satisfies (i) and (ii). If (u,v) does not belong to _i-1 then (u,v) is either (u_1,v_i) or (v_i,u_q) (see Fig. <ref>). Suppose it is  (u_1,v_i) (the other case is similar). Consider the cut (L_i-1(u_1,u_2),R_i-1(u_1,u_2)). Since by I2 (u_1,v_i) contains an horizontal segment and there is a face of _i that contains both (u_1,u_2) and (u_1,v_i), the cut 
	(L_i(u,v),R_i(u,v)) with  L_i(u,v)=L_i-1(u,v) and  R_i(u,v)=R_i-1(u,v) ∪{v_i} satisfies (i) and (ii).
	
	We construct the drawing '_i from _i by increasing the length of the edges that cross the cut (L_i(u,v),R_i(u,v)) by λ units. In other words, we increase by λ units the x-coordinate of all vertices in R_i(u,v). It is immediate to verify that '_i is a 1-bend upward drawing whose real edges use only slopes in  and that '_i satisfies I2–I4. 
	
	Concerning planarity, we claim that translating the subdrawing induced by R_i(u,v) does not violate planarity. Suppose for a contradiction that '_i is not planar. Then there exist two non-adjacent edges e_L and e_R of _i that intersect in a point p. Since e_L and e_R did not cross in _i,  p belongs to only one of the two edges in _i, say e_L, and there exists a point p' of e_R in _i that has been translated to p when transforming _i into '_i. This means that p' is encountered before p when walking from left to right along the horizontal line ℓ passing through p and p'. Since p' has been translated and p has not, p' belongs to the subpath of _i that goes from v to v_R, while p belongs to the subpath of _i from v_L to v. In other words, when walking along _i from v_L to v_R, p is encountered before p'. But this contradict Invariant I5 for _i, which means that '_i is planar.
	
	We finally prove that I5 holds for '_i. Let ℓ be any horizontal line and let p and p' be any two intersection points between ℓ and the polyline representing _i in _i, with p to the left of p' along ℓ. If, in '_i, the order of p and p' along ℓ is reversed or p and p' coincide, then p has been translated while p' has been not. On the other hand, since Invariant I5 holds for _i, p precedes p' when walking along _i from v_L to v_R and therefore if p is translated, p' is also translated. Thus, I5 holds for '_i.




	Let _i be a drawing of ^-_i that satisfies Invariants I1–I5. Let u be a vertex of _i, and let t_u be any outer top ray of u that crosses an edge of ^-_i in _i. There exists a drawing '_i of ^-_i that satisfies Invariants I1–I5 in which t_u does not cross any edge of ^-_i.


	The ray t_u can cross the subpath of _i from v_L to u and/or the subpath of _i from u to v_R. Let v and w be the vertices that are encountered before and after u along _i when going from v_L to v_R, respectively. To remove the crossing(s) it is sufficient to apply Lemma <ref> to (v,u) and/or to (u,w) for a sufficiently large λ; see Figs. <ref>-<ref> for an illustration.    






	_2 satisfies Invariants I1–I5.


	Invariants I1, I2, and I5 trivially hold. Since v_L2=v_R2=0, I3 trivially holds for v_L and v_R. Vertices v_1 and v_2 are connected by a real edge and therefore each of them has at most Δ-1 real incident edges that are not in _2. Since there are Δ-1 real top rays and they are all outer, I3 holds also for v_1 and v_2. I4 holds because all dummy top rays are outer. 




	Drawing Γ can be computed in O(n) time.



A bitonic st-ordering  of G can be computed in O(n) time <cit.>, and the same time complexity suffices to compute a canonical augmentation G' of G by Lemma <ref>. A triangulated planar st-graph  can be obtained in O(n) time by augmenting G' as follows.  For every non-triangular face f of G', let t_f be the (unique) sink in f. For each vertex u of f different from t_f we add the edge (u,t_f) inside f, unless this edge already belongs to the boundary of f. Clearly, all these edges can be added in a planar way and each face of the resulting digraph is triangular. By construction, for any edge (u,v)  added to triangulate G' there exists a directed path from u to v in G'. Thus (u,v) does not create any directed cycle and  has a single source (vertex v_L) and a single sink (vertex v_n) that are the same as in G'. Therefore, the triangulated digraph  is a planar st-graph. The construction of _i from _i-1, for i=3,4,…,n,  requires O(deg(v_i)) applications of Lemma <ref>, where deg(v_i) is the degree of v_i in ^-_i. Since a straightforward implementation of the technique of Lemma <ref> takes O(n) time, and since ∑_i=3^nO(deg(v_i))=O(n), the overall time complexity would be O(n^2).
	
	To achieve O(n) time, the algorithm can be implemented to work in two phases. In the first phase, the exact coordinates of the vertices are not computed, but we only store information on the edges to reconstruct these coordinates in the second phase. More precisely, in the first phase, we consider each vertex v_i according to  and assign to each edge e=(u,v) that is in ^-_i but not in ^-_i-1 two pairs of numbers (s(e,u),l(e,u)) and (s(e,v),l(e,v)). We aim at guaranteeing the following properties for each i=2,3,…,n:
	
	
		
		
  P1 s(e,u)  (resp. s(e,v)) represents the slope of the segment of e incident to u (resp. v) in _i.
		
		
  P2 l(e,u)  (resp. l(e,v)) represents the length of the segment of e incident to u (resp. v) in _i  if at least one of the following two conditions apply: (a) e is on the boundary of _i, or (b) s(e,u) ≠ 0 (resp. s(e,v) ≠ 0), i.e., the segment does not use the horizontal slope.
	
	
	
	For each edge e=(u,v) in _2, we set s(e,u)=s(e,v)=0 and l(e,u)=l(e,v)=1. It is immediate to verify that Properties P1–P2 hold. Let v_i, i>2, be the next vertex to be considered. Let u_1,u_2,…,u_q be the neighbors of v_i along _i-1 and assume, by induction, that P1–P2 hold for i-1. Consider any edge e_j=(u_j,v_i), for j=1,…,q. We choose the slopes for the two segments of e_j as explained above and set s(e_j,u_j) and s(e_j,v_i) accordingly (the choice of the slopes can be done in O(1) time). In order to compute l(e_j,u_j) and l(e_j,v_i), it is sufficient to compute the positions of u_1,u_2,…,u_q relative to u_1. This can be done in O(deg(v_i)) time, because, by P1–P2, we know both the slope and the length of each edge segments along _i-1 from u_1 to u_q. We can then calculate, again in O(deg(v_i)) the (relative coordinates of) the intersection points p_1,p_2,…,p_q. Afterwards, we may need to (repeatedly) apply Lemma <ref>. Note that the application of this lemma does not modify the slope of any edge segment, and thus it preserves Property P1 for all the edges of _i-1. Instead, it changes the length of some horizontal segments. However, all the involved horizontal segments do not belong to _i. Finally, in order to set l(e_j,u_j) and l(e_j,v_i),  it suffices to know the values of λ used in all the applications of Lemma <ref>, which can be computed by only looking at the intersection points p_1,p_2,…,p_q. It follows that P1–P2 hold. 
	
	Once v_n has been considered, we have information on all the edges of _n=. In particular, by P1–P2, we know the slope and the length in  of all the edges that do not contain any horizontal segment. These edges form a tree[In fact, this tree is one of the three trees obtained by a Schnyder decomposition <cit.>.] rooted at v_n spanning the graph obtained removing v_L and v_R from . To see this, observe that, for j=1,2,…,n-1, each vertex v_j  has been connected exactly once to a vertex v_z, with j < z, with an edge that does not contain any horizontal segment, as otherwise v_j would belong to the outer face of . Hence, v_z is the (only) parent of v_j in the spanning tree. Furthermore, v_n is incident to at least one of these edges since it has degree at least three and exactly two of its edges contain a horizontal segment. Therefore, an assignment of valid coordinates to the vertices of G can be obtained through a pre-order visit of this spanning tree (recall that for all the edges of the spanning tree we know the slope and length of its two segments). Finally, all edges that contain a horizontal segment (including those that are incident to v_L and v_R) can be drawn as we know the slopes of both segments and the y-coordinate of the bend point.






	Every bitonic st-graph with maximum vertex degree Δ≥ 2 has 1-bend upward planar slope number at most Δ, which is worst-case optimal.


	Every bitonic st-graph has 1-bend upward planar slope number at most Δ (Theorem <ref>). Also, for every Δ≥ 2 there is a bitonic st-graph (shown in Fig. <ref>) that requires at least Δ slopes in any 1-bend upward planar drawing <cit.>.




	Every planar st-graph with maximum vertex degree 3 has 1-bend upward planar slope number at most 3.


	Let G be a planar st-graph with maximum vertex degree 3. By Theorem <ref>, if G has a bitonic st-ordering then the statement follows. If G does not contain any forbidden configuration, then it is bitonic (see Section <ref>). Otherwise, recall that a forbidden configuration consists of at least three outgoing edges incident to the same vertex. Thus, G contains exactly one forbidden configuration, which involves its source s and the edge (s,t). We can remove this forbidden configuration by mirroring the embedding of the subgraph obtained removing (s,t) from G (see Fig. <ref> for an illustration).




§ MISSING PROOFS OF SECTION <REF>




	Let G=(V,E) be an n-vertex planar st-graph that is not bitonic. Let G_b=(V_b,E_b) be an N-vertex bitonic subdivision of G, with a bitonic st-ordering ={v_1,v_2,…,v_N}. There exists a planar st-graph G'=(V',E') with an st-ordering ={v_L,v_R,v_1,v_2,…,v_N} such that:
	
	[(i)]
		
  * V'=V_b∪{v_L,v_R}; 
	 	
	 	
  * E_b ⊂ E' and (v_L,v_R) ∈ E'; 
	 	
	 	
  * v_L and v_R are on the boundary of the outer face of G'; 
	 	
	 	
  * Every vertex of G_b with less than two predecessors in  has exactly two predecessors in .
	 	
	 	
  * There is no vertex in G' such that its leftmost or its rightmost incoming edge is an upper stub. 
	 	
	
	
	Also, G' and  are computed in O(n) time.


We construct G' together with its embedding by adding a vertex per step according to . We start with the 3-cycle whose edges are (v_L,v_R), (v_L,v_1), and (v_R,v_1) embedded so that, starting from the outer face, the edge (v_R,v_1) is the first edge in the clockwise circular order of the edges around v. Let G'_i be the plane digraph induced by {v_L,v_R,v_1,…,v_i}. The neighbors of v_i that are in G'_i-1 all belong to the boundary of the outer face (because  is an st-ordering of G_b). Thus v_i can be planarly connected to its neighbors in G'_i-1. In order to guarantee properties (<ref>) and (<ref>) we may add dummy edges connecting v_i to some vertex of the outer face of G'_i-1 that is not adjacent to v_i in G_b. 

Suppose first that v_i has only one predecessor u in . We claim that all the edges connecting u to vertices that are after v_i in  appear consecutively either in clockwise or in counterclockwise order around u starting from (u,v_i) in the embedding of G_b. If this was not the case, then there would be two vertices v_j and v_h, with i < j and i < h, such that v_j precedes v_i and v_h follows v_i in the circular order around u. But this would imply that v_j,v_i,v_k form a forbidden configuration for G_b, which would contradict the fact that G_b is bitonic. If all these edges appear after v_i in clockwise (resp. counterclockwise) order, then we can add the edge (v_i,w), where w is the vertex preceding (resp. following) u when walking clockwise along the boundary of G'_i-1 (see, for example, Fig. <ref>).     




Suppose now that v_i has more than one predecessor in , but its leftmost (resp. rightmost) incoming edge (u,v_i) is an upper stub. This means that u is a dummy vertex and therefore it has no successor in ' other than v_i. Then we can add the edge (v_i,w), where w is the vertex preceding (resp. following) u when walking clockwise along the boundary of G'_i-1 (see, for example, Fig. <ref>). Properties (i), (ii), and (iii) immediately follow from our construction, while (iv) and (v) are guaranteed by the dummy edges that we insert as explained above. Since G' has O(n) vertices and edges, the above procedure can be implemented to run in O(n) time.






	Let  be any set of Δ+1 slopes including the horizontal slope and let G be an n-vertex upward planar graph with maximum vertex degree Δ≥ 2. Graph G has a 2-bend upward planar drawing using only slopes in .


Since G is upward planar, it is possible to augment G with dummy edges to a planar st-graph G_st with maximum vertex degree Δ_st (see, e.g., <cit.>). If we apply the algorithm of Theorem <ref> to G_st we obtain a 2-bend upward planar drawing using any set of Δ_st slopes including the horizontal one. However, it is not immediate to augment G so that Δ_st≤Δ+1.  On the other hand, the algorithm can be applied so to draw the dummy edges of G_st using dummy slopes. In this case we should take into account the fact that a vertex v that is a source (resp. a sink) in G and not in G_st may have Δ outgoing (resp. incoming) real edges. To cope with this issue it suffices to use any set of Δ+1 real slopes that includes the horizontal one.




