Point sets that minimize $(\le k)$-edges, 3-decomposable drawings, and the rectilinear crossing number of $K_{30}$

Details Point sets that minimize $(\le k)$-edges, 3-decomposable drawings, and the rectilinear crossing number of $K_{30}$ Point sets that minimize $(\le k)$-edges, 3-decomposable drawings, and the rectilinear crossing number of $K_{30}$

2010-09-23

arxiv.org/abs/1009.4736v2

Mathematics

Combinatorics

14 pages

Scientific paper

10.1016/j.disc.2011.03.030

There are two properties shared by all known crossing-minimizing geometric drawings of $K_n$, for $n$ a multiple of 3. First, the underlying $n$-point set of these drawings has exactly $3\binom{k+2}{2}$ $(\le k)$-edges, for all $0\le k < n/3$. Second, all such drawings have the $n$ points divided into three groups of equal size; this last property is captured under the concept of 3-decomposability. In this paper we show that these properties are tightly related: every $n$-point set with exactly $3\binom{k+2}{2}$ $(\le k)$-edges for all $0\le k < n/3$, is 3-decomposable. As an application, we prove that the rectilinear crossing number of $K_{30}$ is 9726.

Affiliated with

Also associated with

No associations

Rating

Point sets that minimize $(\le k)$-edges, 3-decomposable drawings, and the rectilinear crossing number of $K_{30}$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Point sets that minimize $(\le k)$-edges, 3-decomposable drawings, and the rectilinear crossing number of $K_{30}$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Point sets that minimize $(\le k)$-edges, 3-decomposable drawings, and the rectilinear crossing number of $K_{30}$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-273744