Monotone crossing number of complete graphs

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Monotone crossing number of complete graphs Martin Balko ∗ 1 , Radoslav Fulek † 1 , and Jan Kyn£l ‡ 2 1 Department of Applied Mathematics, Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 00 Praha 1, Czech Republic; 2 Department of Applied Mathematics and Institute for Theoretical Computer Science, Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 00 Praha 1, Czech Republic; Abstract In 1958, Hill conjectured that the minimum number of crossings in a drawing of Kn is exactly Z(n) = 1 4bn 2cn−1 2n−2 2n−3 2. Generalizing the result by Ábrego et al. for 2-page book drawings, we prove this conjecture for plane drawings in which edges are represented by x -monotone curves. In fact, our proof shows that the conjecture remains true for x - monotone drawings in which adjacent edges do not cross and we count only pairs of edges which cross odd number of times. We also discuss a combinatorial characterization of these drawings. 1 Introduction Let G be a graph with no loops and multiple edges. In a drawing D of a graph G in the plane, the vertices are represented by distinct points and each edge is represented by a simple continuous arc connecting the images of its endpoints. As usual, we identify the vertices and their images, as well as the edges and the arcs representing them. It is required that the edges pass through no vertices other than their endpoints. We also assume for simplicity that any two edges have only nitely many points in common, no two edges touch at an interior point and no three edges meet at a common interior point. A crossing in D is a common interior point of two edges where they properly cross. The crossing number cr(D) of a drawing D is the number of crossings in D . The crossing number cr(G) of a graph G is the ∗ Email: [email protected].cuni.cz. Research supported by the grant GACR GIG/11/E023 GraDR in the framework of ESF EUROGIGA program, by the Grant Agency of the Charles University, GAUK 1262213, and by the grant SVV-2013-267313 (Discrete Models and Algorithms). † Email: [email protected].cuni.cz. Research supported by the grant GACR GIG/11/E023 GraDR in the framework of ESF EUROGIGA program. ‡ Email: [email protected].cuni.cz. Research supported by the grant GACR GIG/11/E023 GraDR in the framework of ESF EUROGIGA program, by the Grant Agency of the Charles University, GAUK 1262213, and by the grant SVV-2013-267313 (Discrete Models and Algorithms). minimum of cr(D) , taken over all drawings D of G . A drawing D is called simple if no two adjacent edges cross and no two edges have more than one common crossing. It is well known and easy to see that every drawing of G which minimizes the crossing number is simple. According to the famous conjecture of Hill [7, 8] (also known as Guy's conjecture), the crossing number of the complete graph Kn on n vertices satises cr(Kn) = Z(n) , where Z(n) = 1 4n 2n−1 2n−2 2n−3 2. This conjecture has been veried for n≤12 [12] and for each n , there are drawings of Kn with Z(n) crossings [6, 7, 8, 9]. A curve α in the plane is x-monotone if every vertical line intersects α in at most one point. A drawing of a graph G in which every edge is represented by an x -monotone curve and no two vertices share the same x -coordinate is called x -monotone (or monotone , for short). The monotone crossing number mon-cr (G) of a graph G is the minimum of cr(D) , taken over all monotone drawings D of G . The rectilinear crossing number cr(G) of a graph G is the smallest number of crossings in a drawing of G where every edge is represented by a straightline segment. Since every rectilinear drawing of G in which no two vertices share the same x -coordinate is x -monotone, we have cr(G)≤ mon-cr (G)≤cr(G) for every graph G . We call a drawing of a graph semisimple if adjacent edges do not cross but independent edges may cross more than once. The monotone semisimple odd crossing number of G (called monotone odd + by Schaefer [14]), denoted by mon-ocr +(G) , is the smallest number of pairs of edges that cross an odd number of times in a monotone semisimple drawing of G . Clearly, mon-ocr +(G)≤ mon-cr (G). The monotone crossing number has been introduced by Valtr [15] and recently further investigated by Pach and Tóth [11], who showed that mon-cr (G)< 2cr(G)2 holds for every graph G . On the other hand, 127 Monotone crossing number of complete graphs they showed that the monotone crossing number and the crossing number are not always the same: there are graphs G with arbitrarily large crossing numbers such that mon-cr (G)≥7 6cr(G)−6. We study the monotone crossing numbers of complete graphs. The drawings of complete graphs with Z(n) crossings obtained by Blaºek and Koman [6] (see also [9]) are 2 -page book drawings, which may be considered as a strict subset of x -monotone drawings. Thus we have mon-cr (Kn)≤Z(n) . Ábrego et al. [1] recently proved Hill's conjecture for 2 -page book drawings of complete graphs. We generalize their techniques and show that Hill's conjecture holds for all x -monotone drawings of complete graphs, even for the monotone semisimple odd crossing number. Theorem 1 For every n∈N , we have mon-ocr +(Kn) = mon-cr (Kn) = Z(n). The rectilinear crossing number of Kn is known to be asymptotically larger than Z(n) : this follows from the best current lower bound cr(Kn)≥ (277/729)n 4−O(n3) [3, 5] and from the simple upper bound Z(n)≤3 8n 4+O(n3) . See a recent survey by Schaefer [14] for an encyclopedic treatment of all known variants of crossing numbers. After submitting this extended abstract, we were informed that the authors of [1] achieved the result mon-cr (Kn) = Z(n) already during discussions after their presentation at SoCG 2012, and that it will appear in the proceedings of LAGOS 2013 [2]. 2 Monotone Crossing Number To prove the upper bound on the 2 -page crossing number of Kn , Ábrego et al. [1] generalized the notion of k -edges to arbitrary simple drawings of complete graphs. They also introduced the notion of ≤≤k - edges. These capture the essential properties of 2 - page book drawings better than ≤k -edges, which had been successfully used before for rectilinear and pseudolinear drawings [10, 4, 3]. We show that the approach using ≤≤k -edges can be generalized to arbitrary semisimple x -monotone drawings. For a semisimple drawing D of Kn and distinct vertices u and v of Kn , let γ be the oriented arc representing the edge {u, v} . If w is a vertex of Kn dierent from u and v , then we say that w is on the left (right) side of γ if the topological triangle uvw with vertices u , v and w traced in this order is oriented counterclockwise (clockwise, respectively). This generalizes the denition introduced by Ábrego et al. [1] for simple drawings. However, we were not able to nd a meaningful generalization of this notion to drawings that are not semisimple, where the edges of the triangle uvw can cross several times. A k -edge is an edge {u, v} of D that has exactly k points on the same side (left or right). Since every k -edge has n−2−k points on the other side, every k - edge is also an (n−2−k) -edge and so every edge of D is a k -edge for some integer k where 0≤k≤ bn/2c−1 . An i -edge with i≤k is called a ≤k -edge . Let Ei(D) be the number of i -edges and E≤k(D) the number of ≤k -edges of D . Clearly, E≤k(D) = Pk i=0 Ei(D) . Similarly, the number of ≤≤k -edges of D , E≤≤k(D) , is dened by the following identity. E≤≤k(D) = k X j=0 E≤j(D) = k X i=0 (k+ 1 −i)Ei(D) (1) Considering the only three dierent simple drawings of K4 up to a homeomorphism of the plane, Ábrego et al. [1] showed that the number of crossings in a simple drawing D of Kn can be expressed in terms of the number of k -edges in the following way. Lemma 2 ([1]) For every simple drawing D of Kn we have cr(D)=3n 4− bn/2c−1 X k=0 k(n−2−k)Ek(D), (2) which can be equivalently rewritten as cr(D) = 2 bn/2c−2 X k=0 E≤≤k(D)−1 2n 2n−2 2 −1 2(1 + (−1)n)E≤≤bn/2c−2(D). In fact, Lemma 2 can be easily generalized to semisimple drawings of Kn where cr(D) is replaced by ocr (D) , which counts the number of pairs of edges that cross an odd number of times in D . The main reason is that the cycle C4 cannot be drawn in the plane in such a way that both its pairs of opposite edges cross oddly while adjacent edges do not cross. By Lemma 2, lower bounds on Ek(D) imply lower bounds on cr(D) and ocr (D) . Considering ≤k -edges, Ábrego and Fernández-Merchant [4] and Lovász et al. [10] proved that for rectilinear drawings of Kn , the inequality E≤k≥3k+2 2 together with (2) gives cr(G)≥Z(n) . However, there are simple x -monotone (even 2 -page) drawings of Kn where E≤k<3k+2 2 for k= 1 [1]. Ábrego et al. [1] showed that similar inequality for ≤≤k -edges is satised by all 2 -page book drawings. We show that the same inequality is satis- ed by all x -monotone semisimple drawings of Kn . Let {v1, v2, . . . , vn} be the vertex set of Kn . Note that we can assume that all vertices in an x -monotone 128 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 drawing lie on the x -axis. We also assume that the x -coordinates of the vertices satisfy x(v1)< x(v2)< · · · < x(vn) . Observation 3 Let D be a semisimple drawing of Kn , not necessarily x -monotone. Let v be a vertex incident with the outer face of D and let γi be the i th edge incident with v in the counter-clockwise cyclic order such that γ1 and γn−1 are incident with the outer face in a small neighborhood of v . Let vki be the other endpoint of γi . Then for every i, j , 1≤i<j≤n−1 , the triangle vkivvkj is oriented clockwise. Consequently, for every k , 1≤k≤(n−1)/2 , the edges γk and γn−k are (k−1) -edges. For even n , the edge γn/2 is a halving edge.  For an x -monotone drawing D of Kn , we use Observation 3 directly for the vertex vn and then for each i , for the vertex vi and the subgraph induced by vi, vi+1, . . . , vn . The following denitions were introduced by Ábrego et al. [1] for 2 -page book drawings. Let D be a semisimple x -monotone drawing of Kn and let D0 be a drawing obtained from D by deleting the vertex vn together with its adjacent edges. A k -edge in D is a (D, D0) -invariant k -edge if it is also a k -edge in D0 . It is easy to see that every ≤k -edge in D0 is also a ≤(k+ 1) -edge in D . If 0≤j≤k≤ bn/2c − 1 , then a (D, D0) -invariant j -edge is called a (D, D0) - invariant ≤k -edge . Let E≤k(D, D0) denote the number of (D, D0) -invariant ≤k -edges. For i < j , the edge vivj is called the right edge at vi . The right edges at vi have a natural vertical order. Lemma 4 Let k be a xed integer such that 0≤k≤ (n−3)/2 . For every i∈ {1,2, . . . , k+1} , the k+ 2 −i bottommost and the k+ 2 −i topmost right edges at vi are ≤k -edges in D . Moreover, at least k+ 2 −i of these ≤k -edges are (D, D0) -invariant ≤k -edges. Proof. The rst part of the lemma follows directly from Observation 3. If the edge vivn is one of the k+ 2 −i topmost right edges at vi , then the k+ 2 −i bottommost right edges at vi are (D, D0) -invariant ≤k -edges. Otherwise the k+ 2 −i topmost right edges at vi are (D, D0) -invariant ≤k -edges.  Corollary 5 We have E≤k(D, D0)≥ k+1 X i=1 (k+ 2 −i) = k+ 2 2.  The following theorem gives the lower bound on the number of ≤≤k -edges. The proof is essentially the same as in [1], we only extracted Lemma 4, which needed to be generalized. Together with Lemma 2, Theorem 6 yields Theorem 1. Theorem 6 Let n≥3 and let D be a semisimple x - monotone drawing of Kn . Then for every k , 0≤k < n/2−1 , we have E≤≤k(D)≥3k+3 3. Proof. The proof proceeds by induction on n where the case n= 3 is trivially true. Let n≥4 and let D be a semisimple x -monotone drawing of Kn . For the induction step we remove the point vn together with its adjacent edges to obtain a drawing D0 of Kn−1 , which is also semisimple and x -monotone. Using Observation 3 we see that for 0≤i≤k < n/2−1 there are two i -edges adjacent to vn in D and together they contribute with 2Pk i=0(k+ 1 −i) = 2k+2 2 to E≤≤k(D) by (1). Let γ be an i -edge in D0 . Then γ contributes by (k−i) to the sum E≤≤k−1(D0) = Pk−1 i=0 (k−i)Ei(D0). We already observed that γ is either an i -edge or an (i+ 1) -edge in D . If γ is also an i -edge in D (that is, γ is a (D, D0) -invariant i -edge), then it contributes by (k+ 1 −i) to E≤≤k(D) . This is a gain of +1 towards E≤≤k−1(D0) . If γ is an (i+ 1) -edge in D , then it contributes only (k−i) to E≤≤k(D) . Therefore we have E≤≤k(D)=2k+ 2 2+E≤≤k−1(D0) + E≤k(D, D0). By the induction hypothesis we know that E≤≤k−1(D0)≥3k+2 3 and thus we obtain E≤≤k(D)≥3k+ 3 3−k+ 2 2+E≤k(D, D0). The theorem follows by plugging the lower bound from Corollary 5.  3 Combinatorial Description In this section we develop a combinatorial characterization of x -monotone drawings which is based on the signature function introduced by Peters and Szekeres [13] for describing order types of points sets. Let Tn be the set of ordered triples (i, j, k) of the set [n] = {1,2, . . . , n} and let Σn be the set of signature functions σ:Tn→ {−,+} . Let D be an x -monotone drawing of the complete graph Kn= (V, E) with vertices v1, v2, . . . , vn such that their x -coordinates satisfy x(v1)< x(v2)<· · · < x(vn) . We assign a signature function σ∈Σn to the drawing D according to the following rule. For each e={vi, vk} ∈ E and every integer j , i < j < k , let σ(i, j, k) = − if the point vj lies above the arc representing the edge e and σ(i, j, k)=+ otherwise. Note that if the drawing D is also semisimple, then a triangle vivkvj , j∈(i, k) , is oriented counterclockwise (clockwise) if and only if σ(i, j, k) = − ( σ(i, j, k)=+ , respectively). It is easy to see that 129 Monotone crossing number of complete graphs for every signature function σ∈Σn there is an x - monotone drawing D which induces σ . However, such a drawing does not have to be semisimple. We show a characterization of simple and semisimple x - monotone drawings by small forbidden congurations in the signature functions. For a, b, c, d ∈[n] with a<b<c<d and a signature function σ∈Σn we say that the 4-tuple (a, b, c, d) is of the form ξ1ξ2ξ3ξ4 in σ if σ(a, b, c) = ξ1, σ(a, b, d) = ξ2, σ(a, c, d) = ξ3 and σ(b, c, d) = ξ4. Theorem 7 A signature function σ∈Σn can be realized by a semisimple x -monotone drawing if and only if each ordered 4 -tuple of indices is of one of the forms ++++ , −−−− , ++−− , −−++ , −++− , +−−+ , −−−+ , +++− , +−−− , −+++ in σ . The signature function σ can be realized by a simple x - monotone drawing if, in addition, there is no 5 -tuple (a, b, c, d, e) , a<b<c<d<e , with σ(a, b, e) = σ(a, d, e) = σ(b, c, d) = −σ(a, c, e). Note that in a simple x -monotone drawing of Kn the crossings can appear only between edges whose endpoints induce a 4-tuple of one of the forms ++++,−−−−,++−−,−−++,−++−,+−−+ . Analogously to a similar correspondence in rectilinear drawings of Kn , we may call these 4-tuples convex . Then for a simple x -monotone drawing D of Kn the crossing number of D equals the number of convex 4-tuples. A similar notion of convexity for general k -tuples was used by Peters and Szekeres [13]. This description of crossings is convenient for computer calculations. Using it, we have obtained a complete list of optimal x -monotone drawings of Kn for n≤10 . 4 Concluding remarks It is an interesting direction of further research to see if similar techniques can be helpful in proving Hill's conjecture for general drawings of complete graphs. We note that the same approach does not generalize to all drawings: for example, a particular planar realization of the so-called cylindrical drawing [7, 8] of K10 , with crossing number Z(10) , does not satisfy the lower bound on ≤≤1 -edges in Theorem 6. It would also be interesting to further generalize Theorem 1 to monotone drawings where also adjacent edges are allowed to cross. Acknowledgments We would like to thank Pavel Valtr for initializing the research which led to this problem and Marek Eliá² for developing visualization tools that were helpful during the research. References [1] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, and G. Salazar, The 2-page crossing number of Kn , preprint, 2012, arXiv:1206.5669. [2] B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, and G. Salazar, More on the crossing number of Kn : Monotone drawings, Proceedings of the VII Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS) 2013, Playa del Carmen, Mexico (to appear). [3] B. M. Ábrego, M. Cetina, S. Fernández-Merchant, J. Leaños, and G. Salazar, On ≤k -edges, crossings, and halving lines of geometric drawings of Kn , Discrete Comput. Geom. 48 (2012), 192215. [4] B. M. Ábrego and S. Fernández-Merchant, A lower bound for the rectilinear crossing number, Graphs Combin. 21 (2005), 293300. [5] B. M. Ábrego, S. Fernández-Merchant, J. Leaños, and G. Salazar, A central approach to bound the number of crossings in a generalized conguration, in: The IVLatin-American Algorithms, Graphs, and Optimization Symposium , Electron. Notes Discrete Math., 30, Elsevier Sci. B. V., Amsterdam, 2008, 273278. [6] J. Blaºek and M. Koman, A minimal problem concerning complete plane graphs, in: Theory of Graphs and its Applications , Proc. Sympos. Smolenice, 1963, Publ. House Czechoslovak Acad. Sci., Prague, 1964, 113117. [7] R. K. Guy, A combinatorial problem, Nabla (Bull. Malayan Math. Soc) 7 (1960), 6872. [8] F. Harary and A. Hill, On the number of crossings in a complete graph, Proc. Edinburgh Math. Soc. (2) 13 (1963), 333338. [9] H. Harborth, Special numbers of crossings for complete graphs, Discrete Mathematics 244 (2002), 95 102. [10] L. Lovász, K. Vesztergombi, U. Wagner, and E. Welzl, Convex quadrilaterals and k -sets, in: Towards a theory of geometric graphs , Contemp. Math., 7034, Amer. Math. Soc., Providence, RI, 2004, 139148. [11] J. Pach and G. Tóth, Monotone Crossing Number, in: Graph drawing , Lecture Notes in Comput. Sci., 7034, Springer, Berlin Heidelberg, 2012, 278289. [12] S. Pan and B. R. Richter, The crossing number of K11 is 100, J. Graph Theory 56 (2007), 128134. [13] G. Szekeres and L. Peters, Computer solution to the 17-point Erd®s-Szekeres problem, ANZIAM J. 48 (2006), 151164. [14] M. Schaefer, The Graph Crossing Number and its Variants: A Survey, Electronic Journal of Combinatorics , Dynamic Survey 21 (2013). [15] P. Valtr, On the pair-crossing number, in: Combinatorial and computational geometry , Math. Sci. Res. Inst. Publ., 52, Cambridge Univ. Press, Cambridge, 2005, 569575. 130