3-symmetric and 3-decomposable geometric drawings of Kn Article uri icon

abstract

  • Even the most superficial glance at the vast majority of crossing-minimal geometric drawings of Kn reveals two hard-to-miss features. First, all such drawings appear to be 3-fold symmetric (or simply 3-symmetric). And second, they all are 3-decomposable, that is, there is a triangle T enclosing the drawing, and a balanced partition A, B, C of the underlying set of points P, such that the orthogonal projections of P onto the sides of T show A between B and C on one side, B between A and C on another side, and C between A and B on the third side. In fact, we conjecture that all optimal drawings are 3-decomposable, and that there are 3-symmetric optimal constructions for all n multiples of 3. In this paper, we show that any 3-decomposable geometric drawing of Kn has at least 0.380029 (frac(n, 4)) %2b Θ (n3) crossings. On the other hand, we produce 3-symmetric and 3-decomposable drawings that improve the general upper bound for the rectilinear crossing number of Kn to 0.380488 (frac(n, 4)) %2b Θ (n3). We also give explicit 3-symmetric and 3-decomposable constructions for n < 100 that are at least as good as those previously known. © 2009 Elsevier B.V. All rights reserved.

publication date

  • 2010-01-01