Block Course: Methods in Graph Drawing - Crossing Numbers and Crossing Minimization

Supplementary lecture materials

Complete graphs

Conjecture. [Guy]   $ \displaystyle cr(K_n) = \frac 14 \floor{\frac n2} \floor{\frac{n-1}2} \floor{\frac{n-2}2} \floor{\frac{n-3}2} $
 
The conjectured value for the crossing number of $ K_n $ is known to be an upper bound. This is shown by exhibiting a drawing with that number of crossings. If $ n = 2m $, place $ m $ vertices regularly spaced along two circles of radii 1 and 2, respectively. Two vertices on the inner circle are connected by a straight line; two vertices on the outer circle are connected by a polygonal line outside the circle. A vertex on the inner circle is connected to one on the outer circle with a polygonal line segment of minimum possible positive winding angle around the cylinder. A simple count shows that the number of crossings in such a drawing achieves the conjectured minimum. For $ n = 2m-1 $ we delete one vertex from the drawing described and achieve the conjectured minimum.
The conjecture was recently verified for n=11 and 12 (The Crossing Number of K11 Is 100 by Shengjun Pan and R. Bruce Richter). Moreover, $ 0.8594 \cdot Z(n)\leq cr(K_n) \leq Z(n) $.

  • The crossing number of K11 is 100. Shengjun Pan, R. Bruce Richter. Journal of Graph Theory 56, pages 128–134, October 2007.

Complete bipartite graphs

Conjecture. [Turan / Zarankiewicz]   $ \displaystyle cr(K_{m,n}) = \floor{\frac m2} \floor{\frac {m-1}2} \floor{\frac n2} \floor{\frac {n-1}2} $

This problem is also known as Turan's Brickyard Problem (since it was formulated by Turan when he was working at a brickyard - the edges of the drawing would correspond to train tracks connecting different shipping depots, and fewer crossings would mean smaller chance for collision of little trains and smaller chance for their derailing). This conjectured value for the crossing number of $ K_{m,n} $ can be realized by the following drawing. Place $ \ceil{n/2} $ vertices on the positive $ x $-axis and $ \floor{n/2} $ vertices on the negative $ x $-axis. Similarly, place $ \ceil{m/2} $ and $ \floor{m/2} $ along the positive and negative $ y $-axis. Now connect each pair of vertices on different axes with straight line segments.
  • Guy, R. K. "The Decline and Fall of Zarankiewicz's Theorem." In Proof Techniques in Graph Theory, Proceedings of the Second Ann Arbor Graph Theory Conference, Ann Arbor, Michigan, 1968. New York: Academic Press, pp. 63-69, 1969.

Actually, there have been a false "proof" of the conjecture by Zarankiewicz in the 50s, disproved much later on. As with the complete graphs, the conjecture is still wide open.

The Crossing Number of the Complete Graph
Zarankiewicz's conjecture
The crossing number of K11 is 100. Pan, Richter. 2007
Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs. Richter and Thomassen. 1997
Improved bounds for the crossing numbers of K_m,n and K_n Authors: E.de Klerk, J.Maharry, D.V.Pasechnik, R.B.Richter, G.Salazar. 2004

Toroidal grids Cm x Cn

grid pic                   

In 1973, Harary, Kainen, and Schwenk proved that toroidal graphs can have arbitrarily large crossing numbers [7]. In the same paper, they put forward the following conjecture.
Conjecture [HKS-Conjecture]. The crossing number of the Cartesian product CmxCn is (m-2)n, for all m,n such that n>=m>=3.
This has been proved for m,n satisfying n>=m, m<=7 [Richter, Salazar, Adamsson, Thomassen, Klesc, Stobert, Rodney, and more...]. Specifically, a few citations:

  • Hector A. Juarez, Gelasio Salazar: Drawings of Cm x Cn with One Disjoint Family II. J. Comb. Theory, Ser. B 82(1): 161-165 (2001)

Proving that at least half of the conjectured value is true (following some deep technical work of [Richter et al]).

  • Arrangements, circular arrangements and the crossing number of C7×Cn.Jay Adamsson and R. Bruce Richter. Journal of Combinatorial Theory, Series B 90, January 2004, Pages 21-39.

    Motivated by the problem of determining the crossing number of the Cartesian product Cm×Cn of two cycles, we introduce the notion of an (m,n)-arrangement, which is a generalization of a planar drawing of Pn+1×Cm in which the two “end cycles” are in the same face of the remaining n cycles. The main result is that every (m,n)-arrangement has at least (m−2)n crossings. This is used to show that the crossing number of C7×Cn is 5n, in agreement with the general conjecture that the crossing number of Cm×Cn is (m−2)n, for 3less-than-or-equals, slantmless-than-or-equals, slantn.

  • Lev Yu. Glebsky, Gelasio Salazar: The crossing number of Cm × Cn is as conjectured for n >= m(m + 1). Journal of Graph Theory 47(1): 53-72 (2004)

abstract

 

Generalized Petersen graphs P(N,3)

  • R. Bruce Richter, Gelasio Salazar: The Crossing Number of P(N, 3). Graphs and Combinatorics 18(2): 381-394 (2002)

 

P(8,3)

Theorem 1. [Richter and Salazar] The crossing number of the Generalized Petersen Graph P(3k+h,3) is k+h if h=0,2 and k+3 if h=1, for each k>=3, with the single exception of P(9,3) whose crossing number is 2.

Intersections of curve systems and the crossing number of C 5 ×C 5. R. B. Richter and C. Thomassen. 1995
Arrangements, circular arrangements and the crossing number of C7×Cn Jay Adamssona and R. Bruce Richter. 2004
(The Crossing Number of Cm × Cn: A Reluctant Induction. Myers. 1998)
Hector A. Juarez, Gelasio Salazar: Drawings of Cm x Cn with One Disjoint Family II. J. Comb. Theory, Ser. B 82(1): 161-165 (2001)
The crossing number of Cm × Cn is as conjectured for n >= m(m + 1). Glebsky, Salazar. 2004
The Crossing Number of P(N, 3). Richter and Salazar. 2002

Rectilinear crossing number

  • Bounds for rectilinear crossing numbers, Daniel Bienstock, Nathaniel Dean.  Journal of Graph Theory Volume 17, Issue 3, pages 333–348, July 1993

Abstract  A rectilinear drawing of a graph is one where each edge is drawn as a straight-line segment, and the rectilinear crossing number of a graph is the minimum number of crossings over all rectilinear drawings. We describe, for every integer k ≥ 4, a class of graphs of crossing number k, but unbounded rectilinear crossing number. This is best possible since the rectilinear crossing number is equal to the crossing number whenever the latter is at most 3. Further, if we consider drawings where each edge is drawn as a polygonal line segment with at most one break point, then the resulting crossing number is at most quadratic in the regular crossing number.

 

Odd crossing number

  • János Pach, Géza Tóth: Which Crossing Number Is It Anyway? J. Comb. Theory, Ser. B (JCT) 80(2):225-246 (2000).

Bounds for rectilinear crossing numbers. Bienstock, Dean. 1993
The Rectilinear Crossing Number Project
Which Crossing Number Is It Anyway? Pach and Tóth. 2000
Předchozí
Následující