Toward the Rectilinear Crossing Number of $K_n$: New Drawings, Upper Bounds, and Asymptotics
<|reference_start|>Toward the Rectilinear Crossing Number of $K_n$: New Drawings, Upper Bounds, and Asymptotics: Scheinerman and Wilf (1994) assert that `an important open problem in the study of graph embeddings is to determine the rectilinear crossing number of the complete graph K_n.' A rectilinear drawing of K_n is an arrangement of n vertices in the plane, every pair of which is connected by an edge that is a line segment. We assume that no three vertices are collinear, and that no three edges intersect in a point unless that point is an endpoint of all three. The rectilinear crossing number of K_n is the fewest number of edge crossings attainable over all rectilinear drawings of K_n.   For each n we construct a rectilinear drawing of K_n that has the fewest number of edge crossings and the best asymptotics known to date. Moreover, we give some alternative infinite families of drawings of K_n with good asymptotics. Finally, we mention some old and new open problems.<|reference_end|>
@article{brodsky2000toward,
    title={Toward the Rectilinear Crossing Number of $K_n$: New Drawings, Upper
  Bounds, and Asymptotics},
    author={Alex Brodsky, Stephane Durocher, Ellen Gethner},
    journal={Discrete Mathematics. 262(1-3):59-77. 2003},
    year={2000},
    doi={10.1016/S0012-365X(02)00491-0},
    archivePrefix={arXiv},
    eprint={cs/0009028},
    primaryClass={cs.DM cs.CG math.CO}
}