The conjecture that optimal rectilinear drawings of KnK_n are 3-decomposable

For a positive integer nn, let KnK_n be the complete graph drawn with straight-line edges on a point set in general position. A drawing is optimal if it minimizes the number of crossings among rectilinear drawings of KnK_n, and it is 3-decomposable if its underlying point set admits the three-part decomposition described in the paper.

3-decomposability conjecture. For each positive integer nn divisible by 33, all optimal rectilinear drawings of KnK_n are 3-decomposable.

The conjecture is motivated by the fact that all best crossing-wise known drawings have underlying point sets minimizing the number of (k)(\leq k)-sets for every kn/3k\leq n/3, a property equivalent to 3-decomposability. It remains open in general.

Sources & referencesView supporting material

Primary source

B. Ábrego, M. Cetina, S. Fernández–Merchant, J. Leaños and G. Salazar, “3–symmetric and 3–decomposable drawings of K_n (extended version)”, arXiv:0805.0016 (2008).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.