Geometric biplane graphs II: graph augmentation

Geometric Biplane Graphs II: Graph Augmentation ∗ Alfredo Garc´ıa1Ferran Hurtado2Matias Korman3,4Inˆes Matos5 Maria Saumell6Rodrigo I. Silveira5,2Javier Tejel1Csaba D. T´oth7 Abstract We study biplane graphs drawn on a finite point set Sin the plane in general position. This is the family of geometric graphs whose vertex set is Sand which can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6- connected biplane graph. Furthermore, we show that every plane graph (other than a wheel or a fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges. 1 Introduction In a geometric graph G= (V, E), the vertices are distinct points in the plane in general position (that is, no three points in Sare collinear) and the edges are straight line segments between pairs of vertices. A plane graph is a geometric graph in which no two edges cross. It is well known that every planar graph can be realized as a plane graph by F´ary’s theorem [14]. We consider a generalization of plane graphs. A geometric graph G= (V, E) is k-plane for some k∈Nif its edge set can be partitioned into kdisjoint subsets, E=E1· ∪. . . · ∪Ek, such that G1= (V, E1), . . . , Gk= (V, Ek) are all plane graphs, where · ∪represents the disjoint union. For a finite point set Sin the plane in general position, denote by Gk(S) the family of k-plane graphs with vertex set S. With this terminology, G1(S) is the family of plane graphs with vertex set S, and G2(S) is the family of 2-plane graphs (also known as biplane graphs) with vertex set S. We contrast several combinatorial properties of plane graphs G1(S) and biplane graphs G2(S) for point sets Sin this and a companion paper [18]. For example, it is well known that the vertex connectivity of every plane graph in G1(S) is at most 5, but it is natural to expect that the larger family G2(S) contains graphs of higher vertex connectivity. A graph G= (V, E) in G2(S) is maximal if there is no graph G0= (V, E0) in G2(S) such that E⊂E0. In [18] we compare combinatorial properties of maximal biplane graphs in G2(S) with triangulations in G1(S), and show that there are arbitrarily large point sets Sfor which G2(S) contains an 11- connected graph, but no biplane graph is 12-connected. In this paper, we study the maximum ∗A preliminary version of this paper has been presented at the Mexican Conference on Discrete Mathematics and Computational Geometry, Oaxaca, M´exico, November 2013 [19]. 1Departamento de M´etodos Estad´ısticos, IUMA, Universidad de Zaragoza, Zaragoza, Spain. [email protected],[email protected]. 2Departament de Matem`atica Aplicada II, Universitat Polit`ecnica de Catalunya, Barcelona, Spain. [email protected],[email protected]. 3National Institute of Informatics (NII), Tokyo, Japan. [email protected] 4Kawarabayashi Large Graph Project, ERATO, Japan Science and Technology Agency (JST). 5Departamento de Matem´atica & CIDMA, Universidade de Aveiro, Aveiro, Portugal, [email protected], [email protected]. 6Department of Mathematics and European Centre of Excellence NTIS (New Technologies for the Information Society), University of West Bohemia, Pilsen, Czech Republic. [email protected]. 7Department of Mathematics, California State University Northridge, Los Angeles, USA. [email protected]. 1 vertex connectivity of a graph in G2(S) for a given point set S. We also consider closely related connectivity augmentation problems. We refer to [18] and the references therein for a broad overview of further related work.1 Organization. The problem of constructing a plane graph with the largest possible vertex- or edge-connectivity on a given point set has received significant attention [10, 15, 16]. The combinatorial aspect of the problem asks for characterizing the point sets that admit graphs of a certain connectivity, and the algorithmic aspect is to develop algorithms for computing highly connected graphs. These are the topics we study in Section 2, considering biplane graphs instead of plane graphs. A closely related family of problems is the graph augmentation, in which one would like to add new edges, ideally as few as possible, to a given graph in such a way that some desired property is achieved. There has been extensive work on augmenting disconnected plane graphs to connected ones (see [22] for a recent survey) or achieving good connectivity properties [1, 2, 3, 12, 24, 25, 27]. For abstract graphs, this corresponds to the classical connectivity augmentation problem in combinatorial optimization and has a rich history, as well. In Section 3, we consider several problems on augmenting plane graphs to biplane graphs with higher connectivity. We conclude in Section 4 with some final remarks and open problems. 2 Drawing Biplane Graphs from Scratch Given a set Sof npoints in general position, we would like to construct a graph G∈ G2(S) with high vertex connectivity κ(G). We determine the maximum κ(G) that can be attained for every (sufficiently large) point set S. We also consider the special case that the point set Sis in convex position. For comparison, we briefly review analogous results for plane graphs G1(S) on a given point set S. Refer to [22] for a survey. Every set of n≥3 points in general position admits a spanning cycle (a polygonization of S), which is 2-connected. For points in convex position, every plane graph has a vertex of degree 2, so in this case κ(G) = 2 is the best possible value over all G∈ G1(S). Since every planar graph has a vertex of degree not greater than 5, the vertex connectivity of every graph in G1(S) is at most 5. It is known that every set of n≥4 points not in convex position admits a 3-connected triangulation. Additionally, every set of n≥6 points whose convex hull is a triangle admits a 4-connected triangulation, provided that a certain condition is satisfied (see [10] for details). Characterizations for point sets in general position that admit 4-connected triangulations have only recently been proposed [11, 16, 17], and no characterization is known for 5-connectivity. 2.1 Point Sets in Convex Position We begin with the special case of points in convex position. It turns out that all biplane graphs on a point set Sin convex position are planar. Moreover, the maximum number of edges (resp., the maximum vertex connectivity) of a graph in G2(S) is the same as the maximum attained in the family of planar graphs with |S|vertices. Lemma 1. Let Sbe a set of npoints in the plane in convex position. (i) Every graph in G2(S)is planar (as an abstract graph). 1Note: The companion paper [18] contains a larger introduction to the concept of biplane graphs, comparing it with other related concepts such as the geometric thickness and others. Ideally, both papers will appear in the same journal issue. Preliminary versions of both papers have been presented at the Mexican Conference on Discrete Mathematics and Computational Geometry (Oaxaca, 2013) [18, 19]. To avoid repetition, a complete introduction is presented in the companion paper, and here we include only a brief self-contained introduction. 2 (ii) If G= (V, E)is a Hamiltonian planar (abstract) graph with nvertices, then it has a geometric realization in G2(S). Remark: In [6], Bernhart and Kainen show two results (Lemma 2.1 and Theorem 2.5), given in terms of book thickness, that are more general than Lemma 1. Since it is straightforward to see that Lemma 1 follows from those results, we omit its proof. Note, however, that not every planar graph can be realized as a biplane graph on a point set in convex position. If Sis in convex position, then the boundary of the convex hull ch(S) forms a Hamiltonian cycle in every maximal (i.e., edge-maximal) graph in G2(S). Hence every maximal graph in G2(S) is planar and Hamiltonian. However, there are maximal planar graphs (triangulations) that are not Hamiltonian. (It is NP-complete to decide whether a maximal planar graphs is Hamiltonian [9, 30].) These planar graphs cannot be realized as a biplane graph on a point set in convex position. We can now characterize the maximum vertex connectivity of a graph in G2(S) when Sis in convex position. Theorem 1. Let Sbe a set of npoints in convex position. • G2(S)contains a 4-connected graph if and only if n≥6. • G2(S)contains a 5-connected graph if and only if n= 12 or n≥14. • G2(S)contains no 6-connected graphs for any n∈N. Proof. It is well known that every 4-connected planar graph Ghas a Hamiltonian cycle [29]. By Lemma 1(ii), it is enough to establish the existence or nonexistence of a k-connected planar graph for a given nfor k= 4, 5, and 6. By Lemma 1(i), every graph in G2(S) is planar. Every planar graph on n≥3 vertices has at most 3n−6 edges, and the sum of vertex degrees is at most 6n−12. In a k-connected graph, the degree of every vertex is at least k, and the sum of vertex degrees is at least kn. Comparing these bounds, we have kn ≤6n−12 or 12/(6 −k)≤n. It follows that no planar graph is 6-connected, every 5-connected planar graph has at least 12 vertices, and every 4-connected planar graph has at least 6 vertices. It is easy to see that there is a 4-connected planar graph on nvertices for every n≥6. Specifically, the 1-skeleton of the octahedron is 4-connected with 6 vertices; and a vertex split operation can increase the number of vertices by one while maintaining 4-connectivity and planarity. In an embedding of a 4-connected planar graph on nvertices, this split operation removes an edge (u, v) and adds a new vertex connected to all the vertices of the two faces adjacent to (u, v). Barnette [4] and Butler [8] independently designed algorithms for generating all 5- connected triangulations, using simple operations starting from the icosahedron (see also [7]). The 1-skeleton of the icosahedron is 5-connected with 12 vertices, and each operation either splits a vertex of degree 6 or higher, or simultaneously splits two adjacent vertices. Hence there is a 5-connected planar graph for n= 12 and for every n≥14 (but not for n= 13). Remark. We have shown that G2(S) contains 4- and 5-connected graphs when n≥6 and n≥14, respectively. The existence proof in Theorem 1 can be turned into an O(n)-time algorithm for constructing such biplane graphs. Here we present explicit constructions for 5-connected biplane graphs for points in convex position when n= 12 and n≥14. The construction in Figure 1 (left) works when nis even and n≥12. It is based on two plane spanning trees, T1and T2, and the edges of ch(S). Each spanning tree consists of two stars with 3 leaves each, connected by a zig-zag path. Let us assume that the points are numbered clockwise. Then, the centers of the stars of T1(the nondashed spanning tree) are placed at opposite points, say iand i+n/2, the leaves of the first star are placed at points i+ 1, i + 2 3 and i+ 3 and the leaves of the second star are placed at points i+n/2+1, i +n/2 + 2 and i+n/2+3. The zig-zag path connects the centers of the stars visiting alternatively the points {i+ 4, . . . , i +n/2−1}and the points {i−1, i −2, . . . , i +n/2+4}. Tree T2(the dashed spanning tree) is symmetric to T1, where point i+n/2 + 1 is the image of point iand i+ 1 is the image of point i+n/2. Note that the only common edges to both trees are (i, i + 1) and (i+n/2, i +n/2 + 1). The construction in Figure 1 (right) works when nis odd and n≥15. It is analogous to the previous construction, but one of the stars in T1and T2has 4 leaves instead of 3. Figure 1: Two 5-connected biplane graphs for points in convex position. 2.2 Point Sets in General Position In this section we find the largest k∈Nsuch that every sufficiently large point set Sin general position admits a k-connected biplane graph. Hutchinson et al. [23] proved that every biplane graph in G2(S) has at most 6n−18 edges for n≥8. In particular, this implies that every biplane graph contains a vertex of degree 11 or less, hence k≤11. Theorem 1 directly improves the bound to k≤5. We now show that this bound is tight, that is, every sufficiently large point set Sadmits a 5-connected biplane graph. Theorem 2. Let Sbe a set of npoints in the plane in general position. If Scontains at least 14 points in convex position, then there is a 5-connected graph in G2(S). Erd˝os and Szekeres proved that for every k∈Nthere is an integer f(k) such that every set of at least f(k) points in the plane in general position contains a subset of kpoints in convex position. They conjectured f(k) = 2k−2+ 1, and showed f(k)≥2k−2+ 1. The currently best upper bound [28] for k≥7 is f(k)≤2k−5 k−2+ 1. When k= 14, this result implies that every set Sof npoints in general position has a subset of at least 14 points in convex position for n≥2·14−5 14−2+ 1 = 1352079. Therefore, every sufficiently large point set Sin general position satisfies the condition in Theorem 2. Corollary 1. If Sis a set of n≥1352079 points in the plane in general position, then there is a 5-connected biplane graph in G2(S). Outline. The remainder of Section 2.2 is devoted to the proof of Theorem 2. Our approach is as follows: given a point set S, let S0⊂Sbe a largest subset of points in convex position (in case of ties, choose a set S0whose convex hull has the largest area). By assumption, we have |S0| ≥ 14. By Theorem 1, S0admits a 5-connected biplane graph G0. We increment G0with new vertices from S\S0, maintaining a 5-connected biplane graph, in 3 phases: we first insert the points lying in the interior of ch(S0), then the vertices of ch(S), and finally all remaining points (which lie in the exterior of ch(S0)). We continue with the details. 4 Preliminaries. To ensure that we maintain 5-connectivity, we use the following well-known properties of graphs. Property 1. Let G= (V, E)be a k-connected (abstract) graph. Augment Gwith a new vertex xjoined to kvertices of G. Then the new graph on vertex set V∪ {x}is also k-connected. Property 2. Let G= (V, E)be a k-connected (abstract) graph in which vw is an edge. Remove edge vw from G, and augment it with a new vertex xjoined to both v,wand to k−2 additional vertices. Then the new graph with vertex set V∪ {x}is also k-connected. Since adding edges to a graph can only increase the vertex connectivity, we may assume in each phase of our algorithm that we have started with a 5-connected maximal biplane graph. Thus, we can rely on the following two structural results for maximal biplane graphs from the companion paper [18]. Lemma 2. [18] Let G= (S, E)be a maximal biplane graph in G2(S). Then there are two triangulations T1= (S, E1)and T2= (S, E2)such that E=E1∪E2. Given an edge e∈Ein a triangulation T= (S, E), we denote by Q(e) the quadrilateral formed by the two triangles adjacent to e. Note that Q(e) is not defined if eis an edge of ch(S). An edge eis flippable if and only if Q(e) is a convex quadrilateral. Lemma 3. [18] Let G= (S, E)be a maximal biplane graph in G2(S)such that E=E1∪E2, where T1= (S, E1)and T2= (S, E2)are two triangulations. Every edge of E1∩E2is flippable in neither T1nor T2. Furthermore, every maximal biplane graph with n≥4vertices is 3- connected. The following tool (Lemma 4) is crucial for increasing the vertex degree of a vertex in a triangulation. This tool is applicable to all triangulations other than the wheel. (A wheel is a triangulation on npoints such that n−1 points are in convex position and one point lies in the interior of ch(S), the points on the convex hull induce a cycle on the boundary of ch(S) and the interior point is joined to all other n−1 points.) Lemma 4. Let T= (S, E)be a triangulation other than the wheel. Let s∈Sbe a point in the interior of ch(S)such that it is adjacent to a vertex on the boundary of ch(S), and the graph induced by its neighbors in Tis a cycle. Then Tcontains a triangle incident to sin which the edge opposite to sis flippable. Proof. Denote the neighbors of sby v1, v2, . . . , vk∈S, for some k≥3, in counterclockwise order. Since Tis not a wheel, some edges of the cycle (v1, . . . , vk) are not on the boundary of ch(S). Without loss of generality, assume that v1is a vertex of ch(S) but v1v2is not on the boundary of ch(S). Note that Q(v1v2) is defined, and it has a convex vertex at v1. Starting with i= 1 we use the following iterative argument: we know that Q(vivi+1) is defined and has a convex vertex at vi. If vivi+1 is flippable, we are done. Otherwise, Q(vivi+1) is a nonconvex quadrilateral and has a reflex vertex at vi+1. It follows that vi+1 is in the interior of ch(S), and thus Q(vi+1vi+2) is defined. Since the neighbors of sinduce a cycle, we have vivi+2 6∈ E. Therefore vivi+1 and vi+1vi+2 are not adjacent to a common triangle. Since vi+1 is a reflex vertex of Q(vivi+1), it must be a convex vertex of Q(vi+1vi+2). Thus, we can increment the value of iand repeat the same argument. This process ends as soon as we find a flippable edge or when we conclude that none of the edges vivi+1,i= 1, . . . , k −1 is flippable. However, in the latter case, the above argument implies that v1is in the interior of ch(S), contradicting our initial assumption. Inserting interior vertices. The following lemma allows augmenting a 5-connected biplane graph with an interior point. 5 ss Figure 2: Left: 5-connected biplane graph on 15 points. Middle: point slies in the interior of two gray triangles, which jointly have 5 distinct vertices. Right: point sis now part of the 5-connected biplane graph. Lemma 5. Let G= (S, E)be a 5-connected biplane graph. Denote by Sint ⊂Sthe points lying in the interior of ch(S), and let s6∈ Sbe a point such that sis in the interior of ch(S) but in the exterior of ch(Sint). Then a 5-connected biplane graph on S∪{s}can be constructed from G= (S, E)by adding at least 5 new edges incident to sand deleting at most one edge of E. Proof. Augment G= (S, E) to a 5-connected maximal biplane graph b G= (S, b E) by adding dummy edges, if necessary. By Lemma 2, b Gis the union of two triangulations, T1and T2. Point slies in the interior of some triangles ∆1and ∆2in the two triangulations (∆1and ∆2 may share vertices and edges). Since slies in the exterior of ch(Sint), at least one vertex of ∆1(resp., ∆2) is on the boundary of ch(S). Let us augment T1(resp., T2) with vertex sand three edges joining sto the vertices of ∆1(resp., ∆2) to a new triangulation T0 1(resp., T0 2) in which sis adjacent to a vertex of ch(S). We distinguish three cases based on the total number of distinct vertices of ∆1and ∆2. Case 1: ∆1and ∆2jointly have 5 or 6 distinct vertices. We have joined sto at least 5 distinct vertices of G(Figure 2). The union of T0 1and T0 2is biplane and 5-connected by Property 1. Case 2: ∆1and ∆2jointly have 4 distinct vertices. In this case, ∆1and ∆2share an edge (see Figure 3), say ∆1=v1v2v3and ∆2=v1v2v4. Since sis in the interior of both ∆1and ∆2, the points v3and v4are on the same side of the line v1v2. Since v4is in the exterior of ∆1and v3is in the exterior of ∆2, the convex hull ch(v1, v2, v3, v4) is a convex quadrilateral. Without loss of generality, we may assume ch(v1, v2, v3, v4) = (v1, v2, v3, v4) in counterclockwise order. By Lemma 4, T0 1(resp., T0 2) has a flippable edge e0 1(resp., e0 2) in a triangle opposite to s. If flipping edge e0 1in T0 1or edge e0 2in T0 2increases the degree of sto 5, then perform the edge flip. By Property 2, the union of the two triangulations is a 5-connected biplane graph. Assume now that neither flipping e0 1in T0 1nor e0 2in T0 2increases the degree of sto 5. This implies that the third vertex of the triangles adjacent to e0 1and e0 2, respectively, are v4and v3. That is, the 4-cycle (v1, v2, v3, v4) is part of both triangulations T0 1and T0 2. After flipping e0 1in T0 1, the cycle (v1, v2, v3, v4) has a flippable edge ˆeby Lemma 4. We can flip ˆein T0 1to increase the degree of sto 5, while retaining edge ˆein the other triangulation T0 2. By Property 2, the union of these two triangulations is a 5-connected biplane graph. Case 3: ∆1and ∆2jointly have 3 distinct vertices. In this case, ∆1= ∆2, say ∆1= ∆2=v1v2v3. By Lemma 4, T0 1(resp., T0 2) has a flippable edge e0 1(resp., e0 2) in a triangle opposite to s. If e0 16=e0 2, then we can flip each edge in its corresponding triangulation, while 6 ss e0 1 ∆1 ∆2 Figure 3: Left: 5-connected biplane graph on 16 points. Middle: point slies in the interior of triangles ∆1and ∆2, which share an edge, and e0 1is a flippable edge adjacent to ∆1. Right: point sis now part of the 5-connected biplane graph. keeping it in the other triangulation. Thus the degree of sincreased to 5, and the union of the two triangulations forms a 5-connected biplane graph by Property 1. If e0 1=e0 2but the two flips together increase the degree of sto 5, then the union of these two triangulations is a 5-connected biplane graph by Property 2 (since the two flips together remove at most one edge e0 1=e0 2from G). It remains to consider the case that e0 1=e0 2, say e0 1=e0 2=v2v3, and the two flips together would only increase the degree of sto 4. That is, ∆1= ∆2=v1v2v3is adjacent to the same triangle, say v2v3v4, in both T1and T2. In particular, the 4-cycle (v1, v2, v4, v3) is part of both triangulations. We claim that the 4-cycle (v1, v2, v4, v3) has no external chords in at least one of T1and T2. Clearly, the claim is true when (v1, v2, v4, v3) is a convex quadrilateral. Let us assume to the contrary that ch(v1, v2, v3, v4) is a triangle, say ∆ = v1v2v4, and suppose that the external chord v1v4belongs to both T1and T2, so ∆ = v1v2v4is part of both triangulations. If ∆ = ch(S), then the path v4v3v1separates v2from the rest of the vertices in G, and if ∆6= ch(S), then v3lies in the interior of ∆ and some point of Slies in its exterior. It follows that either the path v4v3v1or ∆ is a 3-vertex cut in G, contradicting our initial assumption that Gis 5-connected, and proving the claim. Without loss of generality, we may now assume that the 4-cycle (v1, v2, v4, v3) has no external chord in T1, and hence in T0 1either. After flipping e0 1=v2v3in T0 1, the 4-cycle (v1, v2, v3, v4) is an induced subgraph in the resulting triangulation T00 1, and this cycle has a flippable edge ˆeby Lemma 4. Flipping ˆe in T00 1increases the degree of sto 5, while the edge ˆeremains part of the triangulation T0 2. By Property 1, the union of these two triangulations is a 5-connected biplane graph. This completes the proof in case 3. In all three cases, we have augmented b G= (S, b E) with a new vertex sby adding at least 5 new edges incident to sand deleting at most one edge of b E. Finally, delete all remaining dummy edges (that have not been flipped in the above procedure). Since the original graph Gwas 5-connected without the dummy edges, Properties 1 and 2 imply that the resulting biplane graph on S∪ {s}is also 5-connected. Inserting vertices of the convex hull. We now introduce a method to augment a 5-connected biplane graph G= (Sa, E) with a set Sbof points in the exterior of ch(Sa). We would like the new edges to be disjoint from the interior of ch(Sa) (although some edge flips will be necessary). For this purpose, we introduce the concept of visibility. We say that a point sin the exterior of ch(Sa)sees an edge uv of ch(Sa) if the triangle suv is also in the exterior of ch(Sa). A line segment st in the exterior of ch(Sa)sees uv if both sand tsee uv. Note that every exterior point smust see a subset of consecutive edges of ch(Sa), but cannot see all edges of ch(Sa). 7 We show below (Lemma 7) that a 5-connected biplane graph G= (Sa, E) can be augmented with a set Sbof exterior points if Saand Sbsatisfy the following property (see Fig. 4). Property 3. Let Saand Sbbe disjoint point sets such that • |ch(Sa)| ≥ 4; •every point s∈Sbis a vertex of ch(Sa∪Sb); •if kpoints in Sbare consecutive vertices of ch(Sa∪Sb), then they jointly see at least k+ 2 consecutive edges of ch(Sa), for all positive integers k < |ch(Sa)|. Property 3 implies a similar property for edges (rather than vertices) under some additional conditions. This will allow the application of Hall’s theorem to match the edges of ch(Sb) to some edges of ch(Sa). Lemma 6. Assume that Saand Sbsatisfy Property 3, Salies in the interior of ch(Sb), and every two consecutive vertices of ch(Sb)see some common edge of ch(Sa). Then every kedges of ch(Sb)jointly see at least kedges of ch(Sa). Proof. When k= 1, the claim holds by our assumption that every two consecutive vertices of ch(Sb) see some common edge of ch(Sa). Suppose, to the contrary, that there is a counterexample for some k > 1. That is, there is a set Hbof k≥2 edges of ch(Sb) that jointly only see a set Haof edges of ch(Sa) with |Ha|< k. Consider a counterexample where |Ha| is minimal. We may assume that Hbis the maximal set of edges of ch(Sb) that jointly see exactly the edges in Ha. If two edges h1, h2∈Hbsee the same h∈Ha, then every edge along ch(Sb) between h1and h2(say, in counterclockwise order) can see only edges of ch(Sa) that are already visible to h1or h2. Thus every edge in Hais visible from a sequence of consecutive edges in Hb. It is clear that every edge h∈Hbsees a set of consecutive edges of ch(Sa). Consequently, we may assume that both Hband Haconsist of consecutive edges (along ch(Sb) and ch(Sa), respectively). The kconsecutive edges in Hbform a path P. By Property 3, the k−1 interior vertices of this path jointly see at least k+ 1 consecutive edges of ch(Sa). These edges of ch(Sa) are each visible by at least two (consecutive) vertices of the path P: either by two interior vertices or by one interior vertex and an endpoint of P. Hence |Ha| ≥ k+ 1, contradicting our initial assumption |Ha|< k. Using the preceding observations, we present our main tool for augmenting a 5-connected biplane graph with exterior points. Lemma 7. Let Saand Sbbe two point sets satisfying Property 3, and let G= (Sa, E)be a 5-connected biplane graph in G2(Sa). Then there exists a 5-connected biplane graph G0= (Sa∪Sb, E0)such that E⊂E0. Proof. We may assume, by adding dummy edges if necessary, that Gis a 5-connected maximal biplane graph. We consider two cases depending on whether the conditions of Lemma 6 are satisfied or not. Case 1: Salies in the interior of ch(Sb)and every two consecutive vertices of ch(Sb)see some common edge of ch(Sa).Denote the vertices of ch(Sa) by a1, . . . , ap in counterclockwise order, and let b1, . . . , bqdenote the vertices of ch(Sb) in counterclockwise order. By Lemma 6, every set of kedges of ch(Sb) jointly see at least kedges of ch(Sa). Thus, using Hall’s theorem, we can assign every edge of ch(Sb) to a unique visible edge of ch(Sa). We have q≥3, and Property 3 yields p≥5. Given an index i∈ {1, . . . , q}, let jbe the index such that the edge bibi+1 is assigned to ajaj+1. By hypothesis, the quadrilateral bibi+1aj+1ajmust be convex. We look for an assignment in which these quadrilaterals have pairwise disjoint interiors. If two such quadrilaterals, say bibi+1aj+1ajand bi0bi0+1aj0+1aj0, 8 a3 a8 b2 b3 b4 b5 b6 b1 b7 a12 a10 a11 a9 a7 a5 a6 a4 a2 a1 a8 b0 1 a0 4 a0 2 a0 3 a0 1 a7 a1 a2 b0 2 b3 b4 a0 5 ch(Sa)ch(Sa) a5 a6 a3 a4 b1 b2 a14 a13 a9 Figure 4: Left: the boundaries of ch(Sa) and ch(Sb) are disjoint. Right: the points in Sbare partitioned into two treatable chains. cross (have intersecting interiors), then bibi+1 also sees aj0+1aj0and bi0bi0+1 also sees aj+1aj, thus we can exchange the edges assigned to bibi+1 and bi0bi0+1, reducing the total number of crossing quadrilaterals by at least one. We can now assume that the edges of ch(Sb) and the assigned edges of ch(Sa) form interior-disjoint convex quadrilaterals. We describe how to augment Gwith the vertices b1, . . . , bq. In one layer, add all edges of the cycle (b1, . . . , bq). If edge bibi+1 is assigned to ajaj+1, then join bito ajand aj+1 in one layer, and bi+1 to ajin the other layer (where ap+1 =a1and bq+1 =b1). Denote the resulting graph by G0(Figure 4, left). All new edges are disjoint from the interior of ch(Sa), and the edges in each layer are noncrossing, thus G0is biplane. Each biis joined to at least three vertices of the cycle (a1, . . . , ap), which is part of the 5-connected graph G, and to its two neighbors in the cycle (b1, . . . , bq). In particular, each bihas vertex-independent paths to five distinct vertices of the 5-connected graph G. It follows that G0is 5-connected. Case 2: Sadoes not lie in the interior of ch(Sb)or two consecutive vertices of ch(Sb) see disjoint sets of edges of ch(Sa).In this case, we partition the vertices Sbinto maximal chains of consecutive vertices along ch(Sa∪Sb) such that every two consecutive vertices of a chain see a common edge of ch(Sa); and then successively augment Gwith the vertices of the chains. We say that a counterclockwise chain c= (b1, . . . , bq) along the boundary of ch(Sa∪Sb) is treatable if bi∈Sbfor i= 1, . . . , q and every edge of csees some edge of ch(Sa). A treatable chain cis maximal if it is not contained in a longer treatable chain. Let c= (b1, . . . , bq) be a maximal treatable path, and let (a1, . . . , ap) be the counterclockwise sequence of vertices of ch(Sa) jointly visible from c. Property 3 implies p≥q+ 3 (in particular, p≥4, since b1alone sees at least 3 edges, hence at least 4 vertices of ch(Sa)). We distinguish two subcases depending on the length of c. Case 2(a): q≥2.To each bi(i= 1, . . . , q) we assign a sequence of visible edges of (a1, . . . , ap) such that the sequences are disjoint and cover all edges of (a1, . . . , ap). Assign to b1the edges a1a2,a2a3, and any subsequent edge of (a1, . . . , ap) that is not visible to b2. For i= 2, . . . , q, assign to vertex bithe counterclockwise first edge of ch(Sa) that is visible to biand has not been assigned to any previous vertex bj,i<j; furthermore, assign to biany subsequent edge of (a1, . . . , ap) that is not visible to any subsequent vertex bj,j > i. (See Figure 4, right.) We have assigned at least 2 edges to b1by construction, and at least one edge to all other vertices bi(i= 2, . . . , q) by Property 3. By the maximality of the sequence b1, . . . , bq, every two consecutive vertices see at least one edge of ch(Sa). Using this fact, 9 Now, we construct a triangulation from T2by adding vertex vand some incident edges, and possibly deleting some of the edges of T2, as explained next. Refer to Figure 7(a). Let ∆1= (u, w, v0) be the triangle of T2adjacent to uw and let ∆2= (u, x, v0) and ∆3= (w, y, v0) be (if they exist) the two triangles of T2adjacent to triangle ∆1. Note that at least one of them must exist. First, we add ∆ to T2, obtaining a triangulation T0 2on the npoints. By Lemma 10, we can flip edge uw in T0 2and, after flipping it, we can flip one of the edges uv0 and v0w. Assume without loss of generality that we flip uv0. Then, from T0 2, we remove edges uw and uv0and we add edges vv0and vx, obtaining a new triangulation T0on the npoints. By Property 2, T∪T0is 4-connected. Indeed, we have obtained T∪T0from the 4-connected graph T1∪T2by removing at most one edge, uv0(since edge uw is always in both T1and T2) and adding a new vertex vjoined to u,v0and two additional vertices, xand w. This completes the proof of Case 2.1. Case 2.2: There is no leaf cell of size 3. Our proof in this case is similar to Case 2.1, but the constructions are now a bit more complicated. Since Econtains at least one chord of ch(S), the convex hull has at least 4 vertices and there are at least two leaf cells. Since no leaf cell is a triangle, there are at least two points in the interior of ch(S). Assume first that n= 6. In this case, there are exactly four hull vertices, hence there is a unique chord, and exactly one interior vertex on each side of the chord (Figure 6(d)). Consider the four vertices disjoint from the chord, on each side: they admit two disjoint edges between vertices on opposite sides of the chord. These edges augment Tinto a 4-connected biplane graph, as required. Assume now n≥7. Let `be a leaf cell of minimal size (i.e., with minimum number of vertices). This leaf cell is defined by a chord uw, and its size |S`|is at least 4. If we remove the points in S`except for uand w, then all vertices of the second smallest leaf cell survive, and so we are left with at least |S`| ≥ 4 vertices. We obtain a triangulation T1on the n− |S`|+ 2 remaining points. Note that, if |S`|= 4, then n− |S`|+ 2 ≥5 because n≥7, and if |S`| ≥ 5, then n− |S`|+ 2 ≥ |S`| ≥ 5. Therefore, if T1is neither a wheel nor a fan, we can apply induction to the triangulation T1. First, observe that T1cannot be a fan, otherwise it would have two leaves of size 3, and one of them would be a leaf cell of size 3 in T, contradicting the assumption that there is no such leaf cell. Assume that T1is a wheel. Refer to Figure 7(b). Let vdenote the center of the wheel T1, and let the neighbors of vbe denoted w, v1, . . . , vk, u in clockwise order. Note that k≥2 because n− |S`|+ 2 ≥5 and so the degree of vis at least 4. Let hbe the line through v1and u, and let u06=wbe the first point in S`hit when we rotate hclockwise about v1. Now, let T0contain edges connecting u0to v1, . . . , vk; and v1to all the vertices in S`\ {u, w}. Since T`(the graph induced by S`in T) is 3-connected, then by connecting each vertex in S` (except for uand w) to a vertex outside of S`, each separating triangle and bichord of T`is properly crossed. In addition, every bichord incident to vis properly crossed by an edge of type u0vj. Finally, the only chord of T, the chord uw, is properly crossed by two new edges, for example, edges v1u00 and vku0(where u00 is an arbitrary vertex of `other than u,wand u0, which must exist because |S`| ≥ 4). Therefore, (S, E ∪E0) is 4-connected. We can now assume that T1is a 3-connected triangulation other than a wheel or a 2- connected triangulation other than a fan. By induction, there is a plane graph T2on the n− |S`|+ 2 remaining points such that T1∪T2is a 4-connected biplane graph. We may assume that T2is a triangulation. We modify T2to construct a new plane graph T0on all n points as follows (see Figure 7(c)). Similarly to Case 2.1, let ∆1= (u, w, v0) be the triangle of T2adjacent to the chord uw and let ∆2= (u, x, v0) and ∆3= (w, y, v0) be (if they exist) the two triangles of T2adjacent to triangle ∆1. Note that at least one of them must exist. Let ∆ = (u, w, v) be the triangle of T`adjacent to edge uw. Vertex vmust be an interior vertex because T`is 3-connected. By adding ∆ to T2, we obtain a new triangulation T0 2and, 16 again, by Lemma 10, we can flip edge uw in T0 2. We can then flip one of the edges uv0and v0w. Assume without loss of generality that we flip uv0. We construct a plane graph T0from T2on the npoints by removing edges uw and uv0, adding edges xv and v0v, and connecting all remaining points in S`to one of xand v0, depending on which side of the angle bisector of ∠(x, v, v0) they lie on. We have added an edge of type v0v00 or xv00 adjacent to each vertex v00 in S`, where v00 6∈ {u, w}. We claim that T∪T0is 4-connected. We need to show that every chord, every bichord and every separating triangle of Tis properly crossed. By induction, T1∪T2is 4-connected. In the case that edge uv0is removed from the 4-connected graph T1∪T2, the path (u, v, v0) establishes a new connection from uto v0. Note that, since triangle ∆1is empty, any chord properly crossed by edge uv0is also properly crossed by edge v0v. Consequently, every separating triangle, every bichord and every chord of T1, is properly crossed at least once or twice, as required. However, it is possible that a bichord of Tconsists of two edges of T1but it is not a bichord in T1. One possibility for such a bichord is (u, z, w), where ∆0= (u, w, z) is the triangle of T1adjacent to the chord uw and zis an interior point (possibly, z=v0). See Figure 7(c). This bichord (if it exists) is properly crossed by the edge xv. The other possibility is that edge uw belongs to a bichord of Tconsisting of two chords, say wu and uw0. In this case, since there are at least two points on each side of uw0(there are no leaf cells of size 3 on one of the sides, and wand zare on the other side), by induction, there are at least two disjoint edges crossing uw0, one of them properly crossing the bichord. Moreover, every separating triangle and every bichord in T`is properly crossed by an edge of type v0v00 or xv00, where v00 is in S`. Finally, we show that the chord uw is properly crossed by two disjoint edges. For an arbitrary vertex v00 in S`\ {u, v, w}, if v00 is connected to x, then both xv00 and v0vcross uw, and if v00 is connected to v0, then both xv and v0v00 cross uw. We have seen (Lemmas 8 and 9) that a fan and a wheel, respectively, are 2- and 3- connected triangulations that cannot be augmented to a 4-connected biplane graph by adding a second triangulation. We now show that there are 4-connected triangulations that cannot be augmented to 5-connected biplane graphs by adding a second triangulation. Theorem 4. There exist arbitrarily large point sets Sand 4-connected triangulations T= (S, E)such that for every triangulation T0= (S, E0), the biplane graph (S, E ∪E0)is not 5-connected. Proof. Our construction is shown in Figure 8, where the initial triangulation Tappears in Figure 8(a) drawn with black edges. The point set has two main clusters. The top cluster consists of 4k−3 points in convex position, with 2kpoints in a lower chain x1, . . . , x2k, and 2k−3 additional in an upper chain x1, y1, . . . , y2k−3, x2k. The parameter k∈Ncan be made arbitrarily large. The lower cluster consists of 7 points as shown in Figure 8(a). The bottom cluster is sufficiently far below the top cluster so that any new edge between a point yiand a point in the bottom cluster crosses the edge xi+1xi+2. Intuitively, the bottom cluster is a “big dot” far below the top cluster. It is not difficult to verify that Tis 4-connected (i.e., it has no chords, bichords, or separating triangles). Our argument crucially depends on four 4-vertex cuts in T, each consists of the vertices of a path with 3 edges. We call these the four critical trichords of T. Two such critical trichords are highlighted in Figure 8(b): one from uto v, and one from sto x1. The other two are symmetric (one also goes from uto v, and the other from sto x2k). Suppose, to the contrary, that there is a triangulation T0= (S, E0) such that G= (S, E∪E0) is 5-connected. Then the vertices on opposite sides of each critical trichord must be connected by at least one edge in E0. If an edge e∈E0crosses the trichord from sto x1, then emust be incident to u, and it must cross either edge aor edge b. If ecrosses b, it is easy to verify that, no matter what the other endpoint of eis (there are only three possibilities), it is impossible to add pairwise noncrossing edges that cross both trichords between uand v, and the trichord 17 v u v s x1 x3 y1 x2 y2 y2k−3 x2k (a) u x1 s v x3 y1 x4 x2k y2k−3 (c) u s a b x1 x3 y1 x2 y2 y2k−3 x2k (b) Figure 8: (a) Overview of the construction. The top convex cluster is sufficiently far from the bottom part. (b) Schematic view of the construction, highlighting two of the four critical trichords of T. (c) To increase the degree of the vertices in the convex cluster, more edges are needed. However, vertex y2k−3cannot connect to any other vertex. from sto x2k, but do not cross e. We conclude that emust cross aand hence is incident to some vertex in the top cluster. If Gis 5-connected, every vertex must have degree at least 5 in G, and so every vertex in {x1, y1, y2, . . . , y2k−3, x2k}must be incident to at least one new edge in E0\E. Consider an edge e1∈E0\Eincident to y1. If e1connects y1to any vertex in {y3, . . . , y2k−3}, then the vertices on or above e1form a convex polygon within in the top cluster whose triangulation in T0would necessarily contain two ears; therefore at least one vertex yiwould not be incident to any new edge. If e1connects y1to any vertex in the bottom cluster, then e1crosses edge x2x3. Since eand e1do not cross, we have either e=ux2or e=e1=uy1: In any case, x1 cannot be incident to any new edge in E0\E. Therefore, e1must connect y1to some vertex in the chain (x4, x5, . . . , x2k). Assume that e1connects y1to xj(1) for some j(1) ≥4. Using a similar reasoning, y2should connect to xj(2) for j(2) ≥5, and in general, yishould connect to xj(i)for some j(i)≥i+ 3, see Figure 8(c). Since the top chain has three fewer vertices than the bottom chain, then y2k−3cannot be connected to any other vertex by a new edge, and its vertex degree is 4 in G, contradicting our assumption that Gis 5-connected. 3.2 Minimal Augmentation Given a plane graph G= (S, E), we wish to augment Gwith a minimal set of new edges E0 such that we obtain a k-connected biplane graph G= (S, E ∪E0) for some target value k. In this section we present an efficient solution (Lemma 12) when k= 3 and Gis a triangulation. We start with a helpful lemma about augmenting a plane tree to 2-edge-connectivity. Lemma 11. Given a plane tree H= (S, E)with nvertices and mleaves, let L⊂Sbe the set of mleaves of H. In O(n+mlog m)time, one can find a set E0of dm/2epairwise noncrossing edges among the leaves of Hsuch that (S, E ∪E0)is a 2-edge-connected biplane graph. Moreover, if the mleaves are in convex position, then E0can be found in O(n)time, provided that the clockwise ordering of the leaves along their convex hull is given. It is well known (see for example [13]) that an abstract tree with mleaves can be augmented to a 2-edge-connected graph by adding dm/2enew edges among its leaves. However, establishing the noncrossing condition requires a proof. 18 Proof. Choose a root r∈Sarbitrarily, and let Tbe the rooted tree obtained from H. We denote by a≺bif ais a descendent of bin the rooted tree T. For two leaves u, v ∈L, denote by lca(u, v) their lowest common ancestor in T. For a rooted tree with O(n) vertices, there is a data structure that can report lca(u, v) for any query vertex pair {u, v}in O(1) time after O(n) time preprocessing [5, 20, 26]. We construct the set of new edges recursively. Initialize E0to be the empty set. If |L| ∈ {2,3}, then add an arbitrary spanning tree of Lwith d|L|/2eedges to E0. While |L|>3, repeat the following loop: Let vbe an arbitrary vertex of ch(L) other than the root, and let u∈Land w∈Lbe the two vertices of ch(L) adjacent to v. If lca(u, v)lca(v, w), then put edge uv into E0, and remove both uand vfrom L. Otherwise, when lca(u, v)≺lca(v, w), put edge vw into E0, and remove both vand wfrom L. In each loop, the algorithm selects an edge from the boundary of the convex hull of L, which cannot cross any edge selected in a later loop. It follows that E0consists of pairwise noncrossing edges. The algorithm adds one edge for each pair of vertices until |L|drops below 4, and then it uses d|L|/2eedges. So we have |E0|=dm/2e. It remains to show that (S, E ∪E0) is 2-edge-connected. Let ab be an edge of Twith a≺b, and let Lab denote the set of leaves that are the descendants of b. Consider the loop of the algorithm in which the last leaf of Lab is removed from L. The algorithm connects a leaf in La,b to another leaf, which cannot be in La,b (recall that the algorithm compares two alternatives). Thus in this loop, the algorithm adds an edge that induces a cycle containing ab. Therefore, every edge ab is contained in a cycle in (S, E ∪E0), thus it is 2-edge-connected. The convex hull ch(L) can be maintained by the semi-dynamic data structure by Hershberger and Suri [21] in O(mlog m) time, hence the total running time is O(n+mlog m). Finally, observe that, when the mleaves are in convex position, ch(L) can be updated in constant time after removing two consecutive vertices of ch(L), without using the semidynamic data structure by Hershberger and Suri. Therefore, in this case, the set E0of pairwise noncrossing edges can be found in O(n) time, after computing ch(L) in O(mlog m) preprocessing time. Lemma 12. Given a triangulation G= (S, E), with n≥3vertices, one can find a minimal set of edges E0such that G0= (S, E ∪E0)is a 3-connected biplane graph in O(n)time, after computing ch(S)in O(nlog n)preprocessing time. Proof. If the given triangulation Gis not 3-connected, then it must contain 2-vertex cuts. Recall that a set {u, v} ⊂ Sis a 2-vertex cut if and only if uv ∈Eis a chord of ch(S). The biplane graph G0= (S, E ∪E0) will be 3-connected if each chord of ch(S) in Eis crossed by at least one edge in E0. Similar to the proof of Theorem 3, we construct a dual graph H. The chords of ch(S) in Edecompose ch(S) into convex cells. The nodes of Hcorrespond to the cells, and two nodes are joined by an edge in Hif and only if the corresponding cells share a chord. Clearly, His a tree (see the thick edges in Figure 9), and can be easily constructed in O(n) time from G. The leaves of Hcorrespond to leaf cells. Each leaf `of His associated with the set of vertices R`⊂Sthat lie in the interior or on the boundary of the cell, excluding the endpoints of the chord on the boundary of the cell. Note that distinct leaves of Hare associated with disjoint vertex sets (i.e., R`∩R`0=∅for `6=`0). Consider the chords that lie on the boundaries of the leaf cells. These chords are in convex position, thus any new edge can cross at most two of them. It follows that we need to add at least dm/2enew edges, where mdenotes the number of leaves of H. We now show that dm/2enew edges suffice, and can be computed in linear time. For each leaf `of H, pick a point v`∈R`on the boundary of ch(S). We refer to this point as the representative of `. Embed Hin the plane such that every leaf `is embedded at point v`, and every nonleaf node is embedded at an arbitrary point in the interior of its cell. Clearly, this embedding can be constructed in O(n) time, after computing ch(S). 19 Figure 9: A point set, the associated graph H(thick edges), and the additional edges to obtain 3-connectivity (dashed edges). By Lemma 11, the embedding of Hcan be augmented to a 2-edge-connected graph H0by a set E0of dm/2enoncrossing edges (dashed edges in Figure 9) between the leaves (that are representatives from S) in O(n) time, because all the representatives are in convex position. We claim that (S, E ∪E0) is 3-connected. Every 2-vertex cut of Gis a chord cof ch(S) that corresponds to an edge ecof the embedding of H. When the embedding of His augmented to H0,ecbecomes part of at least one cycle in H0, and each of these cycles contains exactly one edge from E0. Observe that, if Cis a cycle in H0that contains both ecand a new edge e∈E0, then all edges of C(except for e) correspond to chords, which are crossed by edge e. In particular, ecrosses chord c. Since H0is 2-edge-connected, every edge of the embedding of Hbelongs to a cycle in H0, so every chord of ch(S) is crossed by some edge of E0. In the above argument, we have added one edge for every two leaf cells of H. Associate to each leaf `of Hall vertices in R`and the two endpoints of the chord. Every vertex of ch(S) is the endpoint of at most two chords that bound leaf cells. Therefore, one can assign to each leaf cell at least two vertices (a vertex of R`and half of each endpoint of the chord on the boundary of the leaf). It follows that there are at most bn/2cleaf cells. This bound is tight, since the chords of the leaf cells may form a cycle of n/2 edges. We obtain an upper bound for the total number of edges added in Lemma 12. Corollary 2. Every triangulation G= (S, E)on n≥3points can be augmented to a 3- connected biplane graph by adding at most dbn/2c/2e=bn+2 4cnew edges. 4 Conclusions We have presented several results on the maximum vertex-connectivity attained by biplane graphs on a point set S, either by constructing a graph from scratch (starting from the empty graph) or by combining a given plane graph with a new plane graph. Our proofs are constructive and lead to polynomial-time algorithms for constructing the new edges. Moreover, when the starting graph is a triangulation, we have also presented an efficient algorithm for finding the minimum number of edges needed to augment the triangulation to a 3-connected biplane graph. Our Theorem 2 shows that G2(S) contains a 5-connected graph if the point set Scontains 14 points in convex position, which is guaranteed only for very large sets (roughly 1.3·106 points or more). Recent research indicates that the threshold can be reduced to 137 and perhaps to 27 using a so-called U-condition [16] or combining 4-connected plane graphs [17] with stars when no 14 points are in convex position. The improved bound heavily relies on our Theorem 2, and will be the subject of a future paper. In Theorem 3, we have shown that every triangulation (other than the wheel and the fan) can be augmented to a 4-connected biplane graph by adding a second plane graph on the 20 same point set; but a second layer is not always sufficient to augment a plane graph to a 5-connected biplane graph. In general, we do not know whether every sufficiently large plane triangulation, other than the fan, can be augmented to a 5-connected biplane graph when the new edges are not required to form a plane graph. Several computational problems related to our results remain open. Is there a polynomialtime algorithm that, given a point set S, finds a 5-connected biplane graph with the minimum number of edges or reports that none exists? Is there a polynomial-time algorithm for finding the minimum number of edges to augment a given 3-connected plane graph with n≥6 vertices into a 4-connected biplane graph? Acknowledgements A. G., F. H., M. K., R.I. S. and J. T. were partially supported by ESF EUROCORES programme EuroGIGA, CRP ComPoSe: grant EUI-EURC-2011-4306, and by project MINECO MTM2012-30951/FEDER. F. H., and R.I. S. were also supported by project Gen. Cat. DGR 2009SGR1040. A. G. and J. T. were also supported by project E58(ESF)-DGA. M. K. was supported by the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia and the European Union. I. M. was supported by FEDER funds through COMPETE–Operational Programme Factors of Competitiveness, CIDMA and FCT within project PEst-C/MAT/UI4106/2011 with COMPETE number FCOMP-01-0124- FEDER-022690. M. S. was supported by the project NEXLIZ - CZ.1.07/2.3.00/30.0038, which is co-financed by the European Social Fund and the state budget of the Czech Republic, and by ESF EuroGIGA project ComPoSe as F.R.S.-FNRS - EUROGIGA NR 13604. R. S. was funded by Portuguese funds through CIDMA (Center for Research and Development in Mathematics and Applications) and FCT (Funda¸c˜ao para a Ciˆencia e a Tecnologia), within project PEst- OE/MAT/UI4106/2014, and by FCT grant SFRH/BPD/88455/2012. C. T. was supported in part by NSERC (RGPIN 35586) and NSF (CCF-0830734). References [1] M. Abellanas, A. Garc´ıa, F. Hurtado, J. Tejel, and J. Urrutia, Augmenting the connectivity of geometric graphs, Comput. Geom. Theory Appl. 40 (3) (2008), 220–230. [2] M. Al-Jubeh, G. Barequet, M. Ishaque, D. L. Souvaine, C. D. T´oth, and A. Winslow, Constrained tri-connected planar straight line graphs, in Thirty Essays on Geometric Graph Theory (J. Pach, ed.), Springer, 2013, pp. 49–70. [3] M. Al-Jubeh, M. Ishaque, K. R´edei, D. L. Souvaine, C. D. T´oth, and P. Valtr, Augmenting the edge connectivity of planar straight line graphs to three, Algorithmica 61 (4) (2011), 971–999. [4] D. Barnette, On generating planar graphs, Discrete Mathematics 7(1974), 199–208. [5] M. A. Bender and M. Farach-Colton, The LCA problem revisited, in Proc. LATIN 2000, LNCS 1776, Springer, 2000, pp. 88–94. [6] F. Bernhart and P.C. Kainen, The book thickness of a graph, Journal of Combinatorial Theory, Series B 27 (1979), 320–331. [7] G. Brinkmann and B. D. McKay, Construction of planar triangulations with minimum degree 5, Discrete Mathematics 301 (2–3) (2005), 147–163. [8] J. W. Butler, A generation procedure for the simple 3-polytopes with cyclically 5- connected graphs, Canadian Journal of Mathematics XXVI(3) (1974), 686–708. [9] V. Chv´atal, Hamiltonian cycles, in The Traveling Salesman Problem (E.L.Lawler et al., eds.), John Wiley, 1985, pp. 403–429. 21 [10] T. K. Dey, M. B. Dillencourt, S. K. Ghosh and J. M. Cahill, Triangulating with high connectivity, Computational Geometry: Theory and Applications 8(1997), 39–56. [11] A. A. Diwan, S. K. Ghosh, and B. Roy, Four-connected triangulations of planar point sets, manuscript, 2013, arXiv:1310.1726. [12] S. Dobrev, E. Kranakis, D. Krizanc O. Morales Ponce and L. Stacho, Approximating the edge length of 2-edge connected planar geometric graphs on a set of points, in Proc. LATIN 2012, LNCS 7256, Springer, 2012, pp. 255–266. [13] K.P. Eswaran and R.E. Tarjan, Augmentation problems, SIAM Journal of Computing 5 (1976), 653–665. [14] I. F´ary, On straight-line representation of planar graphs, Acta Scientiarum Mathematicarum (Szeged) 11 (1948), 229–233. [15] A. Garc´ıa, C. Huemer, F. Hurtado, J. Tejel, and P. Valtr, On triconnected and cubic plane graphs on given point sets, Comput. Geom. Theory Appl. 42 (9) (2009), 913–922. [16] A. Garc´ıa, C. Huemer, J. Tejel, and P. Valtr, On 4-connected geometric graphs, in: Proc. XV Spanish Meeting on Computational Geometry, 2013, pp. 123–126. [17] A. Garc´ıa, C. Huemer, J. Tejel, and P. Valtr, Personal communication (manuscript in preparation). [18] A. Garc´ıa, F. Hurtado, M. Korman, I. Matos, M. Saumell, R. I. Silveira, J. Tejel, and C. D. T´oth, Geometric biplane graphs I: Maximal graphs, manuscript, 2013. (Extended abstract in Proc. Mexican Conference on Discrete Mathematics and Computational Geometry, Oaxaca, M´exico, November 2013, pp. 123–134.) [19] A. Garc´ıa, F. Hurtado, M. Korman, I. Matos, M. Saumell, R. I. Silveira, J. Tejel, and C. D. T´oth, Geometric biplane graphs II: Graph augmentation (extended abstract), in Proc. Mexican Conference on Discrete Mathematics and Computational Geometry, Oaxaca, M´exico, November 2013, pp. 223–234. [20] D. Harel and R. E. Tarjan, Fast algorithms for finding nearest common ancestors, SIAM J. Comput. 13 (2) (1984), 338–355. [21] J. Hershberger and S. Suri, Applications of a semi-dynamic convex hull algorithm, BIT 32 (2) (1992), 249–267 [22] F. Hurtado and C. D. T´oth, Plane geometric graph augmentation: a generic perspective, in Thirty Essays on Geometric Graph Theory (J. Pach, ed.), Springer, 2013, pp. 327–354. [23] J. P. Hutchinson, T. C. Shermer and A. Vince, On representations of some thickness-two graphs, Computational Geometry: Theory and Applications 13 (1999), 161–171. [24] E. Kranakis, D. Krizanc, O. Morales Ponce and L. Stacho, Bounded length, 2-edge augmantation of geometric planar graphs, Discrete Math., Alg. and Appl. 4(2012), 385–397. [25] I. Rutter and A. Wolff, Augmenting the connectivity of planar and geometric graphs, Journal of Graph Algorithms and Applications 16 (2) (2012), 599–628. [26] B. Schieber and U. Vishkin, On finding lowest common ancestors: simplification and parallelization SIAM J. Comput 17 (6) (1988), 1253-–1262. [27] C. D. T´oth, Connectivity augmentation in planar straight line graphs, European J. of Combinatorics,33 (3) (2012), 408–425. [28] G. T´oth and P. Valtr, The Erd˝os-Szekeres theorem: upper bounds and related results, in Combinatorial and Computational Geometry, vol. 52 of MSRI Publications, 2005, pp. 557–568. [29] W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956), 99–116. [30] A. Wigderson, The complexity of the Hamiltonian circuit problem for maximal planar graphs, Technical Report 298, Princeton University, EECS Department, 1982. 22