- View PDF version of TR-2000-11 (285093 bytes)
- View PostScript version of TR-2000-11
- Save PostScript version of TR-2000-11
- Save gzipped PostScript version of TR-2000-11 (123245 bytes)

- Toward the Rectilinear Crossing Number of K_n: New Drawings, Upper Bounds, and Asymptotics, September 14, 2000 Alex Brodsky, Stephane Durocher and Ellen Gethner, 13 pages
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.

If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.