Rectilinear Crossing Number
Rectilinear Crossing Number（通常缩写为RCN）是由奥地利格拉茨技术大学运作的，基于 BOINC 平台的分布式计算项目。Rectilinear Crossing Number 的目标是尝试借助BOINC能召集的计算力来寻找平面化完全图最小交叉数。目前项目已经得到了阶数小于等于17的完全图的交叉数，还有直到阶数为100的完全图交叉数的一些下界。目前项目正在进行对于18阶完全图的搜索。
该项目基于 BOINC 平台，简要的加入步骤如下（已完成的步骤可直接跳过）：
- 下载并安装 BOINC 的客户端软件（官方下载页面或程序下载）
- 点击客户端简易视图下的“Add Project”按钮，或高级视图下菜单中的“工具->加入项目”，将显示向导对话框
- 点击下一步后在项目列表中找到并单击选中 Rectilinear Crossing Number 项目（如未显示该项目，则在编辑框中输入项目网址：http://dist.ist.tugraz.at/cape5/ ），然后点击下一步
在图论，交叉数是指一个图在平面上，边的交叉点的最小数目。一个图在平面上可以有多种画法，若有多于两条边相交于同一点，每对相交边计算一次。给定一个图，计算其交叉数是一个NP-hard的问题。Rectilinear Crossing Number 想要解决的就是这个问题的一个特殊情况，也就是当图为完全图时候的情况。目前项目已经得到了阶数小于等于17的完全图的交叉数，还有直到阶数为100的完全图交叉数的一些下界，详细的结果请参看这里（英文）。
What is the Rectilinear Crossing Number Project?
Many 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.