The conjecture that optimal rectilinear drawings of are 3-decomposable
The conjecture that optimal rectilinear drawings of are 3-decomposable
For a positive integer , let 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 , 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 divisible by , all optimal rectilinear drawings of 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 -sets for every , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.