Computer Science – Discrete Mathematics
Scientific paper
2000-09-22
Electronic Journal of Combinatorics. 8(1):R23 1-30. 2001
Computer Science
Discrete Mathematics
17 Pages, colour figures
Scientific paper
A drawing of a graph G in the plane is said to be a rectilinear drawing of G if the edges are required to be line segments (as opposed to Jordan curves). We assume no three vertices are collinear. The rectilinear crossing number of G is the fewest number of edge crossings attainable over all rectilinear drawings of G. Thanks to Richard Guy, exact values of the rectilinear crossing number of K_n, the complete graph on n vertices, for n = 3,...,9, are known (Guy 1972, White and Beinke 1978, Finch 2000, Sloanes A014540). Since 1971, thanks to the work of David Singer (1971, Gardiner 1986), the rectilinear crossing number of K_10 has been known to be either 61 or 62, a deceptively innocent and tantalizing statement. The difficulty of determining the correct value is evidenced by the fact that Singer's result has withstood the test of time. In this paper we use a purely combinatorial argument to show that the rectilinear crossing number of K_10 is 62. Moreover, using this result, we improve an asymptotic lower bound for a related problem. Finally, we close with some new and old open questions that were provoked, in part, by the results of this paper, and by the tangled history of the problem itself.
Brodsky Alex
Durocher Stephane
Gethner Ellen
No associations
LandOfFree
The Rectilinear Crossing Number of K_10 is 62 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 The Rectilinear Crossing Number of K_10 is 62, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Rectilinear Crossing Number of K_10 is 62 will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-532366