On 4-connected geometric graphs

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 On 4-connected geometric graphs Alfredo García ∗ 1 , Clemens Huemer † 2 , Javier Tejel ‡ 1 , and Pavel Valtr § 3 1 Dept. Métodos Estadísticos. Universidad de Zaragoza. Spain. 2 Dept. Matemàtica Aplicada IV. Universitat Politècnica Catalunya, Spain. 3 Department of Applied Mathematics. Charles University, Czech Republic. Abstract Given a set S of n points in the plane, in this paper we give a necessary and sometimes sucient condition to build a 4-connected non-crossing geometric graph on S . Introduction Given a set S of n points in the plane, a non-crossing geometric graph on S is a graph in which its vertices are the points of S and its edges are straight-line segments between these points such that no edge passes through a vertex dierent from its endpoints and any two edges may intersect only at a common endpoint. Since all the geometric graphs considered in this paper are non-crossing, throughout the paper we will use the term geometric graph, meaning that the geometric graph is non-crossing. The study of geometric graphs and, in particular, the study of problems on how to embed planar graphs as geometric graphs on given point sets is a very active area of research (for a review on geometric graphs and some related topics, see for example [1, 4]). One of these problems is the problem of building geometric graphs with a certain connectivity on a set of points S .We will say that a set of points S is k -connectible if it admits a k -connected geometric graph on it. For k= 1,2,3 , it is well-known when S is k -connectible and how to build a k -connected geometric graph (see [2, 3]). Given S , it is enough to build a non-crossing tree on S (for example the minimum spanning tree of ∗ Email: olav[email protected]. Research partially supported by projects Gob. Arag. E58-DGA, MINECO MTM2012-30951 and ESF EUROCORES programme EuroGIGA, CRP ComPoSe: MICINN Project EUI-EURC-2011-4306. † Email: [email protected]. Research partially supported by projects MINECO MTM2012-30951 and ESF EUROCORES programme EuroGIGA, CRP ComPoSe: MICINN Project EUI-EURC-2011-4306. ‡ Email: [email protected]. Research partially supported by projects Gob. Arag. E58-DGA, MINECO MTM2012-30951 and ESF EUROCORES programme EuroGIGA, CRP ComPoSe: MICINN Project EUI-EURC-2011-4306. § Email: [email protected].cuni.cz. S ) when k= 1 , and it is enough to build a simple polygonization of S when k= 2 . For the case k= 3 , the only set of points not admitting a 3-connected geometric graph is the convex case. Otherwise, in [3] the authors give an algorithm to build a 3-connected geometric graph using max{d3n/2e, n+m−1} edges, where m is the number of points on the boundary of the convex hull of S , and they prove that there is no 3-connected plane graph on S with less edges. However, for k > 3 , little is known about when a set of points is k -connectible. For k= 4 , Dey et al. [2] show points sets that do not admit any 4-connected geometric graph on them and they provide a necessary and sucient condition for point sets whose convex hull consists of exactly three points. A general characterization of 4or 5-connectible sets of points is not known. In this paper, we study sets of points that are 4connectible. We dene a condition (the U-condition) that any set of points must satisfy to be 4-connectible and we show that the U-condition is always sucient for some sets of points. By denoting the convex hull of S by CH(S) and the set of points on the boundary of the convex hull of S by H(S) , if Q=H(S) , I=S\Q and P=H(I) , then the U-condition is sucient for sets of points in which Q∪P satises the U-condition. 1 The U-condition In this section, we will dene the U-condition and we will see that it is a necessary condition to get 4connected geometric graphs. A subset C of points of Q is connected if it consists of consecutive points of Q . We will denote by h(C) the number of connected components of a subset C of Q . Denition 1 A set S of points satises the Ucondition if i) |Q| ≤ |I| ii) For any set C⊂Q , |H(S\C)| ≤ |I|+h(C) . Lemma 2 Every 4-connectible set S satises the Ucondition. 123 On 4-connected geometric graphs Proof. Let us prove that if G(S) is a 4-connected graph drawn on S , then S has to satisfy i) and ii). In G(S) , each vertex must have degree at least 4, and since there are no edges linking non-consecutive points of Q (otherwise G(S) would not be 3-connected), then there are at least 2|Q| edges having an endpoint in Q and the other one in I . On the other hand, as G(S) is 4-connected, each point of I can be linked to a maximum of two (and consecutive) points of Q . Hence, at most there are 2|I| edges with an endpoint in Q and the other one in I . Therefore, 2|Q| ≤ 2|I| and the necessity of i) is proved. Now, suppose C6=∅ is a subset of points of Q and C1, C2, . . . , Ch(C) are its connected components. Let us denote by Ci the points of Q placed between component Ci and component Ci+1 . Thus, Q consists of the points C1, C1, C2, C2, . . . , Ch(C), Ch(C) in this order. When we remove the points of C , all the points in the subsets Ci remain in H(S\C) and perhaps, between Ci and Ci+1 (mod h(C) ), a subset Ii+1 of points of I appears in H(S\C) . Either Ii is empty or it consists of consecutive points of P (see Figure 1). Let I be the set I\(I1∪I2∪. . . ∪Ih(C)) and let C be the set Q\C . Observe that proving ii) is equivalent to proving |C|≤|I|+h(C) . C2 C1 I2 I1q1 qk p1 C2 I3 I C3 C1 C3 Figure 1: Illustration of Lemma 2. Suppose that I1={p1, . . . , pk0} is nonempty and let q1 and qk be the points of C placed on the boundary of CH(S\C) just after and before the points of I1 , respectively (see Figure 1). Without loss of generality, we can assume that G(S) is a triangulation. So, each point of I1 must be connected in G(S) to some point of C1 and, since G(S) is 4-connected, they cannot be connected to a point of C , except for the edges pk0q1 and qkp1 . Therefore, for an edge linking a point of C with an interior point (at least 2|C| edges), the interior endpoint must be in I\I1 , except for the two mentioned edges pk0q1 and qkp1 . We can repeat the same reasoning for every subset Ii , obtaining that there must be at least 2|C| − 2h(C) edges with an endpoint in C and the other one in I . On the other hand, as before, there are at most 2|I| connections of this type, so it follows that 2|C| − 2h(C)≤2|I| .  Observe that if |Q|= 3 , then |I|+1 = n−2 . Hence, part ii) can only fail if we remove one point q of Q and the boundary of CH(S\q) contains all the remaining points. In [2], this is the condition that is proved to be necessary and sucient to build a 4-connected geometric graph (in fact a triangulation) on S . Lastly, let us point out that, given S , checking whether S satises the U-condition or not can be done in O(|Q|+|P|) steps, after calculating Q and P . The algorithm is based in the observation (not easy to prove) that it is not necessary to compute CH(S\C) for all the possible subsets C , but only for a linear number of them. 2 Some 4-connectible sets In this section, we will give some sets of points for which the U-condition is sucient. In particular, we will see that if Q∪P satises the U-condition for a set of points S , then S is 4-connectible. We will use Q ( P ) to refer to the convex polygon dened by the points of Q ( P ). Let us start with the case in which S is precisely Q∪P and |Q|=|P| . Lemma 3 Let Q={q1, . . . , qn} be a set of points in convex position and let P={p1, . . . , pn} be another set of points in convex position such that P is inside Q . Suppose that the set of points S=Q∪P satises the U-condition. Then S is 4-connectible. Proof. Let M be the region CH(Q)\CH(P) . To prove the lemma, it is enough to obtain a crossing free zig-zag cycle Z=piqjpi+1qj+1 . . . pi−1qj−1pi such that its edges are in M , because then the edges of Z and the edges of Q and P dene a 4-connected graph (see Figure 2). P Q Z Figure 2: A 4-connected geometric graph when S= Q∪P . We will say that a triangle qjpipi+1 is legal if it is contained in region M . Proving the lemma is equivalent to proving that there is a sequence of n 124 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 consecutive legal triangles qjpipi+1, qj+1pi+1pi+2,..., qj+n−1pi+n−1pi+n , where points with equal subscripts modulo n are considered identical. Let us assume that {q1, . . . , qm} is the set of clockwise points of Q on the left of the line p1p2 . The following algorithm computes a sequence of n consecutive legal triangles. Begin Do i=j= 2 While (i≤n) Do (* Invariant (1) : Triangles of the sequence qj−1pi−1pi, qj−2pi−2pi−1, . . . , qj−(i−1)p1p2 are legal.*) If ( Triangle qjpipi+1 is legal ) then Do {i=i+ 1; j=j+ 1} Else (* Invariant (2) : qj is between qj−1 and the rst crossing of line pipi+1 with Q *) Do j=j+ 1 End of While (* After nishing the algorithm, all the triangles of the sequence qj−np1p2, qj−(n−1)p2p3, . . . , qj−1pnp1 are legal.*) Let us see that assertions (1) and (2) are always true, so they are invariant in the algorithm. Trivially, assertion (1) is true the rst time because q1p1p2 is legal by hypothesis. Now, suppose that assertions (1) and (2) are true in the iterations 1,2, . . . , k of the loop and let us prove that (1) is still true in the following iteration. If we begin the k+ 1 iteration after exploring a legal triangle in the iteration k , then clearly (1) is still true (because we are adding the last explored triangle to a previous legal sequence). If we begin iteration k+1 after exploring an illegal triangle qjpipi+1 in iteration k , then we need to check that the new sequence ST =qjpi−1pi, . . . , qj−i+2p1p2 of triangles (where j has been increased by one) is legal. Assume to the contrary that in this sequence ST a rst illegal triangle qj−hpi−h−1pi−h appears, so qj−h is the rst clockwise point of Q on the right of line pi−h−1pi−h . By removing the points of Q from qj+1 to qj−h−1 (see Figure 3 left), then the points of P from pi to pi−h ( n−h+1 points) and the points of Q from qj−h to qj ( h+1 points) appear in the boundary of the new convex hull, contradicting the U-condition (at most n+ 1 points can appear in the boundary of the new convex hull). Therefore (1) is invariant. For assertion (2), the rst time that the algorithm goes to the else branch, we are exploring the illegal triangle qjpjpj+1 , being the triangles qj−1pj−1pj, . . . , q1p1p2 legal. If qj was on the right side of pipi+1 and after the second crossing point of that line with Q , then, by removing the points of Q from q1 to qj−1 (remember that q1 is the rst point of Q to the left of p1p2 ), the U-condition is contradicted because in the boundary of the new convex hull n+ 2 P Qpi pi+1 pi−1 qj qj−hpi−h+1 pi−h pi pi+1 qj qj−1 qj1 pi1 pi1+1 pi1−1 Q1 P pi−h−1 Q1 Q Figure 3: Illustration of Lemma 3. Left: Supposing qj−h is on the right of pi−h−1pi−h , the U-condition fails if Q1 is removed. Right: Supposing qj is on the right of pipi+1 , the U-condition fails if Q1 is removed. points appear (the points of P from p1 to pj+1 and the points of Q from qj to qn ). Therefore, in the rst visit to the else branch assertion (2) is true. Suppose that the last illegal triangle explored is qj1pi1pi1+1 and the algorithm is exploring a new illegal triangle qjpipi+1 . As (2) was true in the previous iterations, point qj1 has to be placed between qj1−1 and the rst crossing of line pi1pi1+1 with Q . After exploring this triangle, subscript j1 is increased by one, and then h operations (perhaps h= 0 ) of increasing both subscripts ( i and j ) are done. Therefore, it must be j=j1+h+ 1 and i=i1+h , for some h≥0 . Since (1) is invariant, the h+ 1 triangles qj−1pi−1pi, qj−2pi−2pi−1, . . . , qj1pi1−1pi1 are legal. Therefore, if qj is placed after the second crossing of line pipi+1 with Q , then, by removing the h points of Q from qj1+1 to qj−1 , the h+ 2 points of P from pi1+1 to pi+1 appear in the boundary of the new convex hull, contradicting the U-condition (see Figure 3 right). Hence, (2) is invariant. Lastly, since (1) is invariant and the last triangle, qj−(i−1)p1p2 , is legal, then the subscript j−i+ 1 has to be between 1 and m . This implies that j≤i+m−1 in the algorithm. Hence, the algorithm can go to the else branch a maximum of m−1 times, and nishes in a maximum number of n+m−1 steps. When the algorithm nishes, then i=n+ 1 and the triangles of the sequence qj−1pnpn+1, qj−2pn−1pn, . . . , qj−np1p2 are legal because (1) is invariant.  Now, assume that |Q|=|P| , Q∪P satises the U-condition, there are more points inside P and that |Q|>3 (the case |Q|= 3 was solved in [2]). To get a 4-connected geometric graph, we proceed as follows. First draw the zig-zag including alternatively the points of P and Q , according to the previous lemma. Then, take a diagonal of P , for example diagonal p1p3 . This diagonal divides P into two subpolygons P1= {p1, p3, . . . , pn, p1} and P0 1={p1, p2, p3, p1} . If the interior I(P1) of P1 is nonempty, then let P2 be the convex polygon dened by the points H(I(P1)∪p1, p3) . If the interior I(P2) of this polygon is again nonempty, 125 On 4-connected geometric graphs then we dene P3 as the convex polygon dened by the points H(I(P2)∪p1, p3) , and so on, until we obtain an empty convex polygon Ph . Thus, we have a sequence Ph⊂Ph−1⊂. . . ⊂P2⊂P1 of nested polygons (see Figure 4 left). The same process can be done starting at P0 1 , obtaining another sequence P0 h0⊂P0 h0−1⊂. . . ⊂P0 2⊂P0 1 of nested polygons. Observe that the region Mi ( M0 i ) bounded by the consecutive polygons Pi+1 and Pi ( P0 i+1 and P0 i ) has the shape of a half-moon. It is not dicult to prove that Mi ( M0 i ) can be triangulated such that points p1 and p3 are not used, and each one of the added edges has an endpoint in Pi ( P0 i ) and the other one in Pi+1 ( P0 i+1 ). Then, we triangulate all the half-moons in this way (using edges connecting points placed in dierent polygons) and we triangulate the convex polygon Pf , formed by concatenating Ph and P0 h0 , such that the only points with degree two are p1 and p3 . It can be easily checked that the triangulation obtained in this way is 4-connected (see Figure 4 right). p1 p2 p3 Q P1 P2 p1 p2 p3 Q P0 1 p4 p5 p6 p7 p8 Figure 4: The general construction when |Q|=|P| and there are points inside P . The case in which |Q|<|P| and Q∪P satises the U-condition is solved in a similar way. First a graph based on a zig-zag is built, although this starting graph cannot be a zig-zag as in the previous case, because |Q|<|P| . Now, the starting graph is a zigzag connecting the points of Q to some points of P plus some additional edges connecting the points of P not belonging to the zig-zag to some points of Q (bold edges in Figure 5 left). After building this starting graph, we take a diagonal of P connecting two points of P , consecutive in the zig-zag but not consecutive in P (points pi1 and pi2 in Figure 5), and we proceed as in the previous case, adding the triangulations of the dierent half-moons and the nal triangulation of the convex polygon Pf (see Figure 5 right). The resulting triangulation is 4-connected. The U-condition is the key to nding this starting graph (the zig-zag plus some additional edges), although proving the existence of such a graph is not obvious. Due to space limitations, we do not include this proof. Therefore, we have proved the following theorem. Theorem 4 Let S be a set of points. If Q=H(S) , P=H(S\Q) and Q∪P satises the U-condition, Q pi1 pi2 pi3 pi4 pi5 P Figure 5: The general construction when |Q|<|P| and there are points inside P . then S is 4-connectible. 3 Conclusions In this paper, we have dened a condition, the Ucondition, that any set of points S must satisfy to be 4-connectible. Moreover, we have proved that the Ucondition is also sucient for sets of points in which Q∪P satises the U-condition. In [2], the case |Q|= 3 is completely solved. Given a set S of points such that |Q|= 3 , the authors show how to build a 4-connected triangulation on S , except for a particular conguration of points. This particular conguration is precisely the only one not satisfying the U-condition, among all the congurations of points such that |Q|= 3 . Using dierent techniques not included in this paper, we can extend the family of 4-connectible sets. For any set S of points satisfying the U-condition (it is not required that Q∪P satises the U-condition) such that |P|= 3 or |P|= 4 , we can built a 4-connected geometric graph on S . Finally, we conclude with the following conjecture. Conjecture 1 If a set of points S satises the Ucondition, then S is 4-connectible. References [1] P. Brass, W. Moser and J. Pach, Research Problems in Discrete Geometry , Springer-Verlag, Berlin, 2005. [2] T.K. Dey, M.B. Dillencourt, S.K. Ghosh and J.M. Cahill, Triangulating with high connectivity, Comput. Geom. Theory Appl. 8 (1997), 3956. [3] A. García, F. Hurtado, C. Huemer, J. Tejel and P. Valtr, On triconnected and cubic plane graphs on given point sets, Comput. Geom. Theory Appl. 42 (2009), 913922. [4] J. Pach (ed.), Thirty Essays on Geometric Graph Theory , Springer Science+Business Media, New York, 2013. 126