V Dujmović

W Evans

S Lazard

W Lenhart

G Liotta

D Rappaport

S Wismath

On Point-sets that Support Planar Graphs $

Keywords:

A universal point-set supports a crossing-free drawing of any planar graph. For a planar graph with n vertices, if bends on edges of the drawing are permitted, universal point-sets of size n are known, but only if the bend points are in arbitrary positions. If the locations of the bend points must also be specified as part of the point set, we prove that any planar graph with n vertices can be drawn on a universal set S of O(n 2 / log n) points with at most one bend per edge and with the vertices and the bend points in S. If two bends per edge are allowed, we show that O(n log n) points are sufficient, and if three bends per edge are allowed, O(n) points are sufficient. When no bends on edges are permitted, no universal point-set of size o(n 2 ) is known for the class of planar graphs. We show that a set of n points in balanced biconvex position supports the class of maximum-degree-3 series-parallel lattices.

Introduction

A set of points supports the drawing of a graph G if there is a one-to-one mapping f of the vertices of G to the points so that for all pairs of edges (a, b), (c, d) in G (where a, b, c, d are distinct), segments f (a)f (b) and f (c)f (d) do not intersect. A set of points that supports the drawing of all n-vertex graphs in some class is called universal for that class, or simply universal if the class is all planar graphs. The size of any universal point-set for planar graphs requires at least 1.235n points as shown by Kurowski [START_REF] Kurowski | A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs[END_REF] (see also Chrobak and Karloff [START_REF] Chrobak | A lower bound on the size of universal sets for planar graphs[END_REF]). Early graph drawing results, such as the canonical ordering technique of de Frasseix, Pach, Pollack [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF] and Schnyder's embedding [START_REF] Schnyder | Embedding planar graphs on the grid[END_REF] demonstrate that an n × n grid of points is a universal point-set. However, no universal point-set of size o(n 2 ) is known.

Smaller universal point-sets for sub-classes of planar graphs are known. For example, any outerplanar graph can be drawn on any set of n points in general position [START_REF] Gritzmann | Embedding a planar triangulation with vertices at specified points[END_REF]. Indeed, if the point-set is in convex position, then it supports exactly the family of outerplanar graphs. Determining other families of planar graphs for which universal point-sets of size n exist is an interesting problem. We examine a particular type of point-set, of size n, in which points are arranged in biconvex position, and show that it supports the drawing of all maximum-degree-3 series-parallel lattices, a class of graphs that contains members that are not outerplanar.

The main contributions in this paper are stated in Theorems 1 and 2, and pertain to universal point-sets for straight-line drawings, and drawings with bends respectively. Theorem 1. For all n, there exist universal point-sets of cardinality n that support the family of maximumdegree-3 series-parallel lattices with n vertices.

Suppose we relax the definition of support to allow edges of the graph to map to polylines composed of (at most) k + 1 line segments. In other words, we allow edges that "bend" at most k times. In this case, universal point-sets of size n exist for two bends [START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF] and even one bend [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF]. However, these results assume that the bend points can be placed in arbitrary locations and these bend points are not included as part of the universal point-set. It is natural to ask if there exists a point-set that supports all planar graphs where each vertex and each bend point occurs at a point in the set. As before, we require all pairs of edges (a, b) and (c, d) (where a, b, c, d are distinct) to map to non-intersecting polylines. Previous to this paper, no such point-set of cardinality o(n 2 ) was known for any value of k. Extending the results of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] and [START_REF] Kaufmann | Embedding vertices at points: Few bends suffice for planar graphs[END_REF] in a straightforward manner imply point-sets of size O(n 3 ). For k = 3, 2, 1, we present such universal point-sets of cardinality O(n), O(n log n), and O(n 2 / log n) respectively. Our analyses of these cardinalities are tight; no lower bounds other than Ω(n) are known for these cases.

Theorem 2. For all n, there exist universal point-sets of cardinality O(n), O(n log n), and O(n 2 / log n) that support the drawing of all n-vertex planar graphs with at most three, two, or one bend per edge, respectively.

The paper is organized as follows. In Sections 2.1, 2.2, 2.3 the effect of allowing bend points on edges is considered, when the bend points must also be located at points of the supporting point-set. Universal pointsets are constructed for three cases: when at most three, two, or one bend(s) per edge are permitted, thus establishing Theorem 2. One consequence of our construction is that the class of sub-Hamiltonian graphs (i.e. a planar graph that can be made Hamiltonian by the addition of edges while preserving planarity) can be universally supported efficiently (i.e. with fewer bends).

In Section 3 a particular point-set (called biconvex) of size n is considered and we show a class of planar graphs for which it is universal. An application of this result to simultaneous embeddings and other consequences are discussed. Table 1 summarizes our results in terms of which sets of planar graphs can be supported on point-sets of a given cardinality with a specified number of bends. ) 0 [START_REF] De Fraysseix | How to draw a planar graph on a grid[END_REF][START_REF] Schnyder | Embedding planar graphs on the grid[END_REF] We adopt standard notation from the graph drawing literature and we assume all graphs have n vertices. Two of our results rely on point-sets that have a specific form; see, for example, Fig. 10. Two nonintersecting non-linear curves λ 1 and λ 2 are defined to be biconvex if: each of the curves λ 1 and λ 2 is convex, the convex hull of the 4 endpoints of the two curves completely contains the two curves, and the line segment joining any point a of λ 1 to any point b of λ 2 does not intersect either curve except at a and b.

Without loss of generality, we assume the existence of a horizontal line separating the two curves with λ 1 below λ 2 . A point-set all of whose points lie on two curves that are biconvex is said to be in biconvex position. We note that point-sets in such a configuration have been used in other contexts under different names, for example as a double-chain in the triangulation enumeration literature.

Universal Point-sets for Drawing Planar Graphs with Bends

In this section we establish Theorem 2 by constructing universal point-sets for each of the three cases: 3, 2 or 1 bend per edge allowed. A fundamental tool in our constructions for universal point-sets with bends is the following result proving the existence of a book embedding of planar graphs in which the edges are permitted to cross the spine [START_REF] Di Giacomo | Curve-constrained drawings of planar graphs[END_REF]. A monotone topological book embedding of a planar graph G is a planar drawing such that all vertices of G are represented as distinct points on a spine (i.e. the x-axis), and each edge is either represented as an arc in the bottom page (below the x-axis), or as an arc in the top page (above the x-axis), or as the concatenation of two arcs: the first (leftmost) in the bottom page and the second in the top page with their common crossing point between spine points. See Fig. 1.

Theorem 3 ([8]

). Every planar graph has a proper monotone topological book embedding which can be computed in time linear in the size of the graph.

A Set of Θ(n) Points for Drawing Planar Graphs with Three Bends per Edge

Lemma 4. There exists a universal set of 10n -18 points that supports the drawing of planar graphs with 3 bends per edge.

Proof. Before introducing the (fixed) universal point-set, we first outline how the graph will be processed. Consider a proper monotone topological book embedding of the input graph. For each edge that intersects the spine, introduce a dummy vertex creating an augmented two page book embedding with the vertices of the spine drawn on a horizontal line. There are at most n+m 4n-6 vertices on the spine. Imagine a horizontal line slightly above the spine that intersects all arcs in the top page -call these points of intersection from left to right b 1 , . . . , b 2a where a is the number of arcs. Note that a 3n -6.

Consider a point-set that lies on two curves in biconvex position and consists of 6n -12 points on the top curve and 4n -6 points on the bottom curve. We prove that any such point-set is universal for drawing planar graphs with at most three bends per edge. For any specific graph, its augmented two page book embedding defines the drawing and requires at most 10n -18 points. The at most 4n -6 vertices on the spine (including dummy vertices) are assigned, in order, to the first points on the bottom curve. The bend points b 1 , . . . , b 2a are assigned to the first 2a points of the upper curve in left to right order and then each arc in the top page is drawn using the associated bend points. These polylines do not intersect since the upper curve is convex and any segment joining the two curves does not properly intersect these curves. The arcs in the bottom page can be drawn with no bends -they are chords of the bottom curve. Each arc in the top page uses two bend points. Substituting a bend point for each of the dummy vertices results in a drawing with at most three bends per edge. Refer to Fig. 2 for an example of the construction.

Note that a sub-Hamiltonian planar graph corresponds exactly to a graph that has a two page (unaugmented) book embedding [START_REF] Di Giacomo | Curve-constrained drawings of planar graphs[END_REF]. Since such graphs do not require dummy vertices, they can be drawn with at most two bends per edge.

A Set of Θ(n log n) Points for Drawing Planar Graphs with 2 Bends per Edge

Before describing our universal point-sets for the two bend case, we describe the geometric idea underlying our construction. Similar to Section 2.1, we draw the spine vertices of an augmented two page book embedding on a set of points that lie on a slightly concave curve close to the x-axis. This implies that all the arcs in the bottom page of the book embedding can be drawn as straight line segments. For arcs in the top page, if the arc is from the ith to the (i + j)th spine vertex, it is drawn to bend at a point at level j. We place approximately n/j bend points approximately equally spaced in the x-dimension at level j, since only n/j top arcs can have "length" j. The bend point that lies between the ith and (i + j)th spine vertices is used by this arc. Each level is at a y-coordinate that is large enough that the drawing of an arc that uses a bend point at a lower level "nests" inside any drawing of an arc from the same vertex using a higher level bend point. Of course, for each j > n/2, there can be only one arc of "length" j and it uses a single bend point at level j. The total number of bend points we place is O(n log n).

Lemma 5. There exists a universal set of Θ(n log n) points that supports the drawing of planar graphs with 2 bends per edge.

Proof. Let N = 4n-6 and refer to Fig. 3. The following point-set is a 2-bend-universal point-set for n-vertex planar graphs: Place points at (x, 0) for x = 1, . . . , N . (Actually, place points at (x, x(N -x)

N 2
) so that they lie on a slightly concave curve, but for clarity we omit this technical detail in the following.) Let g(i, j) = j i j . For j = 1, 2, . . . , N , place the set of points {(g(i, j) + min{j, N 2 } -1 2 , y j ) | i = 1, 2, . . . , N -j} (avoiding duplicates) where y j satisfies y 1 = 1 and y j+1 > N y j for 1 j < N -1. Notice that the number of points on line y j is at most N j since it is the number of distinct values of i j for 1 i Nj, which is at most 1 + N -j j = N j . Fig. 3 shows the set of points for n = 4. To embed a given n-vertex planar graph G, first construct a proper monotone topological book embedding of G with vertices on the x-axis and introduce dummy vertices on the arcs that cross the x-axis. Let G be the resulting graph, which has (at most) 3n -6 additional vertices and arcs. Place the vertices of G on the points (x, 0), x = 1, . . . , N , preserving their order from the book embedding. Let v x be the vertex at point (x, 0). For every arc (v i , v i+j ) in G above the x-axis in the book embedding, draw a one-bend polyline from (i, 0) to (g(i, j) + min{j, N 2 } -1 2 , y j ) to (i + j, 0). For every arc (v i , v i+j ) in G below the x-axis in the book embedding, draw the straight polyline from (i, 0) to (i + j, 0). We will show that no two polylines above the x-axis cross in this drawing by an analysis of the slopes of the segments of the polylines.

For any arc (v i , v i+j ) above the x-axis in G , let ∆ x and ∆ y be the difference in the x-and y-coordinates respectively of v i and the bend point of arc (v i , v i+j ). We first show that

1 2 ∆ x N 2 . If j N 2 , then ∆ x = g(i, j) + j -1 2 -i and, by definition, 0 i -g(i, j) j -1, thus ∆ x ∈ [1 -j + j -1 2 , j -1 2 ] ⊆ [ 1 2 , N 2 ]. If j > N
2 , then i < N 2 (otherwise i + j > N ), thus i < j and g(i, j) = 0; thus ∆ x = 0 + N 2 -1 2i which is less than N 2 and at least 1 2 since i < N 2 and thus i N 2 -1 (since N is even). Consider now two arcs (v i , v i+j ) and (v i , v i +j ) above the x-axis where i i . Since the arcs do not intersect in the book embedding, we have i + j i + j, and so 0 ii jj with at least one inequality being strict (otherwise the two arcs have identical endpoints). Thus j < j. We now show that the slope of the initial segment of the polyline for arc (v i , v i+j ) is greater than that of the first segment for arc(v i , v i +j ) and that the slope of the second segment of the polyline for arc (v i , v i+j ) is less than that of the one for arc (v i , v i +j ). Since the first segments of each polyline have positive slopes and the second segments have negative slopes, the polylines do not intersect above the x-axis, that is, the "nesting" of the book embedding arcs is preserved.

Again, defining ∆ x and ∆ y as above for the first segment of the polyline in G of arc (v i , v j ), and defining similarly ∆ x and ∆ y for the first segment of the polyline in G of arc (v i , v i +j ), we have that both N ∆ x . On the other hand, y j y j +1 > N y j , thus ∆ y > N ∆ y . Hence,

∆y ∆x > N ∆ y N ∆ x
, which is our slope requirement for the segments incident to v i and v i in arcs (v i , v i+j ) and (v i , v i +j ) respectively. A similar argument establishes our slope requirement for the segments incident to v i+j and v i +j in arcs (v i , v i ) and (v i , v i +j ) respectively. Note also that = Θ(N log N ) = Θ(n log n) points as candidate bend points for edges in the top page, and 4n -6 points on the x-axis to support the augmented spine.

Sub-Hamiltonian graphs require only one bend per edge using this construction, since they have a book embedding containing no dummy vertices.

A Set of Θ(n 2 / log n) Points for Drawing Planar Graphs with 1 Bend per Edge

In [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF], the authors describe a universal set of n points on which all planar graphs with n vertices can be drawn with at most one bend per edge. Although not noted in that paper, their construction trivially yields a universal set of size Θ(n 3 ) of points for the bend locations. We show here how to reduce the size of the universal set of bend points to Θ(n 2 / log n) while preserving a linear size universal set of points for the vertices. Our construction being similar to that in [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF], we recall briefly this construction, referring to Fig. 1 and4.

Given a planar graph G with n vertices, we embed the graph on vertices p i = (-2 i , i) for i = 0, . . . , n -1 with at most one bend per edge, as follows. We first compute a proper monotone topological book embedding, Γ of G. We relabel the vertices of that book embedding from right to left, as v 0 , . . . , v n-1 . We then map these vertices to p 0 , . . . , p n-1 , respectively. All the edges below the spine are drawn as straight-line segments. Figure 4: The one-bend drawing of the three edges, in the top page or crossing the spine, and incident to v 0 = w 1 in the graph of Fig. 1 following the construction of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF]. The points p 6 and p 7 are not shown since the figure is to scale.

The others are drawn with a bend point as follows: Consider an edge whose rightmost vertex is v i and that intersects the spine on the interval [v u+1 , v u ) (inclusive of v u+1 -which is left of v u -for the case where the leftmost endpoint of the edge is v u+1 ). Such an edge is drawn with a bend point on the horizontal line through p u and in the vertical strip delimited by p i and p i+1 (recall that the v i are drawn at the p i ). In what follows, the horizontal line through p u is called the bend line through p u . This construction requires a set of candidate bend points of size Θ(n 3 ) since inside every vertical strip, on every bend line, there need to be up to ni -1 candidate bend points (for every possible edge with right endpoint p i ).

We show how this construction can be modified to contain only a subquadratic universal set of points for the bends while preserving a linear size universal set of points for the vertices. Lemma 6. There exists a universal set of Θ(n 2 / log n) points that supports the drawing of planar graphs with 1 bend per edge.

Proof. The proof is organized as follows. We first add some isolated "dummy" vertices in the topological book embedding Γ of the input graph G. With a slight modification of the construction of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF], we can reduce the number of candidate bend points in each vertical strip bounded by p i+1 and p i to at most one per bend line, resulting in an overall total of Θ(n 2 ); moreover, no drawing will use more than one candidate bend point from any bend line.

We then show how we can reduce the number of candidate bend points from Θ(n 2 ) to Θ(n 2 / log n). We do this by first describing our construction of a universal set of points for the bends, then proving that the size of this set is Θ(n 2 / log n), then verifying that the construction of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] (slightly modified to only use the reduced number of candidate bend points) is still valid. This final step of verifying that the (slightly modified) construction of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] gives a crossing-free drawing of any planar graph on our universal point set is almost the same as in [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF]. Since this proof is fairly long-though not particularly difficult-we do not duplicate it here; instead we give an alternate argument by describing motions of the bend points in the construction of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] to locations in our Θ(n 2 / log n) point set that do not introduce any crossings.

Augmented topological book embedding. We consider, as in [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF], a proper monotone topological book embedding Γ of our input graph G (see Fig. 1). On the spine of Γ, add isolated dummy vertices as follows (see Fig. 5(a)): Between any two vertices v and w of G that are consecutive on the spine of Γ, with v to the left of w, add d v dummy vertices to the spine of Γ, where d v is the number of edges of G that cross the spine between v and w plus the number of top-page edges of Γ having leftmost endpoint v. More precisely, in the interval (v, w), we add on the spine one dummy vertex between each pair of consecutive spine-crossing edges as well as between the rightmost spine-crossing edge and w; the remaining vertices are added between v and the leftmost spine-crossing edge (or between v and w if there is no spine-crossing edge). If w is mapped to p i , then the dummy vertices will be mapped to p i+1 , . . . , p i+dv and v will be mapped to p i+dv+1 , providing a separate bend line for each edge intersecting the segment [p i+dv+1 , p i ) and guaranteeing that at most one bend point is drawn on every bend line (though the bend line supports many candidate bend points). Since the number of edges of a planar graph is at most 3n -6, we add at most that number of isolated vertices and the total number of vertices is less than 4n. Let Γ be the resulting graph. Modification of the construction of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] leading to Θ(n 2 ) candidate bend points. We show how a slight modification of the construction of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] on this augmented graph Γ leads to a quadratic universal set of points for the bends. Refer to Fig. 5(b). Since Γ has no more than 4n vertices, we construct a set of 4n points p 0 , . . . , p 4n-1 as in [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] that will support the vertices v 0 , v 1 , . . . of any augmented graph Γ . We assume from this point on that each vertex v i of Γ is mapped to the point p i . We then place vertically above every point p i one candidate bend point on every bend line. More precisely, we place candidate bend points at integer heights between i + 1 and n -1 above p i , and, since we do not want to consider a candidate bend point that coincides with p i , we place one to the right of p i (at the same height) and sufficiently close to p i . These points will serve as candidate bend points in the vertical strip delimited by p i and p i-1 , that is, every top-page edge or spine-crossing edge of Γ having rightmost endpoint v i-1 will use one of these bend points. All the edges of Γ that are below the spine are drawn as straight-line segments, as explained above and as in [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF]. We now describe how to draw the edges that lie at least partially above the spine. Let v i represent an original (non-dummy) vertex of G and let v i-1 , . . . v i-dv i represent the dummy vertices to the right of v i (thus v i-dv i -1 is the next original vertex of G to the right of v i on the spine of Γ ). Now consider the collection of d vi edges of G that gave rise to these dummy vertices; they are the top-page edges having left endpoint v i along with the edges that cross the spine of Γ between vertices v i and v i-dv i -1 . Denote these edges by e 1 , . . . , e dv i , where the first edges to appear in the list are the edges with left endpoint v i , ordered by their clockwise order at v i , and the last edges to appear in the list are those that cross the spine between v i and v i-dv i -1 in the (left to right) order that they cross the spine. Each edge e k in this list will have its bend point on the bend line at height ik (that is, the bend line through p i-k ); if the right endpoint of edge e k is v r , then e k will use the candidate bend point vertically above p r+1 . For each edge e in G, denote by h(e) the height of the bend point for edge e in the drawing. Note that at most one bend point from any bend line will be used, and thus that h(•) induces a total ordering on the top-page and spine-crossing edges of Γ . Moreover, this ordering (for decreasing h(•)) is the same as the ordering obtained by concatenating, for all vertices of Γ considered from left to right, the edges e 1 , . . . , e dv i in the order described above.

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 0 v 8 v 9 v 10 v 11 v 12 v 14 v 13
To understand why no two of the one-bend polylines intersect properly, we describe a motion that carries the bend points in the original construction of [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] to the bend points in our construction. We consider two consecutive motions. The first one ensures that bend points end up being drawn on distinct bend lines. Note that in the original construction the bend points of two edges of Γ are drawn on the same bend line if and only if both edges have the same leftmost endpoint or if they intersect the spine between the same two consecutive vertices; by definition of the dummy vertices of Γ , this may only happen for two top-page edges that share the same left endpoint. Consider then a vertex v i that is the left endpoint of k edges in the top page of Γ . Denote these edges by e 1 , . . . , e k in their counterclockwise order at v i . These edges (in order) are drawn in the original construction with bend points, ordered from left to right, at the height of p i-1 . Considering the edges e 1 , . . . , e k in that order, we move the bend point of e j along its rightmost segment in the direction of its rightmost endpoint until it reaches height h(e j ) (i.e., we shorten the rightmost segment). All movements take place in the quadrilateral region bounded from above and on the right by edge e k (whose bend point does not move), from below by the horizontal line through p i , and on the left by the segment p i p i-k . Since no edges other than e 1 , . . . , e k intersect that region, we do not create any intersections during the motion. Furthermore, at the end of this motion, no two bend points lie on the same bend line. 1 For the second motion, consider any point p i . All the edges whose right endpoint is p i have their bend point drawn in the vertical strip bounded by the vertical lines through p i+1 and p i . We can thus move these bend points to the left boundary of the strip, without creating any intersection by moving them one by one, starting in every strip by the bottommost bend points. 2 This motion results in the drawing we described above.

Construction of a Θ(n 2 / log n) size universal set for the bend points. We obtain a subquadratic-size universal set of points as follows. As above, we construct a set P of 4n points p 0 , . . . , p 4n-1 as in [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] that will support the vertices of any augmented graph Γ . We then define a set of vertical strips S 0 , . . . , S m , where m ∈ Θ(n/ log n), that are disjoint and that together contain all of the points p 0 , . . . , p 4n-2 (and possibly contain p 4n-1 as well). For each vertical strip S i we will describe how to place Θ(n) candidate bend points in S i which will be used by edges with right endpoint in S i while avoiding intersections among edges. Note that S m may also contain p 4n-1 but it need not since p 4n-1 is not the right endpoint of any edge. The drawing of Γ will then be obtained, from the drawing using Θ(n 2 ) candidate bend points, by moving every bend point to the left (on the same bend line) until it reaches one (not necessarily the first one) of the new Θ(n 2 / log n) candidate bend points.

Let N = 4n -1, the height of p 4n-1 , and refer to Fig. 6. We simultaneously construct a subsequence p u0 , . . . , p um of P along with a set q 0 , . . . , q m of points on the bend line at height N such that q i and p ui define the left and right boundaries, respectively, of S i .

Let u 0 = 0, so p u0 = p 0 . The point q 0 is defined to be the intersection of the bend line at height N with the line p u0 p u0+1 = p 0 p 1 . Let p u1 be the rightmost point of p 0 , . . . , p 4n-1 that is to the left of q 0 (or vertically aligned with q 0 ). The second point q 1 , is the intersection of the bend line at height N with the line p u1 p u1+1 . Inductively, the point p ui is used to define q i , as the point at which the bend line at height N intersects the line through p ui and p ui+1 ; q i is then used to define p ui+1 as the rightmost p j to the left of q i (or vertically aligned with q i ). The construction ends at the first value of m for which q m is to the left of p 4n-2 .

Before proving that the number of vertical strips S 0 , . . . , S m is in Θ(n/ log n), we complete the description of our set of candidate bend points. Refer to Fig. 6. Consider the vertical strip S i bounded by q i on its left side and p ui on its right side (we assume S i is open on its left side and closed on its right side). For each pair p j , p j+1 of consecutive points of P in S i , define L i,j to be the portion of the line p j p j+1 that has p j as its right endpoint and the intersection of line p j p j+1 with the vertical line through q i as its left endpoint. Near each point on segment L i,j having integer height strictly larger than j, we place a candidate bend point at

p N Bend-line at height N p ui p ui+1 p ui+1 q i q i+1 (2 ui+1 -2 ui )(N -u i ) y -2 ui -2 ui+1 -2 ui+1
Bend-line at height u i that height and infinitesimally to the right of L i,j . We do this so that the segments from candidate bend points to p j do not overlap, and so that the candidate bend point at height j + 1 is distinct from p j+1 . Moreover we require that between two of these candidate bend points, the higher ones are moved to the right more than the lower ones, so that a segment connecting p j to a lower bend point is below any segment connecting p j to a higher bend point. We also place a candidate bend point at every point of the vertical line through q i with integer y-coordinate from u i+1 to N . 3 Call this set of candidate bend points B i and let

S i S i+1
B = ∪ i=m i=0 B i .
The number of vertical strips is in Θ(n/ log n). We prove here that the number of vertical strips S 0 , . . . , S m is in Θ(n/ log n). We first prove that the index u i of p ui satisfies u i+1 = u i + log(Nu i + 1) .

Recall that u 0 = 0 and that the points p i have coordinates (-2 i , i). By definition p ui+1 is the rightmost point of p 0 , . . . , p 4n-1 that is to the left of q i (or vertically aligned with q i ). The x-distance between p ui and q i is, as shown on Fig. 6, 2 ui (Nu i ). Thus the x coordinate of q i is -(

2 ui + 2 ui (N -u i )). By definition of p ui+1 we have 2 ui+1-1 < 2 ui + 2 ui (N -u i ) 2 ui+1 . Thus u i+1 = u i + log(N -u i + 1) or equivalently u i+1 = u i + log(4n -u i ) .
Since S i is open on the left side and closed on the right side, the strips are non-intersecting and by construction every element of P (except possibly p 4n-1 ) is contained in one of the strips. Note that u i+1 is the size of the intersection of P with S 0 ∪ . . . ∪ S i and so u i+1u i is the size of P ∩ S i . We have thus established that each S i contains log(4nu i ) points of P . In fact, S i contains the log(4nu i ) rightmost vertices remaining in P after having removed the u i rightmost of its vertices-that is, those in

S 0 ∪ • • • ∪ S i-1 .
Moreover, m is such that P minus the points in S 0 ∪ . . . ∪ S m contains at most one point (since two points are sufficient for defining a strip). It follows that m is the number of iterations (over i) of the process of removing iteratively from a set K (K is initially P ) of size 4n, log(|K|) elements until it is of size at most 1. So, define, for every k 1, T (k) to be the number of iterations required to make a set K of size k at most 1 by repeatedly removing log(|K|) of its elements. We claim that T (k) = T (k/2) + Θ(k/ log k). To see this, note that as long as we have removed fewer than k/2 elements of K, we have that log(k) log(|K|) log(k/2) = log(k) -1. In other words, as long as |K| k/2, an iteration removes at least log(k) -1 elements from K. Thus, the number of iterations required to make |K| < k/2 is at most k/2 log(k) -1 , or Θ(k/ log(k)), and so T (k) = T (k/2) + Θ(k/ log k). The Master theorem then yields that T (k) = Θ(k/ log k), which establishes that the number of vertical strips created is Θ(n/ log n).

The number of candidate bend points in every strip S i is in Θ(n). We now prove that for each i = 0, . . . , m, |B i | is in Θ(n). The line p i p i+1 has equation y = -2 -i x + i -1 and intersects the line

y = N at x = -2 i [N -i + 1]. The line x = -2 i [N -i + 1]
intersects the line p j p j+1 (which has equation y = -2 -j x+j-1) at y = (N -i+1)/2 j-i +j-1. Thus, on the line p j p j+1 , we place (N -i+1)/2 j-i +j-1-j = (Ni + 1)/2 j-i -1 > 0 candidate bend points. How many bend points will this yield in total for strip S i ? We have some number, call it k + 1, of these line segments p j p j+1 , starting with j = i , giving the sum j=i+k j=i

[(N -i + 1)/2 j-i -1] < j=i+k j=i (N -i + 1)/2 j-i < j=∞ j=i (N -i + 1)/2 j-i = j =∞ j =0 (N -i + 1)/2 j = 2(N -i + 1) = O(n).
Adding the linear number of candidate bend points on the vertical line through q i results in B i having size in Θ(n).

One-bend drawing of Γ with vertices in P and bend points in B. Now we show that Γ can be drawn with at most one bend per edge such that its vertices are in P and its bend points are in B. The construction is the same as the one described above with Θ(n 2 ) candidate bend points except for the xcoordinates of the bend points that are used. In particular, vertices v i are still mapped to the p i (except that the dummy vertices in Γ are not actually drawn), and an edge v i v j completely in the bottom page of Γ is drawn as the straight line segment p i p j . As before, an edge v i v j that is partially in the top page of Γ is drawn with a bend point whose height is the same as before, and denoted h(v i v j ). Note that it is still the case that at most one bend point on any bend line is used. Contrary to the previous construction, the bend point of an edge v i v j (with v i left of v j ) is chosen in B as follows. Let S k be the vertical strip that contains p j . The candidate bend point that we choose for edge v i v j is the one that lies just to the right of the segment L k,j (the part of the ray from p j through p j+1 that lies in S k ) if that segment extends to height h(v i v j ); otherwise, the bend point is chosen on the vertical left side of S k (at height h(v i v j )).

To complete the proof, it suffices to show that no two edges of Γ have drawings whose one-bend polylines intersect (except possibly at their endpoints). As mentioned earlier, this proof is very similar to that in [START_REF] Everett | Universal sets of n points for one-bend drawings of planar graphs with n vertices[END_REF] and we do not duplicate these arguments here. Instead, we argue that we can move the bend points used in the previous construction (having Θ(n 2 ) candidate bend points) to locations in our Θ(n 2 / log n) point set B without introducing any crossings. We obtain our drawing on the Θ(n 2 / log n) point set from the drawing on the Θ(n 2 ) point set by moving each bend point to the left (on the same bend line) until it reaches its prescribed location.

Consider an edge e whose left and right endpoints are p i and p k , respectively, and whose bend point b lies at the height of p j (and thus i > j > k); see Fig. 7. Let b 0 be the initial location of the bend point in the drawing on the Θ(n 2 ) point set, and b 1 be its final location in the drawing on the Θ(n 2 / log n) point set. We first argue that when b moves on its bend line from b 0 to b 1 , the edge e never intersects any vertex p , = i, k.

Indeed, first observe that by the definition of b 1 (see Fig. 6), segment p k b does not intersect any vertex other than p k for any b between b 0 and b 1 . Second, segment p i b does not intersect any vertex other than p i because, by definition of the points p 0 , . . . , p 4n-1 , segment p i b intersects segment p j p j+1 (see Fig. 7 and [7, Lemma 6]), thus the line p i b leaves all the vertices p i-1 , . . . , p j+1 strictly above it and all the other vertices (distinct from p i ) strictly below it (for any position of b at the height of p j , strictly to the right of p j and to the left of p 0 ).

Hence, when the bend point of an edge e moves between b 0 and b 1 , the edge e does not intersect any vertex (except its endpoints). Observe that if only one edge e moves at a time, its bend point b cannot intersect another edge e before edge e intersects the bend point of e ; indeed, no two bend points lie at the same height and, as b moves to the left, edge e remains a concave chain of two segments having negative slopes. Thus, it only remains to prove that, if only one edge e moves at a time, it does not intersect any other bend point.

First, observe that, when b moves from b 0 to b 1 , the left segment p i b of edge e intersects no other bend point. Indeed, there is no other bend point at the height of b, and since segment p i b intersects the segment p j p j+1 (see Fig. 7), the horizontal rays from the p , > j, and directed to the right (rays which support the bend points above b) do not intersect segment p i b.

It thus remains to prove that, when b moves from b 0 to b 1 , the right segment bp k of edge e intersects no other bend point. Note first that the segment bp k remains during the motion inside the vertical slab S u that contains p k , thus segment bp k cannot intersect any bend point outside of S u . To prove that bp k intersects no bend point inside S u , we consider the motions of the edges in the right order, that is the increasing order of the height of their bend points. Then, by construction of the Θ(n 2 / log n) candidate bend points, the edge bp k cannot intersect any other bend point. Indeed, it may only intersect the bend points in S u that are below b (and left of p k ), and these are either on the vertical line bounding S u on its left, or below the line p k b 1 . Hence, by considering the motions of the bend points in the given order, the motions do not create any intersection, which completes the proof.

Biconvex Point-sets

Any point-set in general position supports the class of outerplanar graphs [START_REF] Gritzmann | Embedding a planar triangulation with vertices at specified points[END_REF]. Indeed a point-set in convex position supports exactly the class of outerplanar graphs, and no other planar graphs. Motivated by this insight we now consider the class of planar graphs that are supported by a point-set in which n/2 points are on one convex curve and the remainder are on another convex curve -in biconvex position. Clearly outerplanar graphs can be supported by this point-set and efficient algorithms such as that developed by Bose [START_REF] Bose | On embedding an outer-planar graph on a point set[END_REF] exist. We show that any (n/2, n/2) biconvex point-set is universal for a subclass of the series-parallel graphs (Theorem 8) and thus establish Theorem 1. Since our purpose is to exhibit universal point-sets for classes of planar graphs, the balancing condition is critical and since the number of vertices could be odd, the balancing must allow for one vertex to be placed arbitrarily. Henceforth denote by n the number of vertices of the given graph.

A planar graph G is biconvex if there exists a crossing-free straight-line drawing Γ of G with all vertices located on the curves λ 1 and λ 2 .

A planar graph G is balanced biconvex if it is biconvex with a drawing Γ in which the numbers of vertices on the two curves differ by at most one; more formally if:

• for n even, n/2 vertices are on λ 1 and n/2 vertices on λ 2 (called uniform and denoted as Γ = )

• for n odd, either:

n-1 2 vertices are on λ 1 and n+1 2 vertices are on λ 2 (called top-heavy and denoted as Γ + ) or -n+1

2 vertices are on λ 1 and n-1 2 vertices are on λ 2 (called bottom-heavy and denoted as Γ + )

It is convenient to be less explicit about the provided point-set and focus on the biconvexity property. The following lemma formalizes that this is sufficient to claim a universal biconvex point-set of suitable size, since, intuitively, we can shift any biconvex drawing on one point-set to any other point-set with the same numbers of points on the two curves.

Lemma 7. If a graph G on n vertices has a balanced biconvex drawing, then every balanced biconvex point-set of size n supports G Proof. A drawing with n/2 vertices on each of two biconvex curves specifies a particular embedding of the graph. Let u, v, w be three consecutive vertices on one of the two curves. Then v and its incident edges can be shifted to any location between u and w without creating a crossing and without changing the circular ordering around all vertices -thus preserving the specified embedding. A given drawing can be shifted onto any particular point-set, of appropriate cardinality, by preserving the ordering of the vertices along each curve.

As a result of Lemma 7, we may shift our attention to drawings on biconvex curves since a particular point-set is not required.

Series-Parallel Graphs and their Decomposition Trees

The class of graphs that we intend to demonstrate to be balanced biconvex, is a subclass of series-parallel graphs, whose definition we now recall. Although this definition is stated in terms of a directed graph, it is ultimately the underlying undirected graph that we require.

A two terminal series-parallel digraph (also called TTSP-digraph) is a planar digraph recursively defined as follows [START_REF] Di Battista | Graph Drawing[END_REF][START_REF] Valdes | The recognition of series-parallel digraphs[END_REF]:

• A directed edge joining two vertices forms a TTSP-digraph.

• Let G and G be two TTSP-digraphs; the digraph obtained by identifying 4 the sink of G with the source of G (Series Composition) is also a TTSP-digraph.

• Let G and G be two TTSP-digraphs; the digraph obtained by identifying the source of G with the source of G , and the sink of G with the sink of G (Parallel Composition) is also a TTSP-digraph.

A TTSP-digraph has one source and one sink which are called its poles. Also, a TTSP-digraph is always acyclic and admits a planar embedding with the poles on the same face.

A TTSP-digraph is a TTSP lattice if for every directed edge (u, v), there is no directed path from u to v that does not contain (u, v). Note that a TTSP lattice cannot have multiple edges.

The undirected underlying graph of a TTSP-digraph is called a two terminal series-parallel graph or TTSP-graph for short; similarly, the undirected underlying graph of a TTSP-lattice is called a two terminal series-parallel lattice or TTSP-lattice for short. We further shorten these terms in the current paper and refer to them as series-parallel (SP).

Associated with a series-parallel graph is a decomposition tree which identifies the operations required to construct the graph. The proofs of several of our lemmas rely on such a decomposition tree, called an SP Q * -tree.

An SP Q * -tree of a T T SP -graph is a simplification of the definition of SP Q * R-trees of general biconnected graphs [START_REF] Di Battista | Spirality and optimal orthogonal drawings[END_REF], or, equivalently, of general st-graphs. An SP Q * R-tree is a tree having four types of nodes, S-, P -, R-, and Q * -nodes, which describes a decomposition of G into its triconnected components; more precisely, an S-node represents a series component, a P -node represents a parallel component, an R-node represents a rigid component (i.e. a component that is a triconnected graph), and each Q * -node represents a simple path of G. If G is series-parallel, its associated SP Q * R-tree has no R-nodes and its structure can be described only in terms of S-, P -, and Q * -nodes. Also, since G is a T T SP -graph the description of the decomposition process can be further simplified, as described below.

A separation pair of G is a pair of vertices such that the removal of these vertices disconnects G. A split pair of G is either a separation pair or a pair of adjacent vertices of G. A split component of G with respect to a split pair {u, v} is either the edge (u, v) or a maximal subgraph C of G such that C is an uv-graph and {u, v} is not a split pair of C.

Let G be a T T SP -graph with source pole u and sink pole v. An SP Q * -tree T of G describes a recursive decomposition of G with respect to its split pairs. Intuitively, T represents a natural way to describe G in terms of its series and parallel compositions.

More formally, T is a rooted tree whose nodes are of three types: S, P , and Q * . Each node µ of T has an associated T T SP -graph (possibly with multiple edges), called the skeleton of µ and denoted by skeleton(µ). Tree T is recursively defined according to the following cases:

Chain case: G consists of a simple path from u to v. Then, T consists of a single Q * -node µ. Graph skeleton(µ) is G itself.
Series case: Graph G is not a biconnected graph. Let u 2 , . . . , u k (k 2) be the cut-vertices of G of degree 3 or more. Since G is planarly biconnectible, each cut-vertex

u i (i = 2, . . . , k) is contained in exactly two connected components G i and G i-1 ; also, u is in G 1 and v is in G k . Each G i is a T T SP -graph with poles u i , u i+1 (i = 1, . . . , k)
, where u 1 = u, and u k+1 = v. Then, the root of T is an S-node µ.

The skeleton(µ) consists of the chain e 1 , . . . , e k , where e i = (u i , u i+1 ) (for i = 1, . . . , k). Node µ has children ν 1 , . . . , ν k , where ν i is the root of the SP Q * -tree T i of G i (i = 1, . . . , k). Graph G i is called the pertinent graph of ν i , and edge e i is called the virtual edge of ν i in skeleton(µ).

Parallel case: Graph G is a biconnected graph with at least two split components with respect to the split pair {u, v}. Denote these split components G 1 , . . . , G k (k 2). Each G i (i = 1, . . . , k) is a T T SPgraph with poles u and v. Then, the root of T is a P -node µ. The graph skeleton(µ) consists of a bundle of parallel edges e i from u to v (i = 1, . . . , k). Node µ has children ν 1 , . . . , ν k , where ν i is the root of the SP Q * -tree T i of G i (i = 1, . . . , k). Graph G i is called the pertinent graph of ν i , and edge e i is called the virtual edge of ν i in skeleton(µ).

3SP Lattices

A series-parallel graph in which every vertex is of maximum-degree-3 is denoted as 3SP. It is the class of 3SP lattices that we will show to be balanced biconvex. We distinguish between two critical cases. If both the source and sink of a 3SP lattice have degree 2 then the graph is called thin and otherwise (i.e. if either pole has degree 3) it is called thick.

There are several simple properties of the decomposition tree T associated with a given 3SP lattice G:

• The parent of an S-node of T must be a P -node.

• A P -node cannot have two P children5 . (maximum-degree 3 constraint would be violated).

• An S-node can have an arbitrary number of children, however no two consecutive children can be P -nodes. (maximum-degree 3 constraint would be violated).

• If G is biconnected then the root of T must be a P -node.

• If G is not biconnected then the root of T must be either an S-or Q * -node.

Further constraints on the decomposition tree will be exploited for special cases, for example if G is thin. Our construction is recursive and attempts to contain the drawing of the SP lattice in a box spanning the biconvex curves with a balanced number of vertices on each curve and with s and t forming a diagonal of the box. Unfortunately, such a strong invariant cannot be maintained and slightly weaker conditions must be carefully considered.

A series-parallel digraph with poles s and t is bottom-cornered if it is balanced biconvex with a drawing Γ = (n even) or Γ + (n odd) such that:

1. there exists a box (i.e. a convex quadrilateral) B(s, t) with s on λ 1 and t on λ 2 , st forms one diagonal of B, and the other diagonal has one corner on λ 1 and one on λ 2 , and 2. the entire drawing lies inside B. See Fig. 14 for an example. Similarly, a series-parallel digraph with poles s and t is top-cornered if it is balanced biconvex with a drawing Γ = (n even), or Γ + (n odd) such that conditions 1 and 2 hold.

Finally, if a series-parallel graph is both top-cornered and bottom-cornered, it is called double-cornered i.e. if n is odd, there exist two drawings Γ + and Γ + both of which satisfy conditions 1 and 2. See Fig. 10 for example.

In some situations, only weaker conditions on the drawings of a series-parallel graph can be maintained, in which one of t or s is contained strictly inside a box rather than on the diagonal forming the box:

1 . there exists a box B(s, x) with s on λ 1 and x on λ 2 , sx forms one diagonal of B(s, x), and the other diagonal has one corner on λ 1 and one on λ 2 and t is on λ 2 inside B(s, x).

1 . there exists a box B(x, t) with x on λ 1 and t on λ 2 , xt forms one diagonal of B(x, t), and the other diagonal has one corner on λ 1 and one on λ 2 and s is on λ 1 inside B(x, t).

A series-parallel graph with source s and sink t is sink-covered if it is balanced biconvex and conditions 1' and 2 hold (see Fig. 18 for example); similarly, if conditions 1" and 2 hold, then the graph is source-covered.

Theorem 8. The class of 3SP lattices is balanced biconvex.

It is the class of 3SP lattices that we now show to be balanced biconvex. There are several cases to consider depending on whether the graph is biconnected or not, and whether the graph is thin or thick. Our proof is recursive in nature -interior components are replaced by appropriate balanced boxes. Lemmas 9 -15 distinguish and organize these cases and Fig. 8 provides a simple example of each case, the type of drawing obtained, and the prerequisite lemmas used in the proof.

The following invariant is maintained in Lemmas 9, 10 and 11 and is used inductively. Invariant I: Let T be the decomposition tree. For all nodes µ of T with poles s µ and t µ , and for every edge (u, v) of G µ such that u = s µ and v = t µ , u and v are drawn on opposite curves and there exists a box B(u, v) that is empty except for the edge (u, v). Figure 9 provides an example of the technique used. In this example, the 3SP lattice with poles s 1 and t 3 is not biconnected and has one (global) pole of degree 3, and thus Lemma 15 will apply. Since this graph consists of a series of 3 component SP lattices, with poles (s 1 , t 1 ), (t 1 , s 3 ), and (s 3 , t 3 ) Lemmas 10, 9, and 14 respectively are applied. The first two SP lattices can be drawn double-cornered, however the third is bottom-half-cornered. Lemma 9. A simple path consisting of n 2 vertices from s to t is double-cornered.

Proof. Refer to Fig. 10. Let the neighbour of s be s and the neighbour of t be t . If n is even, the path can alternately place vertices on λ 1 and λ 2 , as in Fig. 10. If n is odd, then either s or t can be relocated to the opposite curve to produce top-heavy or bottom-heavy drawings.

Thin 3SP Lattices

This subsection considers those lemmas used for subcases that are thin. Proof. Consider the decomposition tree T of G. Since G is biconnected, the root of T is a P-node. The lemma is proven by induction on the number of P-nodes in T and invariant I is maintained throughout.

Base Case: The simplest form of a biconnected thin 3SP lattice consists of two chains from s to t, i.e. the decomposition tree is a single P-node with two Q * children. Lemma 9 is applied carefully on each chain depending on the parity of the number of vertices on each chain to obtain double-cornered drawings -the cases are shown in Fig. 11.

Let l and r denote the number of vertices on the left and right chains respectively, excluding s and t. Since G is a lattice, l, r ≥ 1. We choose a point on λ 1 for s and a point on λ 2 for t. Box B(s, t) is split into two sub-boxes: B(s, a) and B(b, t), where a is a point on λ 2 left of t and b a point on λ 1 right of s. If l and r are both odd, then n is even and a uniform drawing Γ = is produced with the left chain in box B(s, a) and the right chain in B(b, t) and each box is uniform. If l and r are both even, then n is even and a uniform drawing Γ = is produced with the left chain in box B(s, a) bottom-heavy, and the right chain in B(b, t) top-heavy. In the final case, one of l and r is odd and the other is even, and thus n is odd. A bottom-heavy drawing is produced by drawing the even chain in the box B(s, a) bottom-heavy, and the odd chain in B(b, t) uniform.

A top-heavy drawing uses B(s, a) for the odd chain drawn uniform, and B(b, t) for the even chain drawn top-heavy. Thus, G is double-cornered. Inductive Case: Assume by induction that every biconnected, thin 3SP lattice whose decomposition tree has less than k P -nodes is double-cornered and respects invariant I and let G be a biconnected, thin 3SP lattice whose decomposition tree T has k P -nodes.

Visit T from the leaves to the root and let ν be the first encountered P -node. All children of ν are Q * -nodes. Let µ be the parent of ν and let ρ be the parent of µ in T . Note that µ is an S-node and ρ is a P -node. Furthermore, neither s ν ≡ s µ nor t ν ≡ t µ , since G is a biconnected, thin 3SP graph. Replace G ν with an edge (s ν , t ν ) which we call a virtual edge, and let G be the resulting biconnected, thin 3SP lattice with corresponding decomposition tree T . Since T has fewer than k P -nodes, G is double-cornered and its drawing, Γ , satisfies invariant I. Consider the box B(s ν , t ν ) in Γ and the pertinent graph G ν of ν in T . Applying the base case, G ν can be double-cornered in B(s ν , t ν ), thus providing a double-cornered drawing for G.

We now extend the previous lemma by considering thin 3SP lattices that are not biconnected.

Lemma 11. Let G be a thin 3SP lattice with source s and sink t.

If either deg(s) = deg(t) = 1 or deg(s) = deg(t) = 2 then G is double-cornered.
Proof. Case 1 (both s and t have degree 2): Refer to Fig. 12. If G is biconnected, then the previous lemma applies, so assume G is not biconnected, with decomposition tree T . Let µ be the root of T with children ν 1 , . . . , ν k in left-to-right order. Note that µ is an S-node and both ν 1 and ν k are P -nodes. Also, if ν j and ν l are two P -nodes, there exists a Q * -node ν x with j < x < l, i.e. ν 1 , . . . , ν k is an alternating sequence of P -nodes (odd subscripts) and Q * -nodes (even subscripts). For each P -node ν j , the pertinent graph G νj satisfies Lemma 10 and thus is double-cornered. Each ν j is drawn in a box between the box of G νj-2 and the box of G νj+2 .

For each Q * -node ν i , consider the box B i defined by the diagonally opposite corners t νi-1 and s νi+1 . Draw G νi as described in Lemma 9 and observe that the resulting drawing is double-cornered.

Case 2 (both s and t have degree 1): Refer to Fig. 13. Both the leftmost child ν 1 and rightmost child ν k of µ are Q * -nodes. Consider the subgraph G of G obtained by deleting the pertinent graphs G ν1 and G ν k . Either G satisfies Lemma 10 or the previous case of this proof and thus G can be double-cornered. Let Γ be the corresponding balanced biconvex drawing. We choose a point s on the curve opposite to that of s ν1 , and a point t on the curve opposite to that of t ν k , and so that the box defined by s and t contains Γ . We now draw G ν1 in the box B(s, t ν1 ) and G ν k in the box B(s ν k , t) by using Lemma 9. The resulting drawing is double-cornered. Proof. First case: deg(s) = 1 and deg(t) = 2. Refer to Fig. 14. Let T be the decomposition tree of G. Let µ be the root of T with children ν 1 , . . . , ν k in left-to-right order. Note that µ is an S-node and that ν 1 is a Q * -node and ν k is a P -node. Let s be the (single) neighbour of s. Remove edge (s, s ) from G and call the resulting thin 3SP lattice G . There are now two cases to examine. Assume first that both the source s and the sink t of G are of degree 2. Then G satisfies the condition of Lemma 11 and hence is double-cornered; let Γ be the corresponding drawing. Assume without loss of generality that s is the leftmost vertex on the bottom curve λ 1 . We compute a drawing Γ of G by adding a vertex s left of s on λ 1 and adding the edge (s, s ) This drawing is boxed but bottom-heavy since s is on the same curve as s . Thus Γ is bottom-cornered. Assume now that s has degree 1. Let the decomposition tree of G be T with root µ ; let the children of µ be ν 1 , . . . , ν k . Recall that ν 1 is a Q * -node. Delete G ν 1 from G and call the resulting thin 3SP lattice G . By Lemma 11 G is double-cornered and has a drawing Γ . Assume s ν 2 is on λ 1 . Choose a point s on λ 2 such that B(s , s ν 2 ) does not intersect Γ . Draw G ν 1 in B(s , s ν 2 ) via Lemma 9. Let Γ be the resulting drawing and observe that Γ is uniform but not boxed since s and t are on the same curve. We draw s at a point on λ 1 such that s is left of any other vertex of Γ and add edge ss . Since Γ is uniform, Γ is bottom-cornered.

For the second case, the roles of s and t can be reversed in the above proof to construct a drawing that is top-cornered. Proof. We partition this situation into three cases. Let T be the decomposition tree of G and let µ be the root of T . Case 1: G consists of three series components (S or Q * ) combined in parallel. Note that µ is thus a P -node with exactly three children each of which is an S-node or a Q * -node. Let ν 1 , ν 2 , and ν 3 be the three children of µ in left-to-right order. Observe that for each ν i (i = 1, 2, 3) both the leftmost and rightmost child of ν i is a Q * -node if ν i is a S-node. Let s 3 (resp. t 3 ) be the neighbour of s (resp. t) in G ν3 . Let G be the subgraph of G ν3 obtained by deleting vertices s and t from G ν3 . Graph G is a thin 3SP lattice that satisfies the hypothesis of Lemmas 11, or 12. Let G be the subgraph of G obtained by deleting all vertices of G . Graph G is a biconnected thin 3SP lattice that satisfies the conditions of Lemma 10. We now place 4 points on λ 1 and λ 2 as shown in Fig. 15. Via Lemma 10, we box G into B(s, t) and using one of Lemmas 11, or 12, we box G into B(s 3 , t 3 ) and add the segments corresponding to the edges (s, s 3 ) and (t, t 3 ). Let Γ be the drawing of G and Γ be the drawing of G . If G was boxed into B(s 3 , t 3 ) by using Lemma 12 case 1, then Γ is bottom-heavy. Let n be the number of vertices of G . If n is even, then Γ is bottom-heavy. If n is odd, then by Lemma 10, we can make Γ top-heavy and so Γ is uniform. A similar argument applies if Lemma 12 case 2 is used to compute Γ , in which case Γ is either top-heavy or uniform. Finally, if Lemma 11 applies, then Γ is double-cornered and hence Γ is uniform.

There are two further forms. In both forms, s is the pole of some P -node, as is t.

Case 2: The P -nodes are on opposite sides of the two chains from s to t. See Fig. 16. Here µ is a P -node with children ν 1 and ν 2 in left-to-right order. Also, the leftmost child of ν 1 is a P -node and the rightmost child is a Q * -node. Symmetrically, the leftmost child of ν 2 is a Q * -node and its rightmost child is a P -node.

Let G be the subgraph of G ν1 obtained by deleting t from G ν1 , and let G be the subgraph of G ν2 obtained by deleting s from G ν2 . Let t be the sink of G , and s be the source of G . Observe that G satisfies the hypothesis of either Lemma 11 or Lemma 12 case 2; G satisfies the hypothesis of either Lemma 11 or Lemma 12 case 1. We construct a drawing Γ of G as shown in Fig. 16C, where Γ and Γ represent the drawings of G and G respectively. Let n (resp. n ) be the number of vertices of G (resp. G ). If at least one of n or n is an even integer, then by construction, Γ is either uniform, or top-heavy, or bottom-heavy. Assume that both n and n are odd integers and that G satisfies Lemma 11. We can compute Γ so that it is top-heavy, while Γ will be computed as a bottom-heavy drawing by either Lemma 11 or Lemma 12 case 1. Hence, Γ is uniform. Similarly, if n and n are both odd and G satisfies Lemma 11, Γ is uniform. Finally, if G satisfies Lemma 12 case 2 and G satisfies Lemma 12 case 1, and n and n are both odd, we have that Γ is top-heavy, Γ is bottom-heavy, and thus Γ is uniform. Case 3: The decomposition tree has one chain that starts and ends with Q * -nodes. See Fig. 17. Suppose ν 1 is the node of the decomposition tree that starts and finishes with a P -node, and ν 2 starts and finishes with Q * -nodes. Let G be the subgraph G ν1 and G be the subgraph of G ν2 obtained by deleting s and t from G ν2 . Then G satisfies the conditions of Lemma 11 case 1, and can be drawn double-cornered as Γ . G satisfies Lemma 11, or 12; its drawing, Γ can be drawn and the edges ss and t t can be added. Since Γ is double-cornered, the balancing conditions are easily satisfied. Proof. Case 1: deg(s) = 2 and deg(t) = 3. Let T be the decomposition tree of G and let µ be the root of T . Thus µ is a P -node with exactly two children ν 1 , and ν 2 in left-to-right order. Note that at most one of them can be a Q * -node and that exactly one of them has a P -node as its rightmost child (namely the P -node having t as one of its poles) -assume without loss of generality the latter is ν 1 . Let G be the subgraph of G ν2 obtained by deleting s and t from G ν2 , and let s and t be the source and sink of G . If G satisfies the hypothesis of Lemma 11 or 12 case 2, we construct a sink-covered drawing Γ of G as follows. Choose 4 points s, t, s , t on λ 1 and λ 2 as shown in Fig. 18 Consider now the case in which G satisfies the hypothesis of Lemma 12 case 1. Let n be the number of vertices of G and let n 1 be the number of vertices of G ν1 . If either n or n 1 is an even integer, then a sink-covered drawing Γ of G is constructed as in the previous case; see Fig. 18. Namely, in this case either the drawing of G ν1 or of G is uniform and thus Γ is either uniform or bottom-heavy.

Otherwise, both n and n 1 are odd and we construct a uniform drawing Γ of G as follows. Let G be the subgraph of G obtained by deleting s from G . Let s be the source of G ; observe that the sink of G is t . Since G has an even number of vertices, it has a uniform drawing Γ in a box B(s , t ) and we define this box as shown in Fig. 19. Finally, we add vertex s on the top curve and add segments corresponding to the edges (s, s ) and (s , s ) as in Fig. 19. Observe that the drawing of G ν1 is bottom-heavy and the drawing of G is uniform. Since s is located on the top curve, the drawing Γ is uniform.

For the second case, the roles of s and t can be reversed in the above proof to construct a drawing that is source-covered.

In the final case, G is not biconnected and at least one of the global poles has degree 3.

Lemma 15. Let G be a 3SP lattice with source s and sink t. If deg(s) = 3 or deg(t) = 3 then G is balanced biconvex.

Proof. Refer to Fig. 20. Assume first that neither s nor t have degree 1. If G is biconnected then Lemma 14 or Lemma 13 would apply, so we consider the case that G is not biconnected. Let T be the decomposition tree of G and let µ be the root of T . Then µ is an S-node and has at least three children. In the simplest case, these three children can be labelled ν 1 , ν 2 , ν 3 in left-to-right order with ν 1 and ν 3 being P -nodes, and ν 2 being a Q * -node. In general, the first and last child of µ are P -nodes, but there is a series of children between them starting and ending with Q * -nodes. For convenience, we collapse this intermediate series into a single child ν 2 of root µ. A biconvex drawing Γ of G is computed as follows. Define three boxes, as in Fig. 20. Draw G ν1 in B(s ν1 , t ν1 ), G ν2 in B(s ν2 , t ν2 ), and G ν3 in B(s ν3 , t ν3 ), by using Lemmas 10 and 14 for G ν1 and G ν3 , and using Lemma 11 for G ν2 . Let n 1 be the number of vertices of G ν1 , n 2 be the number of vertices of G ν2 , and n 3 be the number of vertices of G ν3 . Observe that G ν2 satisfies the hypothesis of Lemma 11 and hence if n 2 is odd, the biconvex drawing of G ν2 inside B(s ν2 , t ν2 ) can be chosen to be top-heavy or bottom-heavy. Hence if n 2 is odd, independent of whether n 1 and n 3 are odd or even, Γ can be computed so that the number of vertices in the top curve differs by at most one from the number of vertices in the bottom curve. If n 2 is even, we distinguish two subcases:

• Either n 1 or n 3 is even. In this case, either the drawing of G ν1 or of G ν3 is balanced. Since n 2 is even, also the drawing of G ν2 is balanced. As a result the number of vertices of Γ in the top curve differs by at most one from the number of vertices in the bottom curve.

• Both n 1 and n 3 are odd. If both the drawing Γ 1 of G ν1 is source-covered and the drawing Γ 3 of G ν3 is sink-covered (i.e. Γ 1 is computed via Lemma 14 case 2, and Γ 3 via Lemma 14 case 1) it may happen that Γ 1 and Γ 3 are both top-heavy or both bottom-heavy. If this is the case, then we modify Γ as follows. Refer to Fig. 21 where we assume both are bottom-heavy. We flip Γ 3 , which produces a top-heavy drawing Γ 3 . The flipping operation is possible because within G ν2 , there is a single edge into t ν2 and Lemma 11 ensures that t ν2 is on a corner of the box containing G ν2 . After the flip the drawing of Γ ν2 is also top-heavy but the drawing Γ 1 remains bottom-heavy, so the drawing Γ is uniform. Note that Γ 2 without the shared poles s ν2 and t ν2 remains balanced. The case where Γ 1 and Γ 3 are both top-heavy is symmetric. Finally, observe that if one of Γ 1 and Γ 3 is top-heavy and the other is bottom-heavy, then Γ is already uniform and no flipping operation is required.

t ν1 ≡ s ν2 t ν2 ≡ s ν3 s t t s G ν2 S P P S/Q * A) B) C)
1 Γ 3 t ν2 t ν2 t t → B) A) Γ 1 Γ 3 flip
Now assume s has degree 1 and t has degree 3. The root µ of T has in its simplest form two children ν 1 and ν 2 in left-to-right order, such that ν 1 is a Q * -node, while ν 2 is a P -node. More generally, µ has a series of children starting and finishing with Q * -nodes followed by a P -node. For convenience, we consider the initial series of children as a single child ν 1 , and the final P -node labelled ν 2 . We define two boxes as in Fig. 22. We then compute a cornered drawing Γ 1 of G ν1 in box B(p, q) such that s ≡ p and q ≡ t ν1 . We compute a drawing Γ 2 of G ν2 inside B(q, r). Observe that since G ν2 satisfies the hypothesis of Lemma 14 it is sink-covered and thus t is not mapped to r but is contained in the box B(q, r). Since G ν1 satisfies Lemma 11, we compute Γ 1 so that it is either uniform or top-heavy. Let Γ be the resulting drawing. If Γ 1 and Γ 2 are both uniform, then since t ν1 is a common vertex of both drawings, Γ must be bottom-heavy. If Γ 1 (resp. Γ 2 ) is uniform and Γ 2 (resp. Γ 1 ) is top-heavy then Γ is necessarily uniform.

If Γ 1 and Γ 2 are both top-heavy then Γ is top-heavy. It remains to consider the case that Γ 1 is uniform and Γ 2 is bottom-heavy. This case is handled with a flip operation as demonstrated in Fig. 23. Flipping Γ 2 makes it top-heavy and the resulting drawing becomes uniform. The above lemmas enumerate all possible maximum-degree-3 series-parallel lattices and demonstrate constructively that all such graphs are balanced biconvex, and hence establish Theorem 1. Biconvex pointsets are the only known point-sets of size n that universally support some class of planar graphs other than the outerplanar graphs.

The relevance of the lattice constraint in our technique is evident in the base case of Lemma 10. If one of the two chains in that case were the single edge (s, t), then in order to achieve a balanced partition of the vertices, the drawing would necessarily be either sink-covered or source-covered instead of double-cornered. Subsequent lemmas, such as Lemma 11, rely on their subgraphs being double-cornered in order to produce an appropriate drawing. Fig. 20 displays a situation in which the maximum-degree 3 constraint is critical to our construction. In that figure, neither s nor t is on a diagonal of the box containing the drawing. If in addition, there existed a path s, v, t, the path could not be drawn, even though the graph would be a valid 4SP lattice. It is unlikely that the approach taken in this paper can be modified to accommodate the removal of either of these two constraints. We conjecture that neither the class of 3SP graphs 6 , nor the class of 4SP lattices is balanced biconvex.

It is clear that the class of maximal planar graphs is not balanced biconvex for n 4, since in any biconvex drawing, there exists a face of size at least 4.

Application and Remark

An immediate consequence of Theorem 1 concerns the simultaneous embedding of planar graphs. A set of planar graphs G 1 , . . . , G k (k ≥ 2) each having n vertices has a simultaneous embedding without mapping if there exists a set S of n points that supports the straight-line drawing of G 1 , . . . , G k . It is not known whether such a simultaneous embedding exists when G 1 , . . . , G k are general planar graphs. Braß et al. [START_REF] Braß | On simultaneous planar graph embeddings[END_REF] observed that if 1 is a planar graph and G 2 , . . . , G k are outerplanar graphs, then a simultaneous embedding without mapping for G 1 , . . . , G k exists. The following corollary is a similar observation in this context.

Corollary 16. Let G 1 , . . . , G k (k ≥ 2) be a set of 3SP lattices, all having n vertices. There exists a simultaneous embedding without mapping for the set G 1 , . . . , G k .

Unbalanced Biconvex Point-sets

More generally, biconvex drawings may have h vertices on one curve and nh on the other curve. Any graph that is biconvex drawable (for any value of h) is clearly sub-Hamiltonian, and indeed a stronger condition holds. If the drawing is converted to a book embedding by rotating and translating the vertices on the lower curve, then the resulting book embedding consists of two subgraphs of cycles (one of h vertices and one of nh vertices) each of which is individually outerplanar (edges are crossing-free on the upper side of the book embedding). And edges between the two outerplanar graphs are on the lower side of the spine and are nested and hence do not cross.

We now show that Theorem 8 is tight in the sense that not every (unbalanced) biconvex point-set is universal for the class of 3SP lattices. We first observe a simple property of any biconvex drawing.

Lemma 17. If G is a graph with n vertices that is (k, nk) biconvex drawable, then there exists a set of k vertices in G whose removal results in an outerplanar graph. Theorem 18. For every value of n there exists a 3SP lattice G with n vertices such that in every biconvex drawing of G, there are at least n/7 vertices on both of the two curves.

Proof. Consider a biconvex drawing of the diamond graph D in Fig. 24. Since it is not outerplanar, any biconvex drawing of it requires that both curves contain vertices.

Create a chain of n/7 diamonds and add a path of n -7 • n/7 vertices to create a graph G with n vertices that is a 3SP lattice and requires the removal of at least n/7 vertices to make it outerplanar (since each diamond is independent). Now suppose there exists a biconvex drawing of G in which one of the curves contains fewer than n/7 vertices. By the previous lemma, there then exists some set of fewer than n/7 vertices whose removal yields an outerplanar graph, which is a contradiction.

Characterizing and efficiently recognizing those graphs that can be drawn biconvex (balanced or not), remains an interesting open question.

Conclusions and Open Problems

Our main contributions in this paper are stated in Theorems 1 and 2. In the former, we prove that any balanced biconvex point-set supports the straight-line drawing of any 3SP lattice, and in the latter, we supply universal point-sets for drawings of any planar graph with a small number of bends per edge. Since these results pertain to universal point-sets, they trivially imply corollaries in the context of simultaneous graph drawing (without mapping), since any number of graphs can be simultaneously drawn on a universal point-set.

There remain many open problems including determining whether every pair of planar graphs on n vertices can be simultaneously embedded (with no bends). Closing the gap between the upper and lower bounds of the cardinality of a universal point-set for planar graphs with no bends allowed also remains open. When k bends per edge are permitted, universal point-sets of smaller asymptotic cardinality may be determined for k = 1, 2.

w 0 w 7 w 4 w 5 w 6 w 2 w 3 w 1 Figure 1 :w 7 w 4 w 5 w 6 w 2 w 3 w 1 Figure 2 :

 11712 Figure 1: A graph and a monotone topological book embedding of it.

y 2 = 11 y 3 = 11 2 y 4 = 11 3 y 5 = 11 4 0y 6 = 11 5 y 7 = 11 6 y 8 = 11 7 y 9 = 11 8 y 1 = 1

 2113243546576879811

Figure 3 :

 3 Figure 3: A 2-bend universal point-set for 4-vertex planar graphs. The y-axis is not to scale.

2 .

 2 This implies that ∆ x N 2

∆y ∆x > 1 N

 1 (since ∆ y 1 and ∆ x N 2 ), thus the segments do not properly intersect the slightly concave arc of parabola which support the vertices v i and whose slope is in [-1 N , 1 N ] for x in [0, N ]. Such a universal point-set consists of at most N + N j=1 N j

Figure 5 :

 5 Figure 5: (a) Augmented topological book embedding Γ of the graph Γ of Fig. 1. The isolated dummy vertices are drawn as circles. (b) One-bend drawing of the three top-page or spine-crossing edges incident to v 0 of Γ (the same edges as in Fig.4) in the construction using Θ(n 2 ) candidate bend points, which are drawn as crosses; one arc is drawn curved because the figure is not to scale.

Figure 6 :

 6 Figure 6: Placement of candidate bend points in the strip S i . The figure is not to scale.

Figure 7 :

 7 Figure 7: The segment p i b intersects the segment p j p j+1 . The figure is not to scale.

Figure 8 :

 8 Figure 8: Roadmap of the various cases.

3 Figure 9 :

 39 Figure 9: Example construction. (3 edges are drawn curved for clarity.)

Figure 10 :Figure 11 :

 1011 Figure 10: (Lemma 9) Paths are double-cornered.

Figure 12 : 2 Figure 13 :

 12213 Figure 12: (Lemma 11) Both s and t have degree 2.

Lemma 12 .

 12 Let G be a thin 3SP lattice with source s and sink t. If deg(s) = 1 and deg(t) = 2 (respectively deg(s) = 2 and deg(t) = 1) then G is bottom-cornered (resp. top-cornered).

Figure 14 :

 14 Figure 14: (Lemma 12) Bottom-cornered.

Figure 15 :

 15 Figure 15: (Lemma 13 case 1) A) Sketch of graph; B) Decomposition tree; C) Drawing.

Figure 16 :

 16 Figure 16: (Lemma 13 case 2) s and t both have degree 3. A) Sketch of graph; B) Decomposition tree; C) Drawing.

Lemma 14 .

 14 Let G be a biconnected 3SP lattice with source s and sink t. If deg(s) = 2 and deg(t) = 3 (respectively deg(s) = 3 and deg(t) = 2) then G is sink-covered (resp. source-covered).

2 Figure 18 Figure 19 :

 21819 Figure 18: (Lemma 14) Sketch of graph; Decomposition tree; Drawing.

Figure 20 :

 20 Figure 20: (Lemma 15) Not biconnected and s or t has degree 3. Sketch of graph. Decomposition tree. Drawing

Γ

Figure 21 :

 21 Figure 21: (Lemma 15) Flip operation.

Figure 22 :Figure 23

 2223 Figure 22: (Lemma 15) deg(s)=1, deg(t)=3. Sketch of graph. Decomposition tree. Drawing

Proof.Figure 24 :

 24 Figure 24: Chain of diamonds.

Table 1 :

 1 Summary of results -cardinality of universal point-sets for classes of graphs. The first and last results are well-known. All other results are new.

	Graphs	Number of Points Number of Bends Reference
	outerplanar	n	0	[5]
	3SP lattice	n	0	Thm 1
	planar	O(n)	3	Thm 2
	planar	O(n log n)	2	Thm 2
	planar	O(n 2 / log n)	1	Thm 2
	sub-Hamiltonian	O(n log n)	1	Section 2.2
	sub-Hamiltonian	O(n)	2	Section 2.1
	planar	O(n 2

  Lemma 10. Let G be a biconnected thin 3SP lattice. Then G is double-cornered.

	t	t		t
			t
					t
				s
	s	s	s		s
	Lemma 9	Lemma 10	Lemma 11	Lemma 12 case 1
	double-cornered	double-cornered	double-cornered	bottom-cornered
		uses: Lemma 9	uses: Lemma 10	uses: Lemmas 9,11
		t		t	t	t
	t
			s
	s	s		s	s
	Lemma 12 case 2 top-cornered uses: Lemmas 9,11	Lemma 13 case 1 balanced biconvex uses: Lemmas 10, 11, 12	Lemma 13 case 2,3 balanced biconvex uses: Lemmas 11,12	Lemma 14 case 1 sink-covered uses: Lemmas 11, 12
		t	t	t
	t
				s
			s
	s	s
	Lemma 14 case 2 source-covered uses: Lemmas 11, 12	Lemma 15 balanced biconvex uses: Lemmas 10,11,12,14

  . Via Lemma 12, we draw G ν1 in B(s, t), and

		t
					P
		t
			ν1	S1		S2	ν2
		s	P	...	P	Q *	...	Q *
	A)	s			B)
		t				t
	Γ				Γ
				s
	s	C)

Figure 17: (Lemma 13 case 3) s and t both have degree 3. A) Sketch of graph; B) Decomposition tree; C) Drawing.

During this motion, edges e 1 , . . . , e k may sweep over some vertices in p i-1 , . . . , p i-k+1 . We thus do not ensure that the topology (actually, the isotopy) of the augmented graph Γ is preserved, but this is not an issue since the dummy vertices v i-1 , . . . , v i-k+1 are not part of the input graph G and thus are not ultimately drawn.

To avoid placing a bend point exactly at the location of p i+1 , we specify that the bend point at height p i+1 be moved to the left until it is slightly to the right of p i+1 .

We actually place these bend points infinitesimally close to the right of the vertical line through q i , only to ensure in the following arguments that these points belong to S i (which is open on the left).

i.e. coalescing

Furthermore, only at the topmost level can a P -node have even a single child that is a P -node

3.4. Thick 3SP LatticesThe next sequence of lemmas pertains to the cases when the global poles have degree 3. The drawings obtained rely on the previous lemmas and are balanced biconvex, but may not be double-cornered. We start with the cases when G is biconnected. Lemma 13. Let G be a biconnected 3SP lattice with source s and sink t. If deg(s) = deg(t) = 3 then G is balanced biconvex.

by using either Lemma 11 or 12, we draw G in B(s , t ). Finally, we add the segments corresponding to the edges (s, s ) and (t, t ). The resulting drawing Γ is sink-covered by construction -t is inside the box B(s, t ) and since the drawing of G is either uniform or top-heavy, while the drawing of G ν1 is either uniform or bottom-heavy, the total drawing is not unbalanced.

rather than lattices

Acknowledgement

The work in this paper was initiated at the 2011 McGill/INRIA/UVictoria Bellairs workshop. Comments and discussion with the other participants is gratefully acknowledged. In particular, we thank Sue Whitesides and Raimund Seidel for their valuable input.

$ Research supported by NSERC, and by MIUR of Italy under project AlgoDEEP prot. 2008TFBWL4.