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.