Fabrizio Frati
email: frati@dia.uniroma3.it.

Lower Bounds on the Area Requirements of Series-Parallel Graphs

Keywords: planar graphs, series-parallel graphs, area requirements, graph drawing, straight-line drawings

We show that there exist series-parallel graphs requiring Ω(n2 √ log n ) area in any straight-line or poly-line grid drawing. Such a result is achieved in two steps. First, we show that, in any straight-line or poly-line drawing of K2,n, one side of the bounding box has length Ω(n), thus answering two questions posed by Biedl et al. Second, we show a family of series-parallel graphs requiring Ω(2 √ log n ) width and Ω(2 √ log n ) height in any straight-line or poly-line grid drawing. Combining the two results, the Ω(n2 √ log n ) area lower bound is achieved.

Introduction

A planar graph is a graph that can be drawn in the plane so that no two edges intersect, except, possibly, at their common endpoints. Determining asymptotic bounds for the area requirements of straight-line and poly-line drawings of planar graphs is one of the classical topics in the Graph Drawing literature. Groundbreaking works at the beginning of the nineties by de Fraysseix et al. [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF] and by Schnyder [START_REF] Schnyder | Embedding planar graphs on the grid[END_REF] have shown that every n-vertex planar graph admits a planar straight-line drawing on an O(n) × O(n) grid. Such a bound is worst-case optimal, even for poly-line drawings [START_REF] Dolev | Planar embeddings of planar graphs[END_REF][START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF]. Hence, it is natural to search for interesting sub-classes of planar graphs admitting sub-quadratic area drawings.

It turns out that several important sub-classes of planar graphs contain graphs requiring quadratic area in any grid drawing.

• Every four-connected plane graph whose outer face has at least four vertices admits a straight-line drawing in n 2 × n 2 -1 area, as shown by Miura et al. in [START_REF] Miura | Grid drawings of 4-connected plane graphs[END_REF], improving upon previous results by He [START_REF] He | Grid embedding of 4-connected plane graphs[END_REF]. Miura et al. also observe that such a bound is tight, as shown by the graph in Fig. 1 (a). • Every bipartite plane graph admits a straight-line drawing in n 2 × n 2 -1 area, as shown by Biedl and Brandenburg in [START_REF] Biedl | Drawing planar bipartite graphs with small area[END_REF]. The upper bound of Biedl and Brandenburg is tight, since bipartite plane graphs exist, very similar to the one shown by Miura et al. [START_REF] Miura | Grid drawings of 4-connected plane graphs[END_REF], requiring n 2 × n 2 -1 area in any poly-line/straight-line drawing. • Planar graphs of maximum degree three exist requiring quadratic area in any poly-line/straight-line grid drawing, as shown in Fig. 1 (b).

• Planar graphs with outerplanarity two exist requiring quadratic area in any poly-line/straight-line grid drawing, as shown by the graph in Fig. 1 (c), that has been presented by Biedl in [START_REF] Biedl | Small poly-line drawings of series-parallel graphs[END_REF].

Planar graphs are the graphs excluding K 5 and K 3,3 as minors [START_REF] Wagner | Uber eine eigenschaft der ebenen komplexe[END_REF]. Which are the classes of graphs excluding graphs smaller than K 5 and K 3,3 as minors? The answer to the previous question is a list of some of the most studied sub-classes of planar graphs. In fact, trees are the graphs excluding K 3 as a minor, outerplanar graphs are the graphs excluding K 4 and K 2,3 as minors, and series-parallel graphs are the graphs excluding K 4 as a minor. Such graph classes, apart from having nice characterizations in terms of excluded minors, apart from having nice alternative characterizations (a tree is a connected acyclic graph, an outerplanar graph is a graph that admits a planar embedding in which all the vertices are incident to the same face, and a series-parallel graph is a graph that can be inductively defined by series and parallel compositions of smaller series-parallel graphs), and apart from being of real interest for applications, do admit grid drawings in sub-quadratic area.

• Concerning trees, a slight modification of the h-v drawing algorithm by Crescenzi et al. [START_REF] Crescenzi | A note on optimal area algorithms for upward drawings of binary trees[END_REF] constructs drawings in O(n log n) area. Optimal O(n) area bounds are known if the degree of the tree is bounded, as proved by Garg et al. for poly-line drawings [START_REF] Garg | Planar upward tree drawings with optimal area[END_REF] and by Garg and Rusu for straight-line drawings [START_REF] Garg | Straight-line drawings of general trees with linear area and arbitrary aspect ratio[END_REF].

• Concerning outerplanar graphs, Biedl [START_REF] Biedl | Drawing outer-planar graphs in O(n log n) area[END_REF] has shown how to construct poly-line drawings in O(n log n) area; Di Battista and the author [START_REF] Battista | Small area drawings of outerplanar graphs[END_REF] presented an algorithm for obtaining straightline drawings in O(n 1.48 ) area; the author [START_REF] Frati | Straight-line drawings of outerplanar graphs in O(dn log n) area[END_REF] exhibited an algorithm for constructing straightline drawings in O(dn log n) area, where d is the degree of the graph. Both for outerplanar graphs and for trees, no super-linear area lower bounds are known, neither in the case of straight-line drawings nor in the one of poly-line drawings.

In this paper we deal with series-parallel graphs, a class of planar graphs that has been widely investigated in Graph Theory and Graph Drawing (see, e.g., [VTL82, Epp92, BCD + 94, Di 03, DDLW06]).

The main known result on the construction of small-area grid drawings of series-parallel graphs is that every series-parallel graph admits a poly-line drawing in O(n 3/2 ) area. Such a bound was proved by Biedl in [START_REF] Biedl | Small poly-line drawings of series-parallel graphs[END_REF][START_REF] Biedl | On small drawings of series-parallel graphs and other subclasses of planar graphs[END_REF]; in these papers, the author provides a nice inductive construction of visibility representations of series-parallel graphs and shows how such representations can be turned into poly-line drawings with asymptotically the same area.

While poly-line drawings can be realized in O(n 3/2 ) area, no sub-quadratic area upper bound is known in the case of straight-line drawings. The best known quadratic upper bound for straight-line drawings is provided in [START_REF] Zhou | Small grid drawings of planar graphs with balanced bipartition[END_REF]. In [START_REF] Biedl | Small poly-line drawings of series-parallel graphs[END_REF], Biedl also proved an Ω( n log n log log n ) area lower bound for straight-line drawings of series-parallel graphs.

The Ω( n log n log log n ) area lower bound for straight-line drawings of series-parallel graphs is a direct consequence of the results in [START_REF] Biedl | Drawing K2,n: A lower bound[END_REF], where Biedl, Chan, and López-Ortiz, settling in the positive a conjecture of Felsner et al. [START_REF] Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF], proved that no linear-area straight-line drawing of K 2,n can achieve constant aspect ratio. Observe that a drawing of the complete bipartite graph K 2,n can be thought of as a drawing of n paths that start and end at the same two vertices, in the following denoted by a and b, and that do not share any other vertex. In the following we will refer such paths as the paths of K 2,n . Fig. 2 shows a straight-line drawing of K 2,n with linear area and linear aspect ratio. More precisely, Biedl, Chan, and López-Ortiz proved the following:

Theorem 1 (Biedl et al. [START_REF] Biedl | Drawing K2,n: A lower bound[END_REF]) Every planar straight-line grid drawing of K 2,n on a W × H grid with W ≥ H satisfies W log H ∈ Ω(n).

Corollary 1 (Biedl et al. [START_REF] Biedl | Drawing K2,n: A lower bound[END_REF]) Every planar straight-line grid drawing of K 2,n on a W × H grid satisfies max{W, H} ∈ Ω(n/ log n).

Biedl et al. ask whether the log H factor in Theorem 1 can be eliminated and whether the same lower bound holds even in the case of poly-line drawings.

In this paper we answer both the questions in the affirmative. Namely, we prove the following:

Theorem 2 Every planar straight-line or poly-line grid drawing of K 2,n on a W × H grid satisfies max{W, H} ∈ Ω(n).

Such a result is achieved by first exhibiting a very simple "optimal" drawing algorithm for K 2,n . That is, if there exists a drawing of K 2,n inside an arbitrary convex polygon P in which a and b are placed at two specified vertices of P , then our algorithm constructs one such drawing. Second, we study the drawings constructed by the mentioned algorithm inside a rectangle. Such a study reveals a surprisingly regular behavior of the drawing of the paths of K 2,n ; we argue that such a behavior has a strong relationship with the generation of relatively prime numbers as expressed in the Stern-Brocot tree. On the base of such a relationship, we derive some arithmetical properties of the lines passing through infinite grid points in the plane, that might be interesting by their own, and we achieve the claimed lower bound.

As a consequence of Theorem 2, an Ω(n log n) lower bound on the area requirements of poly-line and straight-line drawings of series-parallel graphs can be obtained. Namely, consider an O(n)-node seriesparallel graph containing K 2,n and an n-node complete ternary tree as subgraphs. Since any poly-line or straight-line drawing of an n-node complete ternary tree requires Ω(log n) width and Ω(log n) height (see [START_REF] Felsner | Straight-line drawings on restricted integer grids in two and three dimensions[END_REF][START_REF] Suderman | Pathwidth and layered drawings of trees[END_REF]), and since the width or the height of any such a drawing has Ω(n) length (by Theorem 2), the lower bound follows. However, we can achieve a better lower bound by means of the following:

Theorem 3 There exist series-parallel graphs requiring Ω(2 √ log n ) width and Ω(2 √ log n ) height in any straight-line or poly-line grid drawing.

Such a result is achieved by carefully constructing a graph out of several copies of K 2,n and by then strongly exploiting Theorem 2 and some further geometric considerations. Theorem 3, together with Theorem 2, immediately implies the following main result:

Theorem 4 There exist series-parallel graphs requiring Ω(n2 √ log n ) area in any straight-line or polyline grid drawing.

We remark that the function 2 √ log n is greater than any polylogarithmic function of n and smaller than any polynomial function of n; we further remark that no super-linear area lower bound was previously known for poly-line drawings of series-parallel graphs and that Ω( n log n log log n ) was the best known area lower bound for straight-line drawings of series-parallel graphs [START_REF] Biedl | Small poly-line drawings of series-parallel graphs[END_REF].

The rest of the paper is organized as follows. In Section 2 we give some preliminaries; in Section 3 we give some geometric lemmata; in Section 4 we prove Theorem 2; in Section 5 we prove Theorem 3; finally, in Section 6 we conclude and suggest some open problems.

Preliminaries

A grid drawing of a graph is a mapping of each vertex to a distinct point of the plane with integer coordinates and of each edge to a Jordan curve between the endpoints of the edge. A planar drawing is such that no two edges intersect except, possibly, at common endpoints. In the following we always refer to planar grid drawings. A straight-line drawing is such that all edges are rectilinear segments. A poly-line drawing is such that the edges are sequences of rectilinear segments. In a poly-line drawing a bend is a point in which an edge changes its slope, i.e., a point common to two consecutive segments in the sequence of segments representing the edge. In a grid drawing bends have integer coordinates. A polygonal path is a poly-line grid drawing of a path.

The bounding box of a drawing Γ is the smallest rectangle with sides parallel to the axes that covers Γ completely. The height (width) of Γ is the height (resp. width) of its bounding box. The area of Γ is the height of Γ times its width. The aspect ratio of Γ is the ratio between the maximum and minimum of its height and width.

Throughout the paper, a grid line is any line passing through an infinite number of grid points. Two grid lines are consecutive if they are parallel and no grid point is contained in the open strip delimited by

(0,1) (1,1) (1,0) (2,1) (1,2) (1,3) (2,3) (3,2) (3,1) (1,4) (2,5) (3,4) (3,5) (4,3) (5,3) (5,2) (4,1)
Fig. 3: The Stern-Brocot tree.

the two lines. We denote by pq the segment between two points p and q. We also denote by a 0 a 1 . . . a k the polygonal line composed of segments a 0 a 1 , a 1 a 2 , . . . , a k-1 a k .

Let p 1 = (x 1 , y 1 ) and p 2 = (x 2 , y 2 ) be ordered pairs of real numbers (such pairs might represent grid points or vectors, for example) and let k be a constant. Throughout the paper, we write kp 1 to denote the pair (kx 1 , ky 1 ), we write p 1 + p 2 to denote the pair (x 1 + x 2 , y 1 + y 2 ), and we write p 1p 2 to denote the pair (x 1x 2 , y 1y 2 ). We denote by v • a the scalar product between a vector v = (v x , v y ) and a point a = (a x , a y ) in the plane, that is, v

• a = v x a x + v y a y .
The Stern-Brocot tree [START_REF] Stern | Ueber eine zahlentheoretische funktion[END_REF][START_REF] Brocot | Calcul des rouages par approximation, nouvelle methode[END_REF] is an infinite tree whose nodes are in bijective mapping with the irreducible positive rational numbers, or equivalently, in bijective mapping with the ordered pairs of relatively prime integers. See Fig. 3.

The Stern-Brocot tree has two nodes (0, 1) and (1, 0) which are both connected to the same node (1, 1). Nodes (0, 1) and (1, 0) are the left parent and the right parent of (1, 1), respectively. Further, 1 0 and 0 1 are the left generating fraction and the right generating fraction of 1 1 , respectively. An ordered binary tree is then rooted at (1, 1) as follows. Consider a node (x, y) of the tree. Such a node has two children. The left child of (x, y) is the node (x, y) + (x , y ), where (x , y ) is the ancestor of (x, y) that is closer to (x, y) (in terms of graph-theoretic distance on the tree) and that has (x, y) in its right subtree. Then, y

x and y

x are the left generating fraction and the right generating fraction of y+y x+x , respectively. Analogously, the right child of (x, y) is the node (x, y) + (x , y ), where (x , y ) is the ancestor of (x, y) that is closer to (x, y) and that has (x, y) in its left subtree. Then, y

x and y x are the left generating fraction and the right generating fraction of y+y x+x , respectively. The following properties of the Stern-Brocot tree are well-known and easy to observe: Property 1 Let (x, y) be a node of the Stern-Brocot tree and let y

x and y x be the left and right generating fractions of y

x . Then, the subtree of the Stern-Brocot tree rooted at the left child of (x, y) contains all and only the pairs of relatively prime integers (z, w) such that y x < w z < y x and the subtree of the Stern-Brocot tree rooted at the right child of (x, y) contains all and only the pairs of relatively prime integers (z, w) such that y x < w z < y x . Property 2 Let (x, y) be a node of the Stern-Brocot tree. Then every node (x , y ) that is a descendant of (x, y) is such that x ≥ x and y ≥ y and either x = x or y = y (or both). ordered in this way from left to right and three vertical lines are associated with these nodes. When a node (x, y) is drawn, it is placed in the strip delimited by the vertical lines associated with its left and right generating fractions, and a vertical line is associated with (x, y). In such a visualization, each node of the tree is "close" to its generating fractions and nodes (x, y) are ordered from left to right by decreasing value of y x .

It is useful to visualize the

Geometric Lemmata

In this section we show some lemmata that will be used to prove Theorems 2 and 3. We first deal with the geometry of K 2,n and then with the relationships between relatively prime numbers and grid lines in the plane. Recall that K 2,n can be considered a collection of n paths (the paths of K 2,n ) that connect two vertices a and b and that do not share any other vertex.

Lemmata on the Geometry of K 2,n

Lemma 1 Consider any poly-line grid drawing of K 2,n , any path π of K 2,n , and any vector v = (v 1 , v 2 ).

There exists a grid point p ∈ π such that v • p ≥ v • p , for any point p ∈ π. Proof: Suppose, for a contradiction, that three paths π 1 , π 2 , and π 3 of K 2,n with the above properties exist. Paths π 1 and π 2 form a cycle C. Line l is external to C and separates a from b in the exterior of C (see Fig. Let P be any convex polygon in the plane with vertices having integer coordinates. Let I be the set of grid points in the interior or on the border of P . Let a and b be two distinct vertices of P . Let π * 1 and π * 2 be the drawings of the two paths that connect a and b and that compose P . At least one out of π * 1 and π * 2 , say π * 1 , is different from segment ab. Let M be the maximum number of paths connecting a and b that can be drawn as non-crossing polygonal paths inside or on the border of P .

Proof: If v • a ≥ v • p or v • b ≥ v • p ,
Lemma 3 There exist M non-crossing polygonal paths connecting a and b such that:

• Each path is inside or on the border of P ; and

• one of such paths is π * 1 .

Proof: Consider any drawing Γ composed of M non-crossing polygonal paths connecting a and b and contained inside or on the border of P . If a path of Γ is π * 1 , there is nothing to prove. Otherwise, observe that no two distinct paths π i and π j pass through points of π * 1 , as otherwise π i and π j cross. Hence, Γ has at most one path π passing through points of π * 1 . Remove π from Γ, if π exists, and draw a path in Γ as π * 1 . Since no path different from π passes through a point of π * 1 , the resulting drawing is planar, hence proving the lemma.

2

Lemma 4 There exist M non-crossing polygonal paths connecting a and b such that:

• Each path is inside or on the border of P ; and

• one of such paths is segment ab.

Proof: We prove the claim by induction on M . If M = 1, then drawing a path as segment ab proves the claim. Suppose M ≥ 2. By Lemma 3, there exists a drawing Γ composed of M non-crossing polygonal paths connecting a and b such that each path is inside or on the border of P and one of such paths, say π, is π * 1 . Remove π from Γ and all the grid points π passes through, except for a and b, from I. Consider the convex polygon P that is the convex hull of the resulting grid point-set I . The vertices of P have integer coordinates. Further, P is such that M -1 paths can be drawn as non-crossing polygonal paths connecting a and b inside or on the border of P . In fact Γ is a drawing having such a property. Hence, the inductive hypothesis applies and M -1 polygonal paths exist so that each path is inside or on the border of P and so that one of the paths is segment ab. Considering such M -1 paths together with the drawing of π as π * 1 proves the lemma. 2

Now assume that a and b are consecutive vertices of P (see Fig. 5). Let I be the set of grid points in the interior or on the border of P . As before, let π * 1 and π * 2 be the drawings of the two paths that connect a b Fig. 5: Drawing the maximum number of paths in a convex polygon with vertices having integer coordinates. Black circles are vertices of P and white circles are grid points inside or on the border of P .

a and b and that compose P , where π * 1 is different from segment ab. Let also M be the maximum number of paths connecting a and b that can be drawn as non-crossing polygonal paths inside or on the border of P .

We iteratively draw some paths π 1 , π 2 , • • • , π N connecting a and b inside or on the border of P as follows. Path π i is drawn when the current convex grid polygon is P i containing in its interior or on its border a set I i of grid points. At the first step P 1 = P and I 1 = I. If P i does not coincide with segment ab, draw path π i as the polygonal path that connects a and b, that lies on P i , and that is different from segment ab. Remove the grid points that lie on P i , except for a and b, from I i , obtaining a new set of grid points I i+1 . Then, P i+1 is the convex hull of I i+1 . If P i coincides with segment ab, draw path π i = π N as segment ab. We observe the following: Lemma 5 Paths π 1 , π 2 , • • • , π N are drawn as non-crossing polygonal paths inside or on the border of P . Further, N = M .

Proof: The first part of the statement is trivial. We prove that N = M by induction on M . If M = 2, then the claim trivially holds, since π 1 is drawn as π * 1 and π 2 as ab. Suppose that M ≥ 3. By Lemma 3, there exists a drawing Γ composed of M non-crossing polygonal paths connecting a and b such that each path is inside or on the border of P and one of such paths, say π 1 , is π * 1 . Remove π 1 from Γ and all the grid points π 1 passes through from I. Consider the convex polygon P that is the convex hull of the resulting grid point-set I . Clearly, the vertices of P have integer coordinates. Further, P is such that M -1 non-crossing polygonal paths connecting a and b exist such that each path is inside or on the border of P . In fact Γ is a drawing having such a property. Hence, the inductive hypothesis applies and the drawing algorithm described before the statement of the lemma draws M -1 paths as non-crossing polygonal paths inside or on the border of P . Considering such paths together with the drawing of π 1 as π * 1 proves the lemma. 2

A Lemma on the Arithmetics of Consecutive Grid Lines

The aim of this section is to prove the following useful lemma.

Lemma 6 Let l 1 be a grid line with slope y x , where x, y > 0 and (x, y) is a pair of relatively prime numbers. Let y

x and y x be the left and right generating fractions of y x . Consider any grid point (p x , p y )

l 1 l 2 p 0 ≡ (0, 0) p 1 ≡ (x, y) q ≡ (q x , q y ) p 2 ≡ (x ′′ , y ′′ ) p 3 ≡ (x + x ′′ , y + y ′′ ) t ≡ (t x , t y ) ( q x
z , q y z )

Fig. 6: Illustration for the proof of Lemma 6.

of l 1 . Let l 2 (l 3 ) be the grid line passing through (p x , p y ) + (x , y ) and through (p x , p y ) -(x , y ) (resp. through (p x , p y ) -(x , y ) and through (p x , p y ) + (x , y )). Then, l 1 and l 2 (resp. l 1 and l 3 ) are consecutive grid lines.

Proof: Refer to Fig. 6. We prove the statement for l 1 and l 2 , the proof for l 1 and l 3 being analogous. Suppose, for a contradiction, that l 1 and l 2 are not consecutive. First, observe that l 1 and l 2 are parallel, as l 2 has slope py+y -py+y px+x -px+x = y +y x +x = y x , where the last equality holds by the definition of generating fractions.

We can assume, without loss of generality up to a simultaneous translation of l 1 and l 2 , that l 1 passes through point p 0 ≡ (0, 0). Denote p 1 ≡ (x, y). Observe that a simultaneous translation of l 1 and l 2 does not alter whether the open strip delimited by the two lines contains a grid point, as the same translation moves any grid point between the two lines before the translation to a grid point between the two lines after the translation.

Suppose that a point q ≡ (q x , q y ) exists between l 1 and l 2 . Then, we can assume that q is in the parallelogram P whose vertices are p 0 , p 1 , p 2 ≡ (x , y ), and p 3 ≡ p 1 + p 2 , or on its border. Namely, if a grid point t ≡ (t x , t y ) is between l 1 and l 2 , then every grid point t ≡ (t x + mx, t y + my) is between l 1 and l 2 , for all m ∈ Z. Suppose that q is inside the closed triangle (p 0 , p 1 , p 2 ), the case in which it is inside (p 1 , p 2 , p 3 ) being analogous.

We can assume that (q x , q y ) and (xq x , yq y ) are two pairs of relatively prime numbers. Namely, suppose that q x and q y have a common divisor, say z. Then, ( qx z , qy z ) is a grid point. Further, such a point is on the border of triangle (p 0 , p 1 , q), actually on p 0 q. Then, point q ≡ ( qx z , qy z ) can be considered instead of q ≡ (q x , q y ). Analogously, if xq x and yq y have a common divisor, say z, then point q ≡ (x-x-qx z , y -y-qy z ) can be considered instead of q ≡ (q x , q y ). Observe that, whenever the currently considered point q ≡ (q x , q y ) is replaced by a new grid point q ≡ ( qx z , qy z ) or q ≡ (x -x-qx z , y -y-qy z ), the sum of the number of grid points on the border and of the number of grid points in the interior of triangle (p 0 , p 1 , q) decreases. Hence, eventually after a certain number of replacements, the coordinates q x and q y of q (and simultaneously xq x and yq y ) are relatively prime numbers.

l a,b d v d h a b v b h a h b v a c d
Observe that q does not lie on p 0 p 1 as it has to lie in the open strip delimited by l 1 and l 2 . Further, it does not lie on p 0 p 2 (on p 1 p 2 ) as otherwise x and y (resp. x and y ) would not be relatively prime numbers.

Now consider the slope qy qx . As q is inside triangle (p 0 , p 1 , p 2 ), it follows that y x < qy qx < y x and that y x < y-qy

x-qx < y x . By Property 1, the relatively prime pairs (q x , q y ) and (xq x , yq y ) are contained in the subtree of the Stern-Brocot tree rooted at (x, y). By Property 2, q x ≥ x and q y ≥ y hold; further, xq x ≥ x and yq y ≥ y hold; hence, q x + xq x ≥ 2x and q y + yq y ≥ 2y hold. Such contradictions prove the lemma. 2

Proof of Theorem 2

By definition, a straight-line drawing is also a poly-line drawing. Hence, it suffices to prove Theorem 2 for poly-line drawings.

Consider any poly-line grid drawing of K 2,n . Let R be the smallest axis-parallel rectangle enclosing a and b (see Fig. 7). Let l a,b be the line through a and b. Suppose, without loss of generality, that y(a) ≤ y(b). Suppose also that x(a) < x(b), the case in which x(a) ≥ x(b) being analogous. Let c and d be the upper left corner and the lower right corner of R, respectively. Let h a and v a be the horizontal and vertical lines through a, respectively. Analogously, let h b and v b be the horizontal and vertical lines through b, respectively. Let d h and d v be the horizontal and vertical distance between a and b, respectively. The width W and the height H of the drawing are such that W ≥ d h and H ≥ d v .

For any line l, denote by H + (l) (resp. by H -(l)) the closed half-plane delimited by l and containing the normal vector of l increasing in the y-direction (resp. decreasing in the y-direction). If l is a vertical line, then H + (l) (resp. H -(l)) denotes the closed half-plane delimited by l and containing the normal vector of l increasing in the x-direction (resp. decreasing in the x-direction). For any non-horizontal line l, we say that a point p is to the right of l (to the left of l) if p is in the open half-plane delimited by l and containing the normal vector of l increasing in the x-direction (resp. decreasing in the x-direction).

Consider the half-plane H + (h b ). By Lemma 1 with v = (0, 1), for each path π that has non-empty intersection with H + (h b ), there exists a grid point p ∈ π whose y-coordinate is maximum among the a c b

Fig. 8: Paths π1, π2, • • • , πM 1 in Π.
points of π. Clearly, p belongs to H + (h b ). Hence, p belongs to a horizontal grid line l that does not intersect or contain the open segment ab. By Lemma 2, at most two paths of K 2,n have their points with greatest y-coordinate belonging to l. It follows that, if a linear number of paths of K 2,n has nonempty intersection with H + (h b ), then their points with greatest y-coordinate belong to a linear number of distinct horizontal grid lines and hence H ∈ Ω(n). Similar arguments show that, if a linear number of paths of K 2,n have non-empty intersection with

H -(h a ), H + (v b ), or H -(v a ), then H ∈ Ω(n), W ∈ Ω(n), or W ∈ Ω(n), respectively.
If there exists no linear number of paths of K 2,n having non-empty intersection with

H + (h b ), H -(h a ), H + (v b ), or H -(v a )
, then a linear number of paths of K 2,n is completely inside or on the border of R. We show that this implies that max{d h , d v } ∈ Ω(n), and hence that max{W, H} ∈ Ω(n).

Let M be the maximum number of paths of K 2,n that can be drawn inside or on the border of R. By Lemma 4, there exists a drawing of M paths connecting a and b, and completely lying inside or on the border of R, such that one of the paths is drawn as segment ab. Since M ∈ Ω(n), then either a linear number of paths of K 2,n is contained inside or on the border of the triangle T 1 having a, b, and c as vertices, or a linear number of paths of K 2,n is contained inside or on the border of the triangle T 2 having a, b, and d as vertices. Suppose that a linear number of paths of K 2,n is contained inside or on the border of T 1 , the other case being symmetric.

Let M 1 ∈ Ω(n) be the maximum number of paths of K 2,n that can be drawn inside T 1 and let I 1 be the set of grid points inside or on the border of T 1 . By Lemma 5, a sequence of M 1 non-crossing polygonal paths Π = (π 1 , π 2 , • • • , π M1 ) connecting a and b and completely inside or on the border of T 1 can be drawn by repeating the following two operations, for 1 ≤ i < M 1 : (1) consider the current convex grid polygon P i (when i = 1 then P 1 = T 1 ); let I i be the set of grid points inside or on the border of P i ; draw path π i as the part of P i that connects a and b, and that is different from segment ab; (2) delete from I i the grid points π i passes through, obtaining a set of grid points I i+1 . Convex polygon P i+1 is the convex hull of I i+1 . Path π M1 is drawn as segment ab. See Fig. 8.

In order to prove that

M 1 ∈ Ω(n) implies max{d h , d v } ∈ Ω(n), we study paths π 1 , π 2 , • • • , π M1
and prove that they have a very regular behavior that is strongly related to the generation of relatively prime numbers as in the Stern-Brocot tree. In the following, we first sketch a description of the geometry of paths π 1 , π 2 , • • • , π M1 , we then detail such a description, we later prove the geometric claims to be correct, and we finally prove that max{d h , d v } ∈ Ω(n). In the reminder of the section we assume that d h , d v > 3. Clearly, if one of d h and d v is O(1), then the other one must be Ω(M 1 ), and there is nothing to prove.

Sketch of the geometry of paths

π 1 , π 2 , • • • , π M 1
First, we observe that each path in Π is composed of two or three segments, i.e., each path has one or two bends. A sequence of paths that are consecutive in Π and that are each composed of three segments is such that all the "second segments" of the paths have the same slope.

In a sequence of paths such that the second segments of the paths have the same slope, all the bends lie on two lines, having slopes one greater and one smaller than dv d h , the slope of segment ab. Moreover, the two lines on which such bends lie have slope y1 x1 and y2 x2 , where (x 1 , y 1 ) and (x 2 , y 2 ) are two pairs of relatively prime numbers; the slope of the second segments of the paths that have such bends is y1+y2 x1+x2 , where (x 1 + x 2 , y 1 + y 2 ) is a pair of relatively prime numbers, and y1 x1 and y2 x2 are the generating fractions of y1+y2

x1+x2 .

The more sequences of three-segments paths that are consecutive in Π are considered, the more the slopes of the first, of the second, and of the third segments of the paths approach to the slope of segment ab. Namely, if a sequence of paths is such that their bends lie on two lines with slopes y1 x1 and y2 x2 and their second segments have slope y1+y2 x1+x2 , then the next sequence of paths whose second segments have the same slope is such that the bends of such paths lie on two lines with slopes

, d v } as a function of M 1 , we subdivide Π into disjoint sub-sequences Π 1 , Π 2 , • • • , Π f
and we argue that Π 1 has at most max{d h , d v } paths and that Π i has at most max{d h , d v }/2 i-2 paths, for 2 ≤ i ≤ f ; such bounds lead to the conclusion that, as long as

M 1 ∈ Ω(n), max{d h , d v } ∈ Ω(n).

Details of the geometry of paths π

1 , π 2 , • • • , π M 1
Path π 1 is acb. Let p 1 ≡ c + (1, -1). Consider the following two sequences of grid points. See Fig. 9.a. Sequence S 0,1 is composed of points p 0,1 k ≡ p 1 -(k -1)(0, 1), for 1 ≤ k ≤ i 1 , where i 1 is the largest integer such that point p 1 -(i 1 -1)(0, 1) is contained inside T 1 (recall that T 1 is the triangle having a, b, and c as vertices). Sequence S 1,0 is composed of points p 1,0 k ≡ p 1 + (k -1)(1, 0), for 1 ≤ k ≤ j 1 , where j 1 is the largest integer such that point p 1 + (j 1 -1)(1, 0) is contained inside T 1 . Notice that the points of S 0,1 lie on a line with slope 1 0 = ∞ and the points of S 1,0 lie on a line with slope 0 1 = 0. A sub-sequence Π 1 of Π, starting at π 2 and composed of paths consecutive in Π, "uses" the points in S 0,1 and in S 1,0 , i.e., each path in Π 1 passes through a point in S 0,1 or a point in S 1,0 . Actually, the first paths in Π 1 pass through a point in S 0,1 and a point in S 0,1 . The paths that use the points in S 0,1 and in S 1,0 terminate when a path uses a point in S 0,1 and a point in S 1,0 that are collinear with one of a and b. Observe that when one of S 0,1 and S 1,0 is over, it is always the case that the last drawn path uses a point in S 0,1 and a point in S 1,0 that are collinear with one of a and b.

Then, path π k+1 is the polygonal path ap 0,1

k p 1,0 k b, for k = 1, 2, • • • , k 1 ,
where k 1 is the smallest index greater than 1 such that a, p 0,1 k1 , and p 1,0 k1 are collinear or p 0,1 k1 , p 1,0 k1 , and b are collinear. When one of S 0,1 and S 1,0 is "over", that is, there exist paths passing through all of its points, then a, p 0,1 k1 , and p 1,0 k1 are collinear or p 0,1 k1 , p 1,0 k1 , and b are collinear. Notice that p 0,1 two segments. The second segment of path π k+1 , for k = 2, 3, • • • , k 1 , has slope 1 1 . Observe that 1 0 and 0 1 are the generating fractions of 1 1 . See Fig. 9.b. Then, three cases have to be considered, namely the one in which a, p 0,1 k1 , p 1,0 k1 , and b are all collinear, the one in which a, p 0,1 k1 , and p 1,0 k1 are collinear (and b is not), and the one in which p 0,1 k1 , p 1,0 k1 , and b are collinear (and a is not). In the first case, path π k1+1 coincides with segment ab, hence π k1+1 = π M1 . In the second case (the third case is analogous to the second one), sequence S 0,1 is replaced by a sequence S 1,1 defined as follows. See Fig. 10.a. The points of S 1,1 are the points p 1,1

1 = p 1,0 1 = p 1 , hence π 2 is composed of only p 0,1 1 ≡ p 1,0 1 p 0,1 2 p 0,1 3 p 1,0 j1 p 1,0 2 p 1,0 3 p 0,1 i1 a b (a) p 0,1 1 ≡ p 1,0 1 π k1+1 a b (b)
k ≡ p 1,0 k1+1 -(k -1)(1, 1), for 1 ≤ k ≤ i 2 , where i 2 is the largest integer such that point p 1,0 k1+1 -(i 2 -1)(1, 1
) is contained inside T 1 . Some paths in Π 1 use the points in S 1,1 and the remaining points in S 1,0 . The paths that use the points in S 1,1 and in S 1,0 terminate when a path uses a point in S 1,1 and a point in S 1,0 that are collinear with one of a and b. Observe that when one of S 1,1 and S 1,0 is over, it is always the case that the last drawn path uses a point in S 1,1 and a point in S 1,0 that are collinear with one of a and b.

Then, path π k1+k+1 is the polygonal path ap 1,1 k p 1,0 k1+k b, for k = 1, 2, • • • , k 2 ,
where k 2 is the smallest index such that a, p 1,1 k2 , and p 1,0 k1+k2 are collinear or p 1,1 k2 , p 1,0 k1+k2 , and b are collinear. When one of S 1,1 and S 1,0 is over, then a, p 1,1 k2 , and p 1,0 k1+k2 are collinear or p 1,1 k2 , p 1,0 k1+k2 , and b are collinear. Notice that p 1,1 1 = p 1,0 k1+1 , hence π k1+2 is composed of only two segments. Also, observe that the bends of paths π k1+k+1 , with k = 1, 2, • • • , k 2 , lie on two lines with slope 1 1 = 1 and 0 1 = 0, while the second segments of such paths lie on lines with slope 1+0 1+1 = 1 2 , where 0 1 and 1 1 are the generating fractions of 1 2 . See Again, three cases have to be considered, namely the one in which a, p 1,1 k2 , p 1,0 k1+k2 , and b are all collinear, the one in which a, p 1,1 k2 , and p 1,0 k1+k2 are collinear (and b is not), and the one in which p 1,1 k2 , p 1,0 k1+k2 , and b are collinear (and a is not). In the first case, path π k1+k2+1 coincides with segment ab, hence π k1+k2+1 = π M1 . Otherwise, a, p 1,1 k2 , and p 1,0 k1+k2 are collinear (and b is not), or p 1,1 k2 , p 1,0 k1+k2 , and b are collinear (and a is not). Suppose that a, p 1,1 k2 , and p 1,0 k1+k2 are collinear (and b is not). Then S 1,1 is replaced by a sequence S 2,1 of points lying on a line with slope 1 2 . Namely, such points have coordinate

p 1,0 k1 a b p 1,1 1 ≡ p 1,0 k1+1 p 1,1 2 p 1,1 3 p 1,1 i2 p 1,0 j1 π k1+1 (a) a b p 1,1 1 ≡ p 1,0 k1+1 π k1+2 π k1+k2+1 (b)
p 2,1 k = p 1,0 k1+k2+1 -(k -1)(2, 1), for 1 ≤ k ≤ i 3
, where i 3 is the largest integer such that point p 1,0 k1+k2+1 -(i 3 -1)(2, 1) is internal to T 1 . See Fig. 11.a. Some paths in Π 1 use the points in S 2,1 and the remaining points in S 1,0 , that is, path π k1+k2+k+1 , with 1 ≤ k ≤ k 3 , passes through point p 2,1 k and through point p 1,0 k1+k2+k , where k 3 is the smallest index such that a, p 2,1 k3 , and p 1,0 k1+k2+k3 are collinear or p 2,1 k3 , p 1,0 k1+k2+k3 , and b are collinear. Observe that when one of S 2,1 and S 1,0 is over, it is always the case that the last drawn path uses a point in S 2,1 and a point in S 1,0 that are collinear with one of a and b. Observe also that the bends of paths π k1+k2+k+1 , with k = 1, 2, • • • , k 3 , lie on two lines with slope 1 2 and 0 1 , while the second segments of such paths lie on lines with slope 1+0 2+1 = 1 3 , where 1 2 and 0 1 are the generating fractions of 1 3 . See Fig. 11.b. The above argument iterates till a path is drawn that passes through a, through a point p l,1 k l+1 of the current sequence S l,1 , through a point p 1,0 k1+k2+•••+k l +k l+1 of S 1,0 , and through b in such a way that p l,1 k l+1 , p 1,0 k1+k2+•••+k l +k l+1 , and b are collinear. If sequence S 1,0 is over, that is, all its points have been traversed by paths in Π, then the last drawn path passes through a, through a point p l,1 k l+1 of S l,1 , through the last point p 1,0 k1+k2+•••+k l +k l+1 of S 1,0 , and through b, where p l,1 k l+1 , p 1,0 k1+k2+•••+k l +k l+1 , and b are collinear. Hence, all the paths that come after π 1 in Π 1 pass through distinct points of S 1,0 , till a path is drawn that passes through a, through a point p l,1 k l+1 of S l,1 , through a point p 1,0

p 1,0 k1+k2 a b p 2,1 1 ≡ p 1,0 k1+k2+1 p 2,1 2 p 2,1 3 p 2,1 i3 p 1,0 j1 π k1+k2+1 (a) a b p 2,1 1 ≡ p 1,0 k1+k2+1 π k1+k2+2 π j1+1 = π k1+k2+k3+1 (b)
k1+k2+•••+k l +k l+1
of S 1,0 , and through b in such a way that p l,1 k l+1 , p 1,0 k1+k2+•••+k l +k l+1 , and b are collinear. Thus,

Π 1 = (π 2 , π 3 , • • • , π k1+k2+•••+k l +k l+1 +1
) is the desired sub-sequence Π 1 of Π. Further, there exists an index l ≥ 1 such that: (1) all the points p i,1 j are traversed by paths in Π 1 , for 0 ≤ i ≤ l -1 and 1 ≤ j ≤ k i+1 , and a, p i,1 ki+1 , and p 1,0 k1+k2+•••+ki+1 are collinear, for 0 ≤ i ≤ l -1;

(2) some points of S l,1 are possibly traversed by paths in Π 1 , and p l,1 k l+1 , p 1,0 k1+k2+•••+k l +k l+1 , and b are collinear. In the example in Figs. 9-11, we have l = 2; indeed, all the points p 0,1 j are traversed by paths in Π 1 , for 1 ≤ j ≤ k 1 ; a, p 0,1 k1 , and p 1,0 k1 are collinear; all the points p 1,1 j are traversed by paths in Π 1 , for 1 ≤ j ≤ k 2 ; a, p 1,1 k2 , and p 1,0 k1+k2 are collinear; some points of S 2,1 are traversed by a path in Π 1 ; p 2,1 k3 , p 1,0 k1+k2+k3 , and b are collinear. After drawing path π k1+k2+•••+k l +k l+1 +1 (that passes through a, p l,1 k l+1 , p 1,0 k1+k2+•••+k l +k l+1 , and b in such a way that p l,1 k l+1 , p 1,0 k1+k2+•••+k l +k l+1 , and b are collinear), either a is collinear with p l,1 k l+1 , p 1,0 k1+k2+•••+k l +k l+1 , and b, or not. In the former case, path π k1+k2+•••+k l +k l+1 +1 coincides with segment ab, hence π k1+k2+•••+k l +k l+1 +1 = π M1 . In the latter case, S l,1 still contains points not traversed by any path in Π 1 . Then, sequence S 1,0 is now replaced by a sequence S l+1,1 , whose points lie on a line with slope 0+1 1+l = 1 l+1 passing through the first point of S l,1 that is not traversed by a path in Π 1 , that is, point p l,1 k l+1 +1 . See Fig. 12.a, where there exists exactly one point of S 2,1 that is not traversed by a path in Π 1 . The whole argument is now repeated again. Namely, a sub-sequence Π 2 of Π uses the points in S l,1 not traversed by paths in Π 1 and the points in S l+1,1 , i.e., each path in Π 2 passes through a point in S l,1 or a point in S l+1,1 . Actually, the first paths in Π 2 pass through a point in S l,1 and a point in S l+1,1 .

p 3,1 2 a b p 2,1 k3+1 ≡ p 3,1 1 π j1+1 = π k1+k2+k3+1 p 2,1 k3 p 3,1 3 (a) a b p 2,1 k3+1 ≡ p 3,1 1 (b)
Again, Π 2 is generally found in several steps, where at each step two sequences S x1,y1 and S x2,y2 of grid points are considered, where one between S x1,y1 and S x2,y2 is S l,1 or S l+1,1 (at the first step S x1,y1 = S l,1 and S x2,y2 = S l+1,1 both hold). The points on S x1,y1 (on S x2,y2 ) lie on a line with slope y1 x1 (resp. y2 x2 ), where (x 1 , y 1 ) and (x 2 , y 2 ) are pairs of relatively prime numbers. The second segments of the paths drawn when S x1,y1 and S x2,y2 are considered have slope y1+y2 x1+x2 , where (x 1 + x 2 , y 1 + y 2 ) is a pair of relatively prime numbers, and y1 x1 and y2 x2 are the generating fractions of y1+y2 x1+x2 . At each step, a path eventually passes through two points of S x1,y1 and S x2,y2 collinear with a or with b. Then, one between S x1,y1 and S x2,y2 (depending on whether the last path drawn in the step passes through two points of S x1,y1 and S x2,y2 collinear with a or with b) is replaced by a sequence of points lying on a line with slope y1+y2 x1+x2 , hence starting a new step. After a certain number of steps, both S l,1 and S l+1,1 have been replaced by other sequences of points. When the last path that passes through a point of S l,1 or of S l+1,1 is drawn (that is, when the last path of Π 2 is drawn), it passes through a, through two points in the currently considered sequences S x1,y1 and S x2,y2 , and through b, so that either these four points are collinear, or a and two points in S x1,y1 and S x2,y2 are collinear and b is not, or b and two points in S x1,y1 and S x2,y2 are collinear and a is not. In the first case, the last drawn path is π M1 , that hence coincides with segment ab. In the second and the third case, either S x1,y1 or S x2,y2 is replaced by a sequence S y1+y2,x1+x2 whose grid points lie on a line with slope y1+y2 x1+x2 , depending on whether a and two points in the currently considered sequences S x1,y1 and S x2,y2 are collinear and b is not, or b and two points in the currently considered sequences S x1,y1 and S x2,y2 are collinear and a is not. The whole argument is then repeated again, searching for a sub-sequence Π 3 of Π such that Π 3 uses the points in S x1,y1 and the points in S x1+x2,y1+y2 . Clearly, there exists an index

f such that Π = {π 1 } ∪ Π 1 ∪ Π 2 ∪ • • • Π f ∪ {ab}.
In the example considered in Figs. 9-12, the sequences considered at the first step, when determining Π 2 , are S 2,1 and S 3,1 . The slope of the second segments is 1+1 2+3 = 2 5 , although no path composed of three segments is drawn. Namely, the first path of Π 2 passes through the only point of S 2,1 not traversed by paths in Π 1 . The sequences considered at the second step are S 2+3,1+1 = S 5,2 and S 3,1 . Sequence S 5,2 has only one point p 5,2 1 ≡ p 3,1 2 . The slope of the second segments is 2+1 5+3 = 3 8 , although no path composed of three segments is drawn. Namely, the second path of Π 2 passes through the only point of S 5,2 . The sequences considered at the third step are S 5+3,2+1 = S 8,3 and S 3,1 . Sequence S 8,3 has only one point p 8,3 1 ≡ p 3,1 3 . The slope of the second segments is 3+1 8+3 = 4 11 , although no path composed of three segments is drawn. Namely, the third path of Π 2 passes through the only point of S 8,3 and the last point of S 3,1 (the two points actually coincide). Sequence Π 2 is over, as all the points in S 2,1 and in S 3,1 are traversed by paths in Π 1 or in Π 2 . Further, since S 8,3 and S 3,1 end simultaneously, the only path of Π after Π 2 is segment ab.

Proof of correctness of the geometry of paths π

1 , π 2 , • • • , π M 1
We now prove that paths π 1 , π 2 , • • • , π M1 have the geometry described in Section 4.2.

In order to do that, we describe five possible sets of geometric features (in the following called Conditions 1-5) that can hold after drawing path π i , we show that after drawing path π 2 Condition 4 is satisfied, and we prove that, if after drawing path π i one of Conditions 1-5 is satisfied, then after drawing path π i+1 one of Conditions 1-5 is still satisfied (unless we are in a special case in which we can directly estimate the number of paths that come after π i in Π).

After paths π 1 , π 2 , . . . , π i have been drawn, a grid point is occupied if it has been traversed by a path π j , with j ≤ i, and is free otherwise. After a path π i is drawn, we associate with the next path π i+1 to be drawn two sequences S x1,y1 and S x2,y2 of points, such that the following properties are satisfied:

• Property S1: x 1 and y 1 are relatively prime numbers; x 2 and y 2 are relatively prime numbers;

• Property S2: y1 x1 > dv d h > y2 x2 ;
• Property S3: y1 x1 and y2 x2 are the left and right generating fractions of y1+y2 x1+x2 , respectively; • Property S4: All the points in a (possibly empty) initial sub-sequence of S x1,y1 and all the points in a (possibly empty) initial sub-sequence of S x2,y2 are occupied; all the other points of S x1,y1 and S x2,y2 are free and lie inside polygon π i ∪ ab;

• Property S5: The half-line l(x 1 , y 1 ) starting at the first point p x1,y1 1 of S x1,y1 , having slope y1 x1 , and directed towards decreasing y-coordinates intersects the interior of segment ab in a point a b l(x 2 , y 2 ) l(x 1 , y 1 )

q 1 (π i ) π i q 2 (π i ) l 1,2 (π i )
Fig. 13: After drawing πi, Condition 1 is satisfied. In all the figures of Section 4.3, black dots represent occupied points of Sx 1 ,y 1 and Sx 2 ,y 2 , white dots represent free points of Sx 1 ,y 1 and Sx 2 ,y 2 , and the shaded triangles are T (Sx 1 ,y 1 , a) and T (Sx 2 ,y 2 , b). The slopes of the lines in the figures do not correspond to slopes of grid lines in the plane. This allows us to improve the readability of the drawings.

q(S x1,y1 , ab); the half-line l(x 2 , y 2 ) starting at the first point p x2,y2 1 of S x2,y2 , having slope y2 x2 , and directed towards increasing x-coordinates intersects the interior of segment ab in a point q(S x2,y2 , ab);

• Property S6: There exists no grid point internal to the triangle T (S x1,y1 , a) having p x1,y1 1 , q(S x1,y1 , ab), and a as vertices; there exists no grid point internal to the triangle T (S x2,y2 , b) having p x2,y2 1 , q(S x2,y2 , ab), and b as vertices.

Conditions 1-5 are as follows: Condition 1. Path π i is aq 1 (π i )q 2 (π i )b; q 1 (π i ) and q 2 (π i ) are the last occupied points of S x1,y1 and S x2,y2 , respectively; segment q 1 (π i )q 2 (π i ) has slope y1+y2 x1+x2 ; the line l 1,2 (π i ) through q 1 (π i ) and q 2 (π i ) has a and b to its right; finally, both S x1,y1 and S x2,y2 have free points (see Fig. 13).

Condition 2. Path π i is aq 1 (π i )q 2 (π i )b; q 1 (π i ) and q 2 (π i ) are the last occupied points of S x1,y1 and S x2,y2 , respectively; segment q 1 (π i )q 2 (π i ) has slope y1+y2 x1+x2 ; the line l 1,2 (π i ) through q 1 (π i ) and q 2 (π i ) has a and b to its right; finally, neither S x1,y1 nor S x2,y2 has free points (see Fig. 14). Condition 3. Path π i is aq 1 (π i )b; further, either (i) q 1 (π i ) is the last occupied point of S x1,y1 and all the points of S x2,y2 are free; the first free point of S x1,y1 coincides with the first point of S x2,y2 ; segment q 1 (π i )b has slope y2 x2 ; y1 x1 is a generating fraction of y2 x2 ; the line l 1,2 (π i ) through q 1 (π i ) with slope y1+y2 x1+x2 has a and b to its right (see Fig. 15); or (ii) q 1 (π i ) is the last occupied point of S x2,y2 and all the points of S x1,y1 are free; the first free point of S x2,y2 coincides with the first point of S x1,y1 ; segment aq 1 (π i ) has slope y1 x1 ; y2 x2 is a generating fraction of y1 x1 ; the line l 1,2 (π i ) through q 1 (π i ) with slope y1+y2 x1+x2 has a and b to its right. Condition 4. Path π i is aq 1 (π i )b; q 1 (π i ) is the last occupied point of S x1,y1 and the last occupied point of S x2,y2 ; the line l 1,2 (π i ) through q 1 (π i ) with slope y1+y2 x1+x2 has a and b to its right; both S x1,y1 and S x2,y2 have free points (see Fig. 16).

Condition 5. Path π i is aq 1 (π i )b; q 1 (π i ) is the last occupied point of S x1,y1 and the last occupied point of S x2,y2 ; the line l 1,2 (π i ) through q 1 (π i ) with slope y1+y2 x1+x2 has a and b to its right; neither S x1,y1 nor S x2,y2 has free points (see Fig. 17). a b l(x 2 , y 2 ) l(x 1 , y 1 ) We are now ready to prove the following:

q 1 (π i ) π i q 2 (π i ) l 1,2 (π i )
q 1 (π i ) π i l 1,2 (π i )
Lemma 7 Suppose that after drawing path π i one of Conditions 1-5 is satisfied. Then, after drawing path π i+1 either one of Conditions 1-5 is satisfied or all the free points inside polygon π i+1 ∪ ab lie on a specific grid line.

First we prove that after drawing path π 2 Condition 4 is satisfied. Clearly, such a path is ap 0,1 1 b, where p 0,1 1 = p 1,0 1 ≡ c + (1, -1). Let S 0,1 and S 1,0 be defined as in Section 4.2. Then, S x1,y1 = S 0,1 and S x2,y2 = S 1,0 are associated with path π 3 , clearly satisfying Properties S1-S6. Further, p 0,1 1 is the last occupied point of S 0,1 and S 1,0 ; moreover, as |d h |, |d v | > 3, the line through p 0,1 1 with slope 1 1 has a and b to its right, and both S 0,1 and S 1,0 have free points. It follows that, after drawing π 2 , Condition 4 is satisfied, with S 0,1 and S 1,0 associated with path π 3 .

Next, suppose that after drawing π i one of Conditions 1-5 is satisfied, where sequences S x1,y1 and S x2,y2 are associated with π i+1 ; then, we argue about the drawing of path π i+1 and about the sequences to be associated with π i+2 . a b l(x 2 , y 2 ) l(x 1 , y 1 ) Suppose that after drawing π i Condition 1 is satisfied. Consider the first free point of S x1,y1 , that is, point q 1 (π i+1 ) ≡ q 1 (π i ) -(x 1 , y 1 ). Also consider the first free point of S x2,y2 , that is, point q 2 (π i+1 ) ≡ q 2 (π i ) + (x 2 , y 2 ). Such points exist by the hypotheses of Condition 1.

q 1 (π i ) π i l 1,2 (π i )
q 1 (π i ) π i l 1,2 (π i )
We will prove that π i+1 passes through q 1 (π i+1 ) and q 2 (π i+1 ), that is, either π i+1 is aq 1 (π i+1 )q 2 (π i+1 )b, or π i+1 is aq 1 (π i+1 )b with q 2 (π i+1 ) being a point of q 1 (π i+1 )b, or π i+1 is aq 2 (π i+1 )b with q 1 (π i+1 ) being a point of aq 2 (π i+1 ). Denote by l 1,2 (π i ) and l 1,2 (π i+1 ) the lines through q 1 (π i ) and q 2 (π i ) and through q 1 (π i+1 ) and q 2 (π i+1 ), respectively.

Claim 1 Path π i+1 passes through q 1 (π i+1 ) and q 2 (π i+1 ).

Proof: Refer to Fig. 18. Since l 1,2 (π i ) has slope y1+y2 x1+x2 , by the hypotheses of Condition 1, the slope of l 1,2 (π i+1 ) is: By Property S3, y1 x1 and y2 x2 are the generating fractions of y1+y2 x1+x2 , hence, by Lemma 6, l 1,2 (π i ) and l 1,2 (π i+1 ) are consecutive grid lines. Then no grid point is internal to polygon (q 1 (π i ), q 2 (π i ), q 2 (π i+1 ), q 1 (π i+1 )). As triangles (a, q 1 (π i ), q 1 (π i+1 )) and (b, q 2 (π i ), q 2 (π i+1 )) are enclosed in T (S x1,y1 , a) and in T (S x2,y2 , b), respectively, polygon π i ∪ (a, q 1 (π i+1 ), q 2 (π i+1 ), b) contains no grid point. Hence, as long as ab ∪ (a, q 1 (π i+1 ), q 2 (π i+1 ), b) is a convex polygon, we have π i+1 = (a, q 1 (π i+1 ), q 2 (π i+1 ), b).

y(q 2 (π i )) + y 2 -(y(q 1 (π i )) -y 1 ) x(q 2 (π i )) + x 2 -(x(q 1 (π i )) -x 1 ) = y 1 + y 2 + (y(q 2 (π i )) -y(q 1 (π i ))) x 1 + x 2 + (x(q 2 (π i )) -x(q 1 (π i ))) = y 1 + y 2 + m(y 1 + y 2 ) x 1 + x 2 + m(x 1 + x 2 ) = (m + 1)(y 1 + y 2 ) (m + 1)(x 1 + x 2 ) = y 1 + y 2 x 1 + x 2 , a b l(x 2 , y 2 ) l(x 1 , y 1 ) q 1 (π i ) π i l 1,2 (π i ) q 2 (π i ) q 2 (π i+1 ) q 1 (π i+1 ) π i+1 l 1,2 (π i+1 )
Consider the possible placements of a and b with respect to l 1,2 (π i+1 ). Neither a nor b is to the left of l 1,2 (π i+1 ), as such vertices are to the right of l 1,2 (π i ), by the hypotheses of Condition 1, and hence, if they were to the left of l 1,2 (π i+1 ), they would be in the open strip delimited by l 1,2 (π i ) and l 1,2 (π i+1 ), which are consecutive grid lines, thus contradicting Lemma 6.

Hence, either a and b are both on l 1,2 (π i+1 ), or one of a and b is on l 1,2 (π i+1 ) and the other one is to the right of such a line, or both a and b are to the right of l 1,2 (π i+1 ). It follows that ab∪(a, q 1 (π i+1 ), q 2 (π i+1 ), b) is a convex polygon and hence that π i+1 = (a, q 1 (π i+1 ), q 2 (π i+1 ), b). 2

Now we discuss which condition is satisfied after drawing π i+1 , discussing the case in which a and b are both on l 1,2 (π i+1 ), the case in which one of a and b is on l 1,2 (π i+1 ) and the other one is to the right of such a line, and the case in which both a and b are to the right of l 1,2 (π i+1 ).

• First, we prove the following:

Claim 2 Vertices a and b can not be both on l 1,2 (π i+1 ).

Proof: Suppose, for a contradiction, that a and b are both on l 1,2 (π i+1 ). Then, we have that q 1 (π i+1 ) and q 2 (π i+1 ) are both on segment ab. However, this implies that q 1 (π i+1 ) and q 2 (π i+1 ) are not inside T 1 , thus violating Property S4, a contradiction. 2

• Second, consider the case in which a and b are both to the right of l 1,2 (π i+1 ).

-Suppose that both S x1,y1 and S x2,y2 have free points as in Fig. 18. Then we have the following: l(x 1 , y 1 ) -Next, we prove the following:

q 1 (π i ) π i q 2 (π i ) l 1,2 (π i ) π i+1 l 1,2 (π i+1 ) q 1 (π i+1 ) q 2 (π i+1 )
Claim 5 Suppose that S x1,y1 has free points. Then S x2,y2 also has free points.

Proof: We prove that if S x1,y1 has free points and S x2,y2 has not, then q 2 (π i+1 ) lies on segment q 1 (π i+1 )b and hence b is on l 1,2 (π i+1 ), a contradiction to the hypotheses. Refer to Fig. 20. Denote by q 1 and q 2 points q 1 ≡ q 1 (π i+1 ) -(x 1 , y 1 ) and q 2 ≡ q 2 (π i+1 ) + (x 2 , y 2 ).

Consider the line l 1,2 through q 1 and q 2 . Such a line has slope y1+y2 x1+x2 . This can be proved analogously as it was shown that line l 1,2 (π i+1 ) has slope y1+y2 x1+x2 in the proof of Claim 1. Since y1 x1 and y2 x2 are the generating fractions of y1+y2 x1+x2 , l 1,2 (π i+1 ) and l 1,2 are consecutive grid lines, hence they do not have any grid point between them, by Lemma 6. However, l 1,2 a b l(x 1 , y 1 )

l 1,2 (π i+1 ) l ′ 1,2 q 1 (π i+1 ) q 2 (π i+1 ) q ′ 2 q ′ 1 l(x 2 , y 2 )
Fig. 20: The case in which vertices a and b are both to the right of l1,2(πi+1), Sx 1 ,y 1 has free points, and Sx 2 ,y 2 has no free point does not occur.

has b to the left as l 1,2 intersects the interior of segment ab, by Property S5. Thus b can not be to the right of l 1,2 (π i+1 ), a contradiction. 2

The proof of following claim is analogous to the proof of Claim 5.

Claim 6 Suppose that S x2,y2 has free points. Then S x1,y1 also has free points.

It follows that if a and b are both to the right of l 1,2 (π i+1 ), then after drawing π i+1 either Condition 1 or Condition 2 is satisfied with S x1,y1 and S x2,y2 associated with path π i+2 .

• Third, consider the case in which a is to the right of l 1,2 (π i+1 ) and b is on l 1,2 (π i+1 ). Then, observe that π i+1 is aq 1 (π i+1 )b with q 2 (π i+1 ) being a point of q 1 (π i+1 )b.

Suppose that S x1,y1 has no free point left. We have the following:

Claim 7 π i+2 = π M1 = ab.
Proof: Refer to Fig. 21. Consider points q 1 ≡ q 1 (π i+1 ) -(x 1 , y 1 ) and q 2 ≡ q 2 (π i+1 ) + (x 2 , y 2 ).

Consider the line l 1,2 through q 1 and q 2 . Such a line has slope y1+y2 x1+x2 . This can be proved as it was shown that line l 1,2 (π i+1 ) has slope y1+y2 x1+x2 in the proof of Claim 1. Then, l 1,2 and l 1,2 (π i+1 ) are consecutive grid lines and the open strip delimited by them contains the interior of triangle (b, q 1 (π i+1 ), q(S x1,y1 , ab)), that hence has no grid point in its interior, by Lemma 6. Since T (S x1,y1 , a) has no grid point in its interior, by Property S6, then polygon π i+1 ∪ ab has no grid point in its interior, and hence

π i+2 = π M1 = ab. 2
Next, suppose that S x1,y1 has free points. Refer to Fig. 22. Consider the first free point on S x1,y1 , that is, point q 1 ≡ q 1 (π i+1 ) -(x 1 , y 1 ). Consider the sequence of grid points S x1+x2,y1+y2 whose points have coordinates q 1 + m(x 1 + x 2 , y 1 + y 2 ), where 0 ≤ m ≤ i * , where i * is the largest integer such that

q 1 + i * (x 1 + x 2 , y 1 + y 2 ) is inside T 1 .
We have the following: x2 are the generating fractions of y1+y2 x1+x2 , y1 x1 and y1+y2 x1+x2 are the generating fractions of 2y1+y2 2x1+x2 . Since S x1,y1 and S x2,y2 satisfy Property S4 after drawing π i , since π i+1 passes through the first free point of S x1,y1 , and since all the points of S x1+x2,y1+y2 are free, it follows that S x1,y1 and S x1+x2,y1+y2 satisfy Property S4. As S x1,y1 and S x2,y2 satisfy Property S5 after drawing π i , then l(x 1 , y 1 ) intersects the interior of segment ab; since the line with slope y1+y2 x1+x2 through q 1 (π i+1 ) intersects ab in b and since q 1 is internal to π i+1 ∪ ab, then l(x 1 + x 2 , y 1 + y 2 ) intersects the interior of segment ab, thus S x1,y1 and S x1+x2,y1+y2 satisfy Property S5. Sequences S x1,y1 and a b l(x 1 , y 1 )

a b l(x 1 , y 1 ) l 1,2 (π i+1 ) l ′ 1,2 q 1 (π i+1 ) q 2 (π i+1 ) q ′ 2 q ′ 1 l(x 2 , y 2 )
q 1 (π i+1 ) π i+1 l 1,2 (π i+1 ) l(x 1 + x 2 , y 1 + y 2 ) q 2 (π i+1 )
q ′ 1 Fig. 22: Illustration for the case in which a is to the right of l1,2(πi+1), b is on l1,2(πi+1), and Sx 1 ,y 1 has free points.

a b q 1 (π i+1 ) l 1,2 (π i+1 ) q ′ 1 l 2y1+y2 2x1+x2 (q 1 (π i+1 )) Fig. 23: If 2y 1 +y 2 2x 1 +x 2 ≤ dv d h , then l 2y 1 +y 2 2x 1 +x 2 (q1(πi+1)
) has a to its right.

S x2,y2 satisfy Property S6 after drawing π i , hence T (S x1,y1 , a) contains no grid point; further, T (S x1+x2,y1+y2 , b) is entirely contained in the strip delimited by l 1,2 (π i+1 ) and by the line through q 1 with slope y1+y2 x1+x2 , hence, by Lemma 6, it contains no grid point. Thus S x1,y1 and S x1+x2,y1+y2 satisfy Property S6. 2

As already observed, π i+1 is aq 1 (π i+1 )b; further, q 1 (π i+1 ) is the last occupied point of S x1,y1 and all the points of S x1+x2,y1+y2 are free, the first free point of S x1,y1 coincides with the first point of S x1+x2,y1+y2 , segment q 1 (π i+1 )b has slope y1+y2 x1+x2 , y1 x1 is a generating fraction of y1+y2 x1+x2 , and both S x1,y1 and S x1+x2,y1+y2 have free points. Hence, if the line l 2y1+y2 2x1+x2 (q 1 (π i+1 )) through q 1 (π i+1 ) with slope 2y1+y2 2x1+x2 has a and b to its right, then, after drawing π i+1 , Condition 3 is satisfied, where sequences S x1,y1 and S x1+x2,y1+y2 are associated with path π i+2 .

We prove that if l 2y1+y2 2x1+x2 (q 1 (π i+1 )) has not both a and b to its right, then none of Conditions 1-5 is satisfied and in such a special case we can directly estimate the number of paths that come after π i+1 in Π.

Claim 9 If l 2y1+y2 2x1+x2 (q 1 (π i+1 )) has not both a and b to its right, then all the free points inside π i+1 ∪ ab lie on a specific grid line.

Proof: Since the line through q 1 (π i+1 ) with slope y1+y2 x1+x2 , that is l 1,2 (π i+1 ), passes through b and since 2y1+y2 2x1+x2 > y1+y2 x1+x2 as y1 x1 > y2 x2 , it follows that l 2y1+y2 2x1+x2 (q 1 (π i+1 )) has b to its right. Suppose, for a contradiction, that 2y1+y2 2x1+x2 ≤ dv d h , as in Fig. 23. Then l 2y1+y2 2x1+x2 (q 1 (π i+1 )) has a to its right, since it has the line through b with slope 2y1+y2 2x1+x2 to its right, and since this line has a to its right or on it, thus contradicting the assumption that l 2y1+y2 2x1+x2 (q 1 (π i+1 )) has not both a and b to its right.

Next, suppose that 2y1+y2 2x1+x2 > dv d h and suppose that l 2y1+y2 2x1+x2 (q 1 (π i+1 )) does not have a to its right, that is, l 2y1+y2 2x1+x2 (q 1 (π i+1 )) intersects segment ab.

Consider the grid point q ≡ q 1 (π i+1 ) -(2x 1 + x 2 , 2y 1 + y 2 ) ∈ l 2y1+y2 2x1+x2 (q 1 (π i+1 )). Such a point is to the left of the line through q 1 (π i+1 ) with slope y1 x1 , that is the line through the points of S x1,y1 , since y1 x1 > 2y1+y2 2x1+x2 (the last inequality holds because y1 x1 > y2 x2 ). Further, q is to the left of l ab , since q 1 is to the left of l ab , since q ≡ q 1 -(x 1 + x 2 , y 1 + y 2 ), and since y1+y2 x1+x2 < dv d h . In order for l 2y1+y2 2x1+x2 (q 1 (π i+1 )) to intersect ab, q has to be either on the line through q 1 (π i+1 ) and a, or to the right of such a line. Hence, q is either on segment aq 1 (π i+1 ) or it is inside triangle (a, q 1 (π i+1 ), q(S x1,y1 , ab)). In the latter case, shown in Fig. 24, q is inside T (S x1,y1 , a), as (a, q 1 (π i+1 ), q(S x1,y1 , ab)) is a subset of T (S x1,y1 , a). However, by Property S4, T (S x1,y1 , a) contains no grid point, hence such a case never occurs.

a b q 1 (π i+1 ) l 1,2 (π i+1 ) q ′ 1 l ab q l 2y1+y2 2x1+x2 (q 1 (π i+1 ))
Fig. 24: Line l 2y 1 +y 2 2x 1 +x 2 can not intersect the interior of segment ab, as otherwise q would be inside T (Sx 1 ,y 1 , a).

Assume that q is on aq 1 (π i+1 ). Suppose first that point q 1 ≡ q 1 -(x 1 , y 1 ) is inside T 1 , as in Fig. 25. Then, since y1+y2 x1+x2 < dv d h < y1 x1 and since y1 x1 > 2y1+y2 2x1+x2 , point q 1 ≡ q 1 -(x 1 + x 2 , y 1 + y 2 ) is inside triangle (a, q 1 (π i+1 ), q(S x1,y1 , ab)). Then, q 1 is inside T (S x1,y1 , a), as (a, q 1 (π i+1 ), q(S x1,y1 , ab)) is a subset of T (S x1,y1 , a). However, by Property S4, T (S x1,y1 , a) contains no grid point, hence such a case never occurs.

Assume that q 1 is the only free point of S x1,y1 inside T 1 . Further, q = a. Indeed, if q = a, then, since q 1 is inside T 1 , dv d h < y1+y2 x1+x2 , a contradiction. We prove that all the grid points inside π i+1 ∪ab lie on the line l y1+y2 x1+x2 (q 1 ) with slope y1+y2 x1+x2 through q 1 . Since triangle (a, q 1 (π i+1 ), q(S x1,y1 , ab)) is a subset of T (S x1,y1 , a), it contains no grid point; the only grid point on the line through q 1 (π i+1 ) with slope y1 x1 is q 1 , which lies on l y1+y2 x1+x2 (q 1 ); l y1+y2 x1+x2 (q 1 ) and the line l y1+y2 x1+x2 (q 1 ) with slope y1+y2 x1+x2 through q 1 are consecutive grid lines, as y1 x1 is a generating fraction of y1+y2 x1+x2 , hence they contain no grid point between them, by Lemma 6; it follows that there is no grid point in the interior of triangle (q 1 , q(S x1,y1 , ab), q(S x1+x2,y1+y2 , ab)). Finally, l y1+y2 x1+x2 (q 1 ) and the line l y1+y2 x1+x2 (q 1 (π i+1 )) with slope y1+y2 x1+x2 through q 1 (π i+1 ) are consecutive grid lines, as y1 x1 is a generating fraction of y1+y2 x1+x2 , hence they contain no grid point between them, by Lemma 6; it follows that there is no

a b q 1 (π i+1 ) l 1,2 (π i+1 ) q ′ 1 l ab q l 2y1+y2 2x1+x2 (q 1 (π i+1 ))
q ′′ 1 q ′′′ 1 Fig. 25: If line l 2y 1 +y 2 2x 1 +x 2 (q1(πi+1)) contains segment aq1(πi+1), point q 1 can not be inside T1, as otherwise q 1 would be inside T (Sx 1 ,y 1 , a). grid point in the interior of polygon (q 1 (π i+1 ), q 1 , q(S x1+x2,y1+y2 , ab), b). Hence, under the above assumptions, all the free points inside π i+1 ∪ ab lie on l y1+y2 x1+x2 (q 1 ), thus proving the claim. 2

Observe that the number of paths that come after π i+1 in Π is at most the number of free points inside π i+1 ∪ ab plus one. Hence if all the free points inside π i+1 ∪ ab lie on a specific grid line, the number of paths that come after π i+1 in Π is at most the number of points on a specific grid line.

• Fourth, the case in which b is to the right of l 1,2 (π i+1 ) and a is on l 1,2 (π i+1 ) can be discussed analogously to the previous case.

Suppose that after drawing π i Condition 2 is satisfied. We have the following:

Claim 10 Polygon π i ∪ ab has no internal grid point.

Proof: the points q 1 ≡ q 1 (π i ) -(x 1 , y 1 ) and q 2 ≡ q 2 (π i ) + (x 2 , y 2 ). Consider the lines l 1,2 (π i ) through q 1 (π i ) and q 2 (π i ) and l 1,2 through q 1 and q 2 . Line l 1,2 (π i ) has slope y1+y2 x1+x2 by the hypotheses of Condition 2. Line l 1,2 has slope y1+y2 x1+x2 . This can be proved analogously as it was shown that line l 1,2 (π i+1 ) has slope y1+y2 x1+x2 in the proof of Claim 1. By the hypotheses of Condition 2 and since l(x 1 , y 1 ) and l(x 2 , y 2 ) intersect segment ab, points q 1 and q 2 lie in the closed half-plane delimited by l ab and not containing c. Then, by Lemma 6, no grid point is in the open strip delimited by l 1,2 (π i ) and l 1,2 . If at least one of q 1 and q 2 is to the right of l ab , then one of a and b is to the left of l 1,2 , hence it is in the open strip delimited by l 1,2 (π i ) and l 1,2 . It follows that both q 1 and q 2 are on l ab . Then, no grid point is internal to polygon (q 1 (π i ), q 2 (π i ), q 2 , q 1 ). As (a, q 1 (π i ), q 1 ) and (b, q 2 (π i ), q 2 ) are enclosed in T (S x1,y1 , a) and in T (S x2,y2 , b), respectively, polygon π i ∪ ab contains no grid point. 2

Since polygon π i ∪ ab has no internal point, π i = π M1-1 . Hence, π i+1 = π M1 = ab. Suppose that after drawing π i Condition 3 is satisfied. By the hypotheses of the case, π i is aq 1 (π i )b. Suppose that Condition 3(i) is satisfied, the case in which Condition 3(ii) is satisfied being analogous. a b q 1 (π i+1 )

q ′ 1 q l y1+y2 x1+x2 (q 1 (π i+1 )) q ′′ 1 l y1+y2 x1+x2 (q ′ 1 ) l y1+y2 x1+x2 (q ′′ 1 )
Fig. 26: If line l 2y 1 +y 2 2x 1 +x 2 (q1(πi+1)) contains segment aq1(πi+1) and q 1 is the free only point of Sx 1 ,y 1 inside T1, then all the grid points inside πi+1 ∪ ab lie on l y 1 +y 2

x 1 +x 2 (q 1 ).

Consider the first free point of S x1,y1 , that is, point q 1 (π i+1 ) ≡ q 1 (π i ) -(x 1 , y 1 ). By the hypotheses of Condition 3, such a point exists and it is also the first point of S x2,y2 . We have the following:

Claim 11 π i+1 is aq 1 (π i+1 )b.
Proof: Since, by the hypotheses of Condition 3, the second segment of π i lies on a line l 1 with slope y2 x2 , since the line l 2 passing through the points of S x2,y2 has slope y2 x2 , and since y1 x1 is a generating fraction of y2 x2 , then l 1 and l 2 are consecutive grid lines. By Lemma 6, there exists no grid point in the strip delimited by l 1 and l 2 , hence there exists no grid point inside polygon (q 1 (π i ), q 1 (π i+1 ), b, q(S x2,y2 , ab)); thus, there exists no grid point inside triangle (q 1 (π i ), q 1 (π i+1 ), b). Further, there exists no grid point inside triangle (q 1 (π i ), q 1 (π i+1 ), a), as such a triangle is a subset of T (S x1,y1 , a). Since (a, q 1 (π i+1 ), b) is a convex polygon, π i+1 is aq 1 (π i+1 )b. 2

Let l 1,2 (π i+1 ) be the line through q 1 (π i+1 ) with slope y1+y2 x1+x2 . Now we discuss which condition is satisfied after drawing π i+1 , discussing the case in which a and b are both on l 1,2 (π i+1 ), the case in which one of a and b is on l 1,2 (π i+1 ) and the other one is to the right of such a line, and the case in which both a and b are to the right of l 1,2 (π i+1 ).

Neither a nor b is to the left of l 1,2 (π i+1 ). This can be shown as when Condition 1 is satisfied. Hence, either a and b are both on l 1,2 (π i+1 ), or one of a and b is on l 1,2 (π i+1 ) and the other one is to the right of this line, or both a and b are to the right of l 1,2 (π i+1 ). Now we discuss which condition is satisfied after drawing π i+1 .

• First, it can be shown that a and b are not both on l 1,2 (π i+1 ) as in the proof of Claim 2.

• Second, consider the case in which a and b are both to the right of l 1,2 (π i+1 ).

-If both S x1,y1 and S x2,y2 have free points, then, after drawing π i+1 Condition 4 is satisfied with S x1,y1 and S x2,y2 associated with path π i+2 . This can be shown as in the proof of Claim 3.

-If neither S x1,y1 nor S x2,y2 has free points, then, after drawing π i+1 Condition 5 is satisfied with S x1,y1 and S x2,y2 associated with path π i+2 . This can be shown as in the proof of Claim 4.

-The case in which exactly one of S x1,y1 and S x2,y2 has free points never occurs. This can be shown as in the proof of Claim 5.

• Third, consider the case in which a is to the right of l 1,2 (π i+1 ) and b is on l 1,2 (π i+1 ).

If S x1,y1 has no free point left, then π i+2 = π M1 = ab. This can be shown as in the proof of Claim 7.

If S x1,y1 has free points, consider the first free point on S x1,y1 , that is, point q 1 ≡ q 1 (π i+1 ) -(x 1 , y 1 ). Consider the sequence of grid points S x1+x2,y1+y2 whose points have coordinates q 1 + m(x 1 + x 2 , y 1 + y 2 ), where 0 ≤ m ≤ i * , where i * is the largest integer such that q 1 + i * (x 1 + x 2 , y 1 + y 2 ) is inside T 1 . Then, as in the proof of Claims 8 and 9, we have that after drawing π i+1 either Condition 3 is satisfied, where sequences S x1,y1 and S x1+x2,y1+y2 are associated with path π i+2 , or all the free points inside π i+1 ∪ ab lie on a specific grid line and hence the number of paths that come after π i+1 in Π is at most the number of points on such a grid line.

• Fourth, the case in which b is to the right of l 1,2 (π i+1 ) and a is on l 1,2 (π i+1 ) can be discussed analogously to the previous case.

Suppose that after drawing π i Condition 4 is satisfied. By the hypotheses of Condition 4, π i is aq 1 (π i )b, where q 1 (π) is the last occupied point of S x1,y1 and the last occupied point of S x2,y2 . Consider the first free point of S x1,y1 , that is, point q 1 (π i+1 ) ≡ q 1 (π i ) -(x 1 , y 1 ), and consider the first free point of S x2,y2 , that is, point q 2 (π i+1 ) ≡ q 1 (π i ) + (x 2 , y 2 ). Such points exist, by the hypotheses of Condition 4. Then, π i+1 = (a, q 1 (π i+1 ), q 2 (π i+1 ), b). This can be shown as in the proof of Claim 1. Denote by l 1,2 (π i ) and l 1,2 (π i+1 ) the lines through q 1 (π i ) and q 2 (π i ) and through q 1 (π i+1 ) and q 2 (π i+1 ), respectively. Now we discuss which condition is satisfied after drawing π i+1 , discussing the case in which a and b are both on l 1,2 (π i+1 ), the case in which one of a and b is on l 1,2 (π i+1 ) and the other one is to the right of such a line, and the case in which both a and b are to the right of l 1,2 (π i+1 ).

Neither a nor b is to the left of l 1,2 (π i+1 ). This can be shown as when Condition 1 is satisfied. Hence, either a and b are both on l 1,2 (π i+1 ), or one of a and b is on l 1,2 (π i+1 ) and the other one is to the right of this line, or both a and b are to the right of l 1,2 (π i+1 ). Now we discuss which condition is satisfied after drawing π i+1 .

• First, it can be shown that a and b are not both on l 1,2 (π i+1 ) as in the proof of Claim 2.

• Second, consider the case in which a and b are both to the right of l 1,2 (π i+1 ).

-If both S x1,y1 and S x2,y2 have free points, then, after drawing π i+1 Condition 1 is satisfied with S x1,y1 and S x2,y2 associated with path π i+2 . This can be shown as in the proof of Claim 3.

-If neither S x1,y1 nor S x2,y2 has free points, then, after drawing π i+1 Condition 2 is satisfied with S x1,y1 and S x2,y2 associated with path π i+2 . This can be shown as in the proof of Claim 4.

the total number of paths in Π is at most

1 π1 + max{d h , d v } paths in Π1 + f i=2 max{d h , d v } 2 i-2 + 1 paths in Πi, for 2 ≤ i ≤ f + max{d h , d v } final paths + 1 ab ≤ 2 + max{d h , d v } + 2 max{d h , d v } + (f -1) + max{d h , d v } = O(max{d h , d v }),
where the last equality holds since

f = O(log(max{d h , d v })) = O(max{d h , d v }), because x i 1 , y i 1 , x i 2 , y i 2 ≥ 2 i-2
and because both the numerator and the denominator of any line slope can not exceed max{d h , d v }.

Since the number of paths in Π is Ω(n), then max{d h , d v } ∈ Ω(n) and hence max{W, H} ∈ Ω(n). Theorem 2 follows.

Proof of Theorem 3

In this section we prove Theorem 3, that is, we present an n-vertex series-parallel graph G k requiring Ω(2 √ log n ) width and Ω(2 √ log n ) height in any straight-line or poly-line grid drawing. As an immediate consequence of Theorems 2 and 3 we have a proof of Theorem 4, that is, there exist series-parallel graphs requiring Ω(n2 √ log n ) area in any straight-line or poly-line grid drawing. In order to prove Theorem 3, we heavily exploit Theorem 2, stating that there exists a constant c > 0 such that every planar straight-line or poly-line grid drawing of K 2,n in a W × H grid satisfies max{W, H} ≥ c • n. Then, let d = min{ c 4 , 1 8 } and let f (n) be a function to be computed later.

Graph G k is inductively defined as follows. Graph G 1 is K 2,f (n)-2 . Graph G i+1 is defined as follows. Consider f (n) copies G 1,1 i , G 1,2 i , G 2,1 i , G 2,2 i , . . . , G j,1 i , G j,2 i , . . . , G f (n) 2 ,1 i , G f (n) 2 ,2 i of G i ; construct f (n) 2 series-parallel graphs G 1 i , G 2 i , . . . , G f (n) 2 i
, where G j i is the series composition of G j,1 i and G j,2 i ; then, G i+1 is the parallel composition of graphs

G 1 i , G 2 i , . . . , G f (n) 2 i
. See Fig. 27. First, we prove Theorem 3 for sufficiently large graphs, that is, for graphs having a number of vertices that is at least some constant n 0 to be determined later. From now till it is otherwise specified, assume that n ≥ n 0 .

Suppose that f (n) ≥ 8, ∀n ≥ n 0 . Let n be the number of vertices of graph G k . We have the following main lemma.

Lemma 8 Let Γ i be any poly-line grid drawing of G i and let a i and b i be the poles of G i , for each 1 ≤ i ≤ k. Then, one of the following holds:

• Condition 1: Both the height and the width of Γ i are greater than or equal to d • f (n);

• Condition 2: The width of Γ i is greater than or equal to d • f (n) and Γ i contains a polygonal path l i connecting a i to b i that has height greater than or equal to 2 i and such that, for every point p ∈ l i , min{y(a i ), y(b i )} ≤ y(p) ≤ max{y(a i ), y(b i )}; or the height of Γ i is greater than or equal to d • f (n) and Γ i contains a polygonal path l i connecting a i to b i that has width greater than or equal to 2 i and such that, for every point p ∈ l i , min{x(a

i ), x(b i )} ≤ x(p) ≤ max{x(a i ), x(b i )}.
Proof: We prove the statement by induction on i. In the base case, consider any poly-line grid drawing Γ 1 of G 1 . By Theorem 2, one of the height and the width of Γ 1 , say the width of Γ 1 , is at least c•f (n), hence it is at least d•f (n). We prove that the height of Γ 1 is at least d • f (n) or there exists a polygonal path l 1 connecting a 1 to b 1 that has height greater than or equal to 2 and such that, for every point p ∈ l 1 , min{y(a 1 ), y(b 1 )} ≤ y(p) ≤ max{y(a 1 ), y(b 1 )}.

Denote by l(a 1 ) and l(b 1 ) the horizontal lines through a 1 and b 1 , respectively, where we suppose, without loss of generality, that y(a 1 ) ≤ y(b 1 ). Suppose that at least 2d • f (n) paths of G 1 = K 2,f (n)-2 have non-empty intersection with the open half-plane H -(y = y(a 1 )) (that is, the half-plane y < y(a 1 ))

or with the open half-plane H + (y = y(b 1 )) (that is, the half-plane y > y(b 1 )). By Lemma 1 with v = (0, -1), for each path π of G 1 that has non-empty intersection with H -(y = y(a 1 )), there exists a grid point p ∈ π whose y-coordinate is minimum among the points of π. Clearly, p belongs to H -(y = y(a 1 )). Hence, p belongs to a horizontal grid line h that does not intersect or contain the segment a 1 b 1 . By Lemma 2, at most two paths of G 1 have their points with smallest y-coordinate belonging to h. It can be proved analogously that at most two paths of G 1 have their points with greatest y-coordinate belonging to the same horizontal grid line in H + (y = y(b 1 )). Hence, as 2d • f (n) paths of G 1 have non-empty intersection with H -(y = y(a 1 )) or with

H + (y = y(b 1 )), it follows that Γ 1 has height at least d • f (n). Now suppose that less then 2d • f (n) paths of G 1 have non-empty intersection with H -(y = y(a 1 )) or with H + (y = y(b 1 )). Then, since d ≤ 1 8 , at least f (n) -2 -2d • f (n) + 1 ≥ 3f (n) 4
-1 paths of G 1 are such that, for every point p of any such a path, y(a 1 ) ≤ y(p) ≤ y(b 1 ). By planarity of Γ 1 at most one of such paths touches l(a 1 ) in a point whose y-coordinate is y(a 1 ) and whose x-coordinate is smaller than x(a 1 ). Analogously, at most one of such paths touches l(a 1 ) in a point whose y-coordinate is y(a 1 ) and whose x-coordinate is greater than x(a 1 ). The last two statements hold even if b 1 replaces a 1 . Hence, as long as 3f (n) 4 -1 ≥ 5, which is always the case whenever f (n) ≥ 8, there is at least one path of G 1 whose every point p has y(a 1 ) ≤ y(p) ≤ y(b 1 ) and whose only vertex v = a 1 , b 1 has y-coordinate greater than y(a 1 ) and smaller than y(b 1 ). It follows that the polygonal path (a 1 , v, b 1 ) connecting the poles of G 1 has height at least two and is such that, for every point p ∈ (a 1 , v, b 1 ), y(a 1 ) ≤ y(p) ≤ y(b 1 ), thus proving the base case of the induction. Now let's consider the inductive case. Let Γ i+1 be any poly-line grid drawing of G i+1 , containing drawings Γ 1,1 i , Γ 1,2 i , Γ 2,1 i , Γ 2,2 i , . . . , Γ j,1 i , Γ j,2 i , . . . , Γ

f (n) 2 ,1 i , Γ f (n)
2 ,2 i of graphs G 1,1 i , G 1,2 i , G 2,1 i , G 2,2 i , . . . , G j,1 i , G j,2 i , . . . , G

f (n) 2 ,1 i , G f (n) 2 ,2 i
, respectively. By induction, for each 1 ≤ j ≤ f (n) 2 and each 1 ≤ k ≤ 2, Γ j,k i satisfies Condition 1 or Condition 2.

If there exists a drawing Γ j,k i , for some 1 ≤ j ≤ f (n) 2 and 1 ≤ k ≤ 2, such that Γ j,k i satisfies Condition 1, then the width and the height of Γ j,k i are both greater than or equal to d • f (n), hence the width and the height of Γ i+1 are both greater than or equal to d • f (n), and there is nothing else to prove.

Hence, we can assume that, for every 1 ≤ j ≤ f (n) 2 and 1 ≤ k ≤ 2, Γ j,k i satisfies Condition 2. If there exist two drawings Γ j ,k i and Γ j ,k i , for some 1 ≤ j , j ≤ f (n) 2 and 1 ≤ k , k ≤ 2, where j = j and k = k do not hold simultaneously, such that the width of Γ j ,k i is greater than or equal to d • f (n) and such that the height of Γ j ,k i is greater than or equal to d • f (n), then the width and the height of Γ i+1 are both greater than or equal to d • f (n), and there is nothing else to prove.

Hence, we can assume (without loss of generality, up to a rotation of the Cartesian axes) that, for every 1 ≤ j ≤ f (n) 2 and 1 ≤ k ≤ 2, the width of Γ j,k i is greater than or equal to d • f (n) and Γ j,k i contains a polygonal path l j,k i connecting a i to b i that has height greater than or equal to 2 i and such that, for every point p ∈ l j,k i , min{y(a i ), y(b i )} ≤ y(p) ≤ max{y(a i ), y(b i )}. Denote by l j i the path connecting a i+1 and b i+1 composed of l j,1 i and l j,2 i . Denote by l(a i+1 ) and l(b i+1 ) the horizontal lines through a i+1 and b i+1 , respectively, where we suppose, without loss of generality, that y(a i+1 ) ≤ y(b i+1 ). Analogously to the base case, it can be proved that if at least 2d • f (n) paths l j i have non-empty intersection with the open half-plane H -(y = y(a i+1 )) (that is, the half-plane y < y(a i+1 ))

or with the open half-plane H + (y = y(b i+1 )) (that is, the half-plane y > y(b i+1 )), then Γ i+1 has height at least d • f (n). Now suppose that less then 2d • f (n) paths l j i have non-empty intersection with H -(y = y(a i+1 )) or with H + (y = y(b i+1 )). Then, since d ≤ 1 8 , at least f (n) -2d • f (n) + 1 ≥ 3f (n) 4 + 1 paths l j i are such that, for every point p of any such a path, y(a i+1 ) ≤ y(p) ≤ y(b i+1 ). By planarity of Γ i+1 at most one of such path l j i touches l(a i+1 ) in a point whose y-coordinate is y(a i+1 ) and whose x-coordinate is smaller than x(a i+1 ). Analogously, at most one of such paths l j i touches l(a i+1 ) in a point whose y-coordinate is y(a i+1 ) and whose x-coordinate is greater than x(a i+1 ). The last two statements hold even if b i+1 replaces a i+1 . Hence, as long as 3f (n) 4 + 1 ≥ 5, which is always the case whenever f (n) ≥ 8, there is at least one path l j i composed of path l j,1 i , that connects the poles a i+1 and v of G j,1 i , and of path l j,2 i , that connects the poles b i+1 and v of G j,2 i , such that v has y-coordinate greater than y(a i+1 ) and smaller than y(b i+1 ). By inductive hypothesis, l j,1 i has height greater than or equal to 2 i and, for every point p ∈ l j,1 i , y(a i+1 ) ≤ y(p) ≤ y(v); further, l j,2 i has height greater than or equal to 2 i and, for every point p ∈ l j,2 i , y(v) ≤ y(p) ≤ y(b i+1 ); hence, l j i has height greater than or equal to 2 i+1 and, for every point p ∈ l j i , y(a i+1 ) ≤ y(p) ≤ y(b i+1 ), thus completing the induction.

2

Corollary 2 Any poly-line grid drawing of G k has height and width that are both greater than or equal to min{d • f (n), 2 k }.

We now compute f (n) as a function of k and n. By construction

|G 1 | = f (n); since G i is composed of f (n) copies of G i-1 , |G i | ≤ f (n) • |G i-1 |; hence, inductively, we obtain that |G k | ≤ f k (n). Assuming that |G k | = n, then f k (n) ≥ n, that is, f (n) ≥ n 1 k .
By Corollary 2, any poly-line grid drawing Γ k of G k has height and width that are both greater than or equal to min{d • f (n), 2 k } ≥ min{d • n 1 k , 2 k }. Then, we choose k in such a way that n 1 k and 2 k are equal. This is done as follows.

2 k = n 1 k ; log 2 (2 k ) = log 2 (n 1 k ); k log 2 (2) = 1 k log 2 (n); k 2 = log 2 (n); k = log 2 (n).
By Corollary 2, both the height and the width of Γ k , with k = log 2 (n), are greater than or equal to

min{d • n 1 √ log 2 (n) , 2 √ log 2 (n) } = d • 2 √ log 2 (n) = Ω(2 √ log 2 (n)
), and Theorem 3 follows if n ≥ n 0 .

Since we need f (n) = 2 √ log 2 (n) ≥ 8, ∀n ≥ n 0 , then n 0 = 512. Observe that the d • 2 √ log 2 (n) lower bound is less than 1 for all n < 512, as d ≤ 1 8 . Since every drawing of a graph that is not a collection of paths has height and width at least one, the d • 2 √ log 2 (n) lower bound holds for graphs with any number (that is, even smaller than 512) of nodes, thus completing the proof of Theorem 3.

Conclusions and Open Problems

In this paper we have shown that there exist series-parallel graphs requiring Ω(n2 √ log n ) area in any straight-line or poly-line grid drawing. Such a result has been achieved in two steps. In the first one, we derived an Ω(n) lower bound for the maximum between the height and the width of any poly-line grid drawing of K 2,n . In the second one, we derived an Ω(2 √ log n ) lower bound for the minimum between the height and the width of any poly-line grid drawing of certain series-parallel graphs.

The best known upper bound for the area requirements of poly-line grid drawings of series-parallel graphs is O(n 3/2 ) [Bie05, Bie10], while no sub-quadratic area upper bound is known in the case of straight-line grid drawings. Hence, in both cases, the gap between the upper and the lower bound is large, thus justifying the following two questions:

Problem 1 What are the area requirements for poly-line grid drawings of series-parallel graphs?

Problem 2 What are the area requirements for straight-line grid drawings of series-parallel graphs?

David Wood [START_REF] Wood | Private Communication[END_REF] conjectures the following: Let p 1 , . . . , p k be positive integers. Let G(p 1 ) be the graph obtained from K 3 by adding p 1 new vertices adjacent to v and w for each edge (v, w) of K 3 . For k ≥ 2, let G(p 1 , p 2 , . . . , p k ) be the graph obtained from G(p 1 , p 2 , . . . , p k-1 ) by adding p k new vertices adjacent to v and w for each edge (v, w) of G(p 1 , p 2 , . . . , p k-1 ). Observe that G(p 1 , p 2 , . . . , p k ) is a series-parallel graph.

Conjecture 1 (Wood [START_REF] Wood | Private Communication[END_REF]) Every straight-line grid drawing of G(p 1 , p 2 , . . . , p k ) requires Ω(n 2 ) area for some choice of k and p 1 , p 2 , . . . , p k .

Fig. 1 :

 1 Fig. 1: (a) A four-connected plane graph requiring n 2 × n 2 -1 area in any poly-line drawing. (b) A plane graph with maximum degree three requiring quadratic area in any poly-line drawing. (c) A plane graph with outerplanarity two requiring quadratic area in any poly-line drawing.

Fig. 2 :

 2 Fig.2: A straight-line drawing of K2,n with linear area and linear aspect ratio.

Fig. 4 :

 4 Fig. 4: (a) Illustration for the proof of Lemma 1. Disk D is the small shaded region. (b) Illustration for the proof of Lemma 2.

  4.b). Consider any path π 3 between a and b. If π 3 is internal to C, then it can not share a point different from a and b with l unless it shares points different from a and b with C. If π 3 is external to C, then it either shares points different from a and b with C or it is in part contained in the open half-plane delimited by l and not containing a and b. If π 3 is part internal and part external to C, then it shares points different from a and b with C. In any case we have a contradiction. 2

Fig. 7 :

 7 Fig. 7: Illustration of the notation for the proof of Theorem 2.

Fig. 9 :

 9 Fig. 9: (a) Sequences S1,0 and S0,1. (b) Paths π k+1 , with 1 ≤ k ≤ k1.

Fig. 10 :

 10 Fig. 10: (a) Sequence S1,1. (b) Paths π k 1 +k+1 , with 1 ≤ k ≤ k2.

Fig. 10

 10 Fig. 10.b.Again, three cases have to be considered, namely the one in which a, p 1,1 k2 , p 1,0 k1+k2 , and b are all collinear, the one in which a, p 1,1 k2 , and p 1,0 k1+k2 are collinear (and b is not), and the one in which p 1,1 k2 , p 1,0 k1+k2 , and b are collinear (and a is not). In the first case, path π k1+k2+1 coincides with segment ab, hence π k1+k2+1 = π M1 . Otherwise, a, p 1,1 k2 , and p 1,0 k1+k2 are collinear (and b is not), or p 1,1 k2 , p 1,0 k1+k2 , and b are collinear (and a is not). Suppose that a, p 1,1 k2 , and p 1,0 k1+k2 are collinear (and b is not). Then S 1,1 is replaced by a sequence S 2,1 of points lying on a line with slope 1 2 . Namely, such points have coordinate p 2,1 k = p 1,0 k1+k2+1 -(k -1)(2, 1), for 1 ≤ k ≤ i 3 , where i 3 is the largest integer such that point p 1,0 k1+k2+1 -(i 3 -1)(2, 1) is internal to T 1 . See Fig.11.a.

Fig. 11 :

 11 Fig. 11: (a) Sequence S2,1. (b) Paths π k 1 +k 2 +k+1 , with 1 ≤ k ≤ k3.

Fig. 12 :

 12 Fig. 12: (a) Sequence S3,1. (b) The paths in Π2.

Fig. 14 :

 14 Fig. 14: After drawing πi, Condition 2 is satisfied.

Fig. 15 :

 15 Fig. 15: After drawing πi, Condition 3 is satisfied.

Fig. 16 :

 16 Fig. 16: After drawing πi, Condition 4 is satisfied.

Fig. 17 :

 17 Fig. 17: After drawing πi, Condition 5 is satisfied.

Fig. 18 :

 18 Fig. 18: Drawing of πi+1 when Condition 1 holds.

Claim 3

 3 After drawing π i+1 Condition 1 is satisfied with S x1,y1 and S x2,y2 associated with path π i+2 . a b l(x 2 , y 2 )

Fig. 19 :-Claim 4

 194 Fig. 19: Vertices a and b are both to the right of l1,2(πi+1) and neither Sx 1 ,y 1 nor Sx 2 ,y 2 has free points.

Fig. 21 :

 21 Fig. 21: If a is to the right of l1,2(πi+1), b is on l1,2(πi+1), and Sx 1 ,y 1 has no free point, then πi+2 = πM 1 = ab.Claim 8 Sequences S x1,y1 and S x1+x2,y1+y2 satisfy Properties S1-S6. Proof: Sequences S x1,y1 and S x1+x2,y1+y2 satisfy Property S1, as sequences S x1,y1 and S x2,y2 satisfy Properties S1 and S3. Since line l 1,2 (π i+1 ) has slope y1+y2 x1+x2 , as shown in the proof of Claim 1, and since a is to the right of this line, it follows that y1+y2 x1+x2 < dv d h , and hence S x1,y1 and S x1+x2,y1+y2 satisfy Property S2. S x1,y1 and S x1+x2,y1+y2 satisfy Property S3; namely, since y1 x1 and y2 x2 are the generating fractions of y1+y2 x1+x2 , y1 x1 and y1+y2 x1+x2 are the generating fractions of 2y1+y2 2x1+x2 . Since S x1,y1 and S x2,y2 satisfy Property S4 after drawing π i , since π i+1 passes through the first free point of S x1,y1, and since all the points of S x1+x2,y1+y2 are free, it follows that S x1,y1 and S x1+x2,y1+y2 satisfy Property S4. As S x1,y1 and S x2,y2 satisfy Property S5 after drawing π i , then l(x 1 , y 1 ) intersects the interior of segment ab; since the line with slope y1+y2 x1+x2 through q 1 (π i+1 ) intersects ab in b and since q 1 is internal to π i+1 ∪ ab, then l(x 1 + x 2 , y 1 + y 2 ) intersects the interior of segment ab, thus S x1,y1 and S x1+x2,y1+y2 satisfy Property S5. Sequences S x1,y1 and

Fig. 27 :

 27 Fig. 27: Graphs Gi, with f (n) = 6. (a) G1. (b) G2. (c) G3.

  for every point p ∈ π, the lemma follows. Otherwise, consider the part π of π starting at a and ending at the first point p in which v • p ≥ v • p , for every point p ∈ π (see Fig.4.a). Since each point p = p of π is such that v • p < v • p, there exists a small disk D centered at p such that the part of π enclosed in D is increasing in the direction determined by v, when π is oriented from a to p. Further π, when oriented from a to b, can not be increasing in the direction determined by v immediately after p, otherwise there would exist a point p such that v • p > v • p. It follows that π changes its slope at p and, by definition of poly-line grid drawing, p is a grid point.2Lemma 2 Consider any drawing of K 2,n . Let l be any line that does share any point with the open segment ab. No three paths π 1 , π 2 , and π 3 of K 2,n exist such that: (i) π 1 , π 2 , and π 3 do not share any point except for a and b; (ii) π 1 , π 2 , and π 3 are entirely contained in the closed half-plane delimited by l and containing a and b; and (iii) each of π 1 , π 2 , and π 3 shares at least one point different from a and b with l.

Acknowledgements

Thanks to Giuseppe Di Battista for very useful discussions. Thanks to David Wood for sharing his strong conjecture.

This work is partially supported by the Italian Ministry of Research, Grant number RBIP06BZW8, FIRB project "Advanced tracking system in intermodal freight transportation" and by the Swiss National Science Foundation, Grant No. 200021-125287/1. 1365-8050

-The case in which exactly one of S x1,y1 and S x2,y2 has free points never occurs. This can be shown as in the proof of Claim 5.

• Third, consider the case in which a is to the right of l 1,2 (π i+1 ) and b is on l 1,2 (π i+1 ).

If S x1,y1 has no free point left, then π i+2 = π M1 = ab. This can be shown as in the proof of Claim 7.

If S x1,y1 has free points, consider the first free point on S x1,y1 , that is, point q 1 ≡ q 1 (π i+1 ) -(x 1 , y 1 ). Consider the sequence of grid points S x1+x2,y1+y2 whose points have coordinates q 1 + m(x 1 + x 2 , y 1 + y 2 ), where 0 ≤ m ≤ i * , where i * is the largest integer such that q 1 + i * (x 1 + x 2 , y 1 + y 2 ) is inside T 1 . Then, as in the proof of Claims 8 and 9, we have that after drawing π i+1 either Condition 3 is satisfied, where sequences S x1,y1 and S x1+x2,y1+y2 are associated with path π i+2 , or all the free points inside π i+1 ∪ ab lie on a specific grid line and hence the number of paths that come after π i+1 in Π is at most the number of points on such a grid line.

• Fourth, the case in which b is to the right of l 1,2 (π i+1 ) and a is on l 1,2 (π i+1 ) can be discussed analogously to the previous case.

Suppose that after drawing π i Condition 5 is satisfied. We have the following claim, that can be proved analogously to Claim 10: Claim 12 Polygon π i ∪ ab has no internal grid point.

Proof that max{d

We now compute how many paths exist in Π, as a function of d h and d v . Denote by S x i 1 ,y i 1 and by S x i 2 ,y i 2 the sequences of grid points that are used by Π i , where the grid points in S x i 1 ,y i 1 lie on a line with slope y i 1 /x i 1 and the grid points in S x i 2 ,y i 2 lie on a line with slope y i 2 /x i 2 . Notice that, following the notation of Section 4.2, S x 1 1 ,y 1 1 = S 0,1 and S x 1 2 ,y 1 2 = S 1,0 . Further, if a, p 0,1 k1 , and p 1,0 k1 are collinear (and b is not), then S x 2 1 ,y 2 1 = S l,1 , and S x 2 2 ,y 2 2 = S l+1,1 , where l is defined as in Section 4.2, while if p 0,1 k1 , p 1,0 k1 , and b are collinear (and a is not), then S x 2 1 ,y 2 1 = S 1,l , and S x 2 2 ,y 2 2 = S 1,l+1 . We claim that x i 1 , y i 1 , x i 2 , y i 2 ≥ 2 i-2 , for i ≥ 2. Notice that, since l ≥ 1, we already observed that such a claim holds when i = 2. From the discussion in Section 4.2 (and subsequent proof in Section 4.3), we have that y i 1 is obtained as the sum of the numerators y i-1 a and y i-1 b of the slopes of two lines containing grid points traversed by paths in Π i-1 . Inductively, y i-1 a

. The number of paths in Π i is the number of grid points in the one out of S x i 1 ,y i 1 and S x i 2 ,y i 2 , with the greatest number of points. When i = 1, each of S 0,1 and S 1,0 has at most max{d h , d v } grid points. Further, for i ≥ 2, S x i 1 ,y i 1 and S x i 2 ,y i 2 lie on lines with slopes whose numerators and denominators are greater than or equal to 2 i-2 . Hence, each of such sequences has at most max{d h ,dv}

+ 1 grid points. In the special case in which the geometry of paths stops to satisfy Conditions 1-5, all the remaining free points lie on a specific grid line, as proved in Section 4.3. Since each remaining path uses one of such free points and no more than max{d h , d v } free points lie on a specific grid line, there are at most max{d h , d v } paths that are drawn in such a special case. Such paths are below called final paths. Hence, We remark that, for outerplanar graphs and trees, no super-linear area lower bounds are known, hence the determination of the area requirements for the straight-line and poly-line grid drawings of such graph classes still requires research efforts. However, we believe (and Conjecture 1 strengthens such a conviction) that understanding whether every series-parallel graph admits a straight-line drawing in subquadratic area is the most interesting open problem in the topic of small-area planar graph drawing. Tab. 1: Area bounds for grid drawings of planar graphs and their sub-classes.