Project SummaryMany questions in computational and combinatorial geometry are based on finite sets of points in the Euclidean plane. Several problems from graph theory also fit into this framework, when edges are restricted to be straight. A typical question is the prominent problem of the rectilinear crossing number (related to transport problems and optimization of print layouts for instance): What is the least number of crossings a straight-edge drawing of the complete graph on top of a set of n points in the plane obtains? Here complete graph means that any pair of points is connected by a straight-edge. Moreover we assume general position for the points, i.e., no three points lie on a common line.

It is not hard to see that we can place four points in a way so that no crossing occurs. For five points the drawing shows different ways to place them (these are all different order types (introduced by Goodman and Pollack in 1983)). If you place five points in convex positions then there are five crossings. The best you can do is to get only one crossing (there is no way to draw a complete graph on five points without crossings, even if you allow the edges to be curves). BTW: Maximizing the number of crossings is easy: Just place all n points on a circle to get the maximum of n choose 4 crossings.

For larger point sets it is very hard to determine the best configuration. The main reason is that the number of combinatorially different ways to place those points grows exponentially. For example already for n=11 there are 2,334,512,907 different configurations.

The remarkable hunt for crossing numbers of the complete graph has been initiated by R. Guy in the 1960s. Till the year 2000 only values for n<=9 have been found, in 2001 n=10 was solved and the case n=11 was settled in 2004. The main goal of the current project is to use sophisticated mathematical methods (abstract extension of order types) to determine the rectilinear crossing number for small values of n. So far we have been successful for n <= 17. From very recent (not even published yet) mathematical considerations the rectilinear crossing numbers for n=19 and n=21 are also known. So the most tantalizing problem now is to determine the true value for n=18, which is the main focus of this project.

An updated list for the best point sets known so far can be found at

http://www.ist.tugraz.at/staff/aichholzer/crossings.html.ApplicationsThe following applications are supported:

Microsoft Windows X86 (32bit)

Microsoft Windows X86_64 (64bit)

Linux X86 (32bit)

Linux X86_64 (64bit)

Mac OS X Intel

Connecting to Rectilinear Crossing NumberThe project's Home Page is located at:

http://dist.ist.tugraz.at/cape5/Rectilinear Crossing Number is also listed in the various BOINC Account Managers and you can join this project through them directly.

Don't forget to join BOINC@Australia Team following your registration.

StatisticsView our Team Members List and their current score

hereView detailed BOINCStats of our Rectilinear Crossing Number Team

here