Rectilinear Crossing Number

当前页面或段落存在质量问题 当前页面或段落不符合页面质量要求，使用了不规范的语言或是提供了错误的信息，可能误导读者，希望了解相关内容的Wiki用户协助改善。 用户 cuihao 给出的意见是：没翻译 。 其他用户若有异议，请前往讨论:Rectilinear Crossing Number发表见解。 欢迎无wiki账号的用户到论坛的Wiki系统讨论区（注册）参与讨论。

Rectilinear Crossing Number
Rectilinear Crossing Number logo
Rectilinear Crossing Number 运行中的图形界面
开发者	奥地利格拉茨技术大学
版本历史	2006年6月30日
计算程序
子项目
项目平台	BOINC 平台
项目类别	数学
项目状态	已结束
官方网址	Rectilinear Crossing Number
项目文献	分类:Rectilinear Crossing Number 相关文献
	通过 RSS 获取项目新闻

Rectilinear Crossing Number（通常缩写为RCN）是由奥地利格拉茨技术大学运作的，基于 BOINC 平台的分布式计算项目。Rectilinear Crossing Number 的目标是尝试借助BOINC能召集的计算力来寻找平面化完全图最小交叉数。目前项目已经得到了阶数小于等于17的完全图的交叉数，还有直到阶数为100的完全图交叉数的一些下界。目前项目正在进行对于18阶完全图的搜索。

如何加入项目

该项目基于 BOINC 平台，简要的加入步骤如下（已完成的步骤可直接跳过）：

1. 下载并安装 BOINC 的客户端软件（官方下载页面或程序下载）
2. 点击客户端简易视图下的“Add Project”按钮，或高级视图下菜单中的“工具->加入项目”，将显示向导对话框
3. 点击下一步后在项目列表中找到并单击选中 Rectilinear Crossing Number 项目（如未显示该项目，则在编辑框中输入项目网址：http://dist.ist.tugraz.at/cape5/ ），然后点击下一步
4. 输入您可用的电子邮件地址，并设置您在该项目的登录密码（并非您的电子邮件密码）
5. 再次点击下一步，如项目服务器工作正常（并且有适合自身操作系统的计算程序），即已成功加入项目

更详细的加入方法说明，请访问 BOINC 新手指南 或 BOINC 使用教程。

本站推荐您加入 Team China 团队，请访问项目官方网站的 团队检索页面，搜索（Search）并进入 Team China 的团队页面，点击页面中的 Join 并输入用户登录信息即可加入！

项目研究内容简介与成果

在图论，交叉数是指一个图在平面上，边的交叉点的最小数目。一个图在平面上可以有多种画法，若有多于两条边相交于同一点，每对相交边计算一次。给定一个图，计算其交叉数是一个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.

相关链接

官方网站
项目新闻中文翻译