The alternating path problem revisited

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 The alternating path problem revisited Mercè Claverol 1 , Delia Garijo 2 , Ferran Hurtado 1 , Dolores Lara 3 , and Carlos Seara 1 1,3 Universitat Politècnica de Catalunya, Barcelona, Spain 2 Universidad de Sevilla, Spain Abstract It is well known that, given n red points and n blue points on a circle, it is not always possible to nd a plane geometric Hamiltonian alternating path. In this work we prove that if we relax the constraint on the path from being plane to being 1 -plane, then the problem always has a solution, and even a Hamiltonian alternating cycle can be obtained on all instances. We also extend this kind of result to other congurations and provide remarks on similar problems. Introduction A geometric graph is a graph drawn in the plane whose vertex set is a set of points and whose edges are straight-line segments connecting pairs of vertices. Two edges of a geometric graph cross if they have an intersection point lying in the relative interior of both edges. A plane geometric graph is a geometric graph without any edge crossings. A 1 -plane geometric graph is a geometric graph in which every edge has at most one crossing. Notice that the terms plane graph and 1 -plane graph refer to a geometric object, while to be planar or 1 -planar are properties of the underlying abstract graph. We use here standard notation for geometric graphs as in [3] and [12]. Let P be a set of points in the plane in general position (i.e., no three points are collinear), and let CH(P) denote its convex hull. A geometric spanning tree on P , generically denoted by tree(P) , is any spanning tree on P whose edges are straight-line segments connecting two points on P . Observe that if |P|= 1 , the tree on P is a single vertex. When the tree is a path, we write path(P) . The geometric complete graph K(P) on P is the complete geometric graph with vertex set P . Notice that tree(P) is a spanning tree of K(P) . 1 Email: [email protected]c.edu, [email protected], [email protected]. Partially supported by projects MINECO MTM2012-30951, Gen. Cat. DGR2009SGR1040, and ESF EUROCORES programme EuroGIGA, CRP Com- PoSe: MICINN Project EUI-EURC-2011-4306. 2 Email: [email protected]. Partially supported by projects 2009/FQM-164 and 2010/FQM-164. 3 Email: [email protected]. Let R and B be two disjoint sets of red and blue points in the plane such that no three points of R∪B lie on the same line. The geometric complete bipartite graph K(R, B) is the graph with vertex set R∪B and whose edges are all the straight-line segments connecting any point in R and any point in B . A line segment dened by two red points is a red segment , and one de- ned by two blue points is a blue segment . More generally, an edge is said to be monochromatic when the two endpoints have the same color, and bichromatic otherwise. The intersections between red segments and blue segments are called bichromatic crossings , and those between segments having the same color are called monochromatic crossings . Problems on adding edges to a given graph to obtain a new graph with some desirable properties are, in general, called augmentation problems . Among these, plane augmentation considers an initial plane graph G= (V, E) (possibly empty, i.e., only the point set V is given) that has to be augmented to another plane supergraph G′= (V, E ∪E′) by adding a set E′ of edges to G , see the survey [7]. In this work we focus on problems in which the initial point set is a bicolored set R∪B . This family of problems has attracted a substantial amount of research, see for instance the surveys [8, 7]. We rst consider alternating graphs , i.e., those in which every edge is bichromatic. A well known fact [2, 1, 10, 11] is that given n red points and n blue points on a circle (equivalently, in convex position), one cannot always obtain a plane geometric Hamiltonian alternating path. In this paper we prove that, if we relax the constrain on the geometric Hamiltonian alternating path from being plane to being 1-plane, then a solution always exists, even yielding stronger properties. We also show that the same result holds for some other congurations. These results appear in Section 1. Regarding monochromatic graphs , i.e, graphs in which every edge is monochromatic, it is easy to see that one cannot always construct a plane perfect matching in K(R)∪K(B) . A trivial example is given by the vertices of a convex quadrilateral in which two opposite vertices are colored red and the other two are colored blue. The same example shows that it is not always possible to obtain two geometric monochro- 115 The alternating path problem revisited matic spanning trees, tree(R) and tree(B) , such that their union is plane. The proven nonexistence of plane congurations had already suggested to researchers to allow some relaxation in the constraint, but the focus was put on constructing geometric graphs having globally few crossings [9, 13]. However, one of the constructions in [13] is in fact a 1 -plane graph. We include some remarks on that particular result and its consequences in Section 2. We conclude in Section 3 with some additional comments. 1 Alternating graphs: paths and cycles In this section we study geometric alternating spanning graphs on R∪B , i.e., spanning subgraphs of K(R, B) . We focus on geometric Hamiltonian alternating paths and cycles, which visit red points and blue points alternately. Notice that when there are no crossings at all, geometric Hamiltonian paths and cycles are also called simple polygonals and simple polygons , respectively. 1.1 Convex position The problem of restricting the bicolored point set to lay on a circle has attracted a lot of attention. It is easy to see that there are sets R and B with the same number of points, say n , such that R∪B is in convex position, and a plane geometric Hamiltonian alternating path on R∪B cannot exist. Erd®s (see [10]) proposed in 1989 to study the value ℓ(n) such that no matter how the colors are distributed a plane geometric alternating path of length at least ℓ(n) always exists. About the same time, Akiyama and Urrutia [2] considered independently the same problem: they proved a necessary and sucient condition for the existence of a plane geometric Hamiltonian alternating path and derived an O(n2) time algorithm to nd one, if it exists. Abellanas et al. [1], and independently Kyn£l et al. [10], proved that ℓ(n)≤4 3n+O(√n) , and Cibulka et al. [4] showed that ℓ(n)≥n+ Ω(√n) . These bounds are the best to date. Remind that the total number of points is 2n . Also, notice that we slightly abuse the notation by using inequalities, and that the two bounds have to be read together, not independently. For more information and details, see Mészáros' PhD Thesis [11]. We next show that if R∪B is in convex position then a 1 -plane geometric Hamiltonian alternating cycle not only a path can always be drawn. The following lemma is the key tool. Lemma 1 Let R and B be two disjoint sets of red and blue points in the plane such that R∪B is in convex position, and |R|=|B|=n≥2 . Let S be a set of disjoint bichromatic segments on the boundary of the convex hull of R∪B , and |S|=s≥2 . Then, there exists a 1 -plane geometric Hamiltonian alternating cycle on R∪B that contains each segment of S as an edge. If R∪B is in convex position and |R|=|B|= n≥2 then there are at least two disjoint bichromatic segments on the boundary of CH(R∪B) , say s1, s2 . Let S={s1, s2} . By Lemma 1, one can draw a 1 - plane geometric Hamiltonian alternating cycle on R∪ B that contains each segment of S as an edge. This argument proves our main result in this section. Theorem 2 Let R and B be two disjoint sets of red and blue points in the plane such that R∪B is in convex position, and |R|=|B|=n≥2 . Then, there exists a 1 -plane geometric Hamiltonian alternating cycle on R∪B . 1.2 Double chain We next consider the problem of drawing a 1 -plane geometric Hamiltonian alternating cycle on a double chain whose points are colored red and blue. The double chain (formally dened below) is a conguration that has been intensively studied since it admits many triangulations, many polygonizations, many crossing-free matchings, etc., and for several families of graphs yields the maximum number known to date of such possible congurations among point sets with the same cardinality (see http://www.cs.tau.ac.il/ sheffera/counting/PlaneGraphs.html). A double chain (C1, C2) consists of two opposite convex chains C1 and C2 , facing each other, such that the convex hull of C1∪C2 is a quadrilateral, each point of C2 lies strictly below every line determined by two points of C1 , and each point of C1 lies strictly above every line determined by two points of C2 . When the points of (C1, C2) are colored red and blue, (C1, C2) is said to be a bicolored double chain (see Figure 1), and ri, bi denote the number of red and blue points, respectively, of Ci for i= 1,2 . Note that the sizes of C1 and C2 may be dierent. 1 C 2 C Figure 1: A bicolored double chain (C1, C2) . 116 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Cibulka et al. [4] proved the following theorem: Theorem 3 [4] (i) If |Ci| ≥ 1 5(|C1|+|C2|) for i= 1,2 , then there exists a non-crossing geometric Hamiltonian alternating path on (C1, C2) ; (ii) there exist bicolored double chains in which one of the chains contains at most 1/29 of all the points, which do not admit a non-crossing geometric Hamiltonian alternating path. Theorem 4 below states that when r1+r2=b1+b2 , allowing at most one crossing per edge is strong enough to let us always draw a geometric Hamiltonian alternating cycle on (C1, C2) . The main idea to obtain this cycle is to use Theorem 2 to construct two 1 -plane geometric alternating cycles Λ1 and Λ2 in CH(C1) and CH(C2) , respectively, and to connect them drawing another 1 -plane geometric alternating cycle Λ in the exterior of CH(C1) and CH(C2) . This process is described next. Let Ei , i= 1,2 , be the set of edges in CH(Ci) that connect consecutive points of Ci . Suppose rst that 3≤b1+ 1 < r1 and 3≤r2+ 1 < b2 . Then there exist at least two monochromatic edges in E1∪E2 : a red edge rr′∈E1 and a blue edge bb′∈E2 . Contract them obtaining a red point r′′ and a blue point b′′ . By Theorem 2, we can draw a cycle Λ1 on the point set formed by the b1 blue points of C1 , the red point r′′ , and b1−1 red points of C1\{r, r′} . Analogously, Λ2 is constructed on the point set formed by the r2 red points of C2 , the blue point b′′ , and r2−1 blue points of C2\{b, b′} . Finally, the cycle Λ is drawn, as in Figure 2, on the remaining r1−b1−1 red points of C1 , the remaining b2−r2−1 = r1−b1−1 blue points of C2 , and the points r′′ and b′′ . Observe that r′′ and b′′ connect Λ with Λ1 and Λ2 , respectively. By reversing the contraction and deleting the edges rr′ and bb′ , we "open" the three cycles obtaining the desired cycle on (C1, C2) . Note that the preceding argument can easily be adapted for b1 or r2 equal to zero or one. Observe also that if all the edges in E1 (analogous for E2 ) are bichromatic then either r1=b1 (and so r2=b2 ) or r1=b1+ 1 (and b2=r2+ 1 ). For these values, even if there are monochromatic edges in E1 , we need to use slightly dierent arguments which are omitted for the sake of brevity. Theorem 4 Let R and B be the sets of red and blue points of a bicolored double chain (C1, C2) , and |R|=|B| ≥ 2 . Then, there exists a 1 -plane geometric Hamiltonian alternating cycle on (C1, C2) . 1.3 General position The positive results for convex position and for the double chain make one wonder whether a similar result holds for any set of points in general position: Question 1 Let R and B be any two disjoint sets of red and blue points in the plane such that no three points of R∪B lie on the same line, and |B|=|R| ≥ 2 . Does there always exist a 1 -plane geometric Hamiltonian alternating cycle on R∪B ? We do not know the answer to the preceding question. Geometric Hamiltonian cycles with few crossings were obtained by Kaneko et al. [9], who gave a tight upper bound of |R| − 1 for the number of crossings of a geometric Hamiltonian alternating cycle. Figure 2 illustrates a conguration R∪B for which this upper bound is best possible. Figure 2: A 1 -plane geometric Hamiltonian alternating cycle, on a point set R∪B , with |R|−1 crossings. To be precise, Kaneko et al. [9] proved the following result. Theorem 5 [9] Let R and B be two disjoint sets of points in the plane such that |R|=|B| and no three points of R∪B are on the same line. Then we can draw a geometric Hamiltonian alternating cycle on R∪B which has at most |R| − 1 crossings. Moreover there exist congurations R∪B for which this upper bound |R|−1 is the best possible. To prove this theorem, the authors use several lemmas that we have carefully examined to see whether it is possible to adapt their proof to obtain a 1 -plane graph. However, as far as we can see, there are cases in which the connection of the paths that exist by induction is not necessarily 1 -plane. It is unclear to us which is the right answer to Question 1, yet our study leads us to believe that it is negative in general, yet positive if only a Hamiltonian path is required, which we state as a conjecture: Conjecture 1 Let R and B be two disjoint sets of red and blue points in the plane such that no three points of R∪B lie on the same line, and |B| ≤ |R| ≤ |B|+1 . There always exists a 1 -plane geometric Hamiltonian alternating path on R∪B . Let us mention that this is ongoing research, currently focusing on the preceding conjecture, which we hope to answer in the next version of this paper. 117 The alternating path problem revisited 2 A remark on monochromatic graphs In this section we would like to remark that a result obtained by Tokunaga in 1996 can be rephrased in terms of 1 -plane graphs, hence giving support to the idea that exploring this relaxation may be worth the eort for more problems. On one hand, it is not always possible to construct a non-crossing perfect matching in K(R)∪K(B) as proved by Dumitrescu and Steiger [6]. The original result was improved by Dumitrescu and Kaye [5], who proved that for given R and B , with |R|+|B|=n , there always exists a non-crossing matching in K(R)∪ K(B) which covers at least 0.8571 ·n points of R∪ B , while for some congurations every non-crossing matching in K(R)∪K(B) covers at most 0.9871 ·n points of R∪B . On the other hand, drawing plane red and blue geometric spanning trees on R and B that avoid bichromatic crossings is not always possible, and Tokunaga [13] characterized their existence in terms of the bichromatic edges on CH(R∪B) . One may wonder whether using 1 -plane graphs would always yield a positive solution to the above problems. The answer is armative: Tokunaga [13] also proved that for given R and B , there exists a pair (path(R),path(B)) of red and blue geometric simple Hamiltonian paths such that each edge of path(R) intersects at most one edge of path(B) and vice versa. Having the red and blue geometric simple Hamiltonian paths from that result, with at most one bichromatic crossing per edge, we already have got 1 -plane spanning trees, and taking in each path one segment out of any two consecutive we get a 1 -plane perfect matching with no monochromatic crossings. This 1 - plane matching can also be obtained by using the Ham-sandwich theorem and induction on |R∪B| . We include this remark because the focus in [13] was to get few crossings rather than achieving the 1 -plane character, but the consequences show that pursuing the latter line of research may be of interest. 3 Conclusion We have proved that several problems on bicolored point sets asking for the construction of a plane geometric graph with some requisites, and that have in general negative answer, turn out to have a solution if the requirement of the graphs being plane is relaxed to being 1 -plane. As mentioned in a previous section, this is ongoing research and answering Conjecture 1 is our priority. On the other hand, we are also studying the same relaxation for other problems in which 1 -plane graphs may provide a solution where plane graphs are not sucient. References [1] M. Abellanas, A. García, F. Hurtado, and J. Tejel, Caminos alternantes, in: Actas X Encuentros de Geometría Computacional (in Spanish), 2003, 712. [2] J. Akiyama and J. Urrutia, Simple alternating path problem, Discr. Math. 84 (1990), 101103. [3] P. Brass, W. Moser, and J. Pach, Research Problems in Discrete Geometry , Springer, 2005. [4] J. Cibulka, J. Kyn£l, V. Mészáros, R. Stola°, and P. Valtr, Hamiltonian alternating paths on bicolored double-chains, in: Graph Drawing 2008, Lecture Notes in Computer Science 5417 (2009), 181192. [5] A. Dumitrescu and R. Kaye, Matching colored points in the plane: Some new results, Comput. Geom. Theory Appl. 19 (2001), 6985. [6] A. Dumitrescu and W. Steiger, On a matching problem in the plane, Discr. Math. 211 (2000), 183195. [7] F. Hurtado and C. D. Tóth, Plane geometric graph augmentation: a generic perspective, Chapter 16 in: Thirty Essays on Geometric Graph Theory (J. Pach, ed.), vol. 29 of Algorithms and Combinatorics, Springer, 2013, 327354. [8] A. Kaneko and M. Kano, Discrete geometry on red and blue points in the plane - a survey, in: Discrete and Computational Geometry, The Goodman-Pollack Festschrift ; edited by B. Aronov et al., Springer, 2003, 551570. [9] A. Kaneko, M. Kano, and Y. Yoshimoto, Alternating Hamiltonian cycles with minimum number of crossings in the plane, Int. J. Comput. Geom. Appl. 10 (2000), 7378. [10] J. Kyn£l, J. Pach, and G. Tóth, Long alternating paths in bicolored point sets, in: Graph Drawing 2004 (J. Pach, ed.), Lecture Notes in Computer Science 3383 (2004), 340348. Also in Discr. Math. 308 (2008), 43154322. [11] V. Mészáros. Extremal problems on planar point sets PhD Thesis, University of Szeged, 2011. [12] J. Pach, ed. Thirty Essays on Geometric Graph Theory , vol. 29 of Algorithms and Combinatorics, Springer, 2013. [13] S. Tokunaga, Intersection number of two connected geometric graphs, Information Proc. Discrete Math. 150 (1996), 371378. 118