Rectilinear Crossing Number Project

Rectilinear Crossing Number Project
Project logo
Project
Status	Completed
Category	Mathematics
Compute	CPU
Requires	None
Development
Developer	Institute for Software Technology, Graz University of Technology
Author	Oswin Aichholzer
Sponsor	Graz University of Technology
Initial release	July 25, 2006  (20 years ago)
Completed	Yes
Software
Operating system	Windows, Linux
Metadata
Website	http://dist.ist.tugraz.at/cape5

Rectilinear Crossing Number Project (internally referred to by its developers as cape5, and often abbreviated RCN or RCP) was a BOINC volunteer computing project in computational geometry operated by the Institute for Software Technology at Graz University of Technology in Austria. The project asked volunteers' computers to search for optimal straight-line drawings of complete graphs in order to help settle open cases of the rectilinear crossing number problem, a long-standing question in combinatorics first raised by Richard K. Guy in the 1960s.

The project was announced by BOINC founder David Anderson on 25 July 2006, alongside two other new BOINC-based projects, Riesel Sieve and Spinhenge@home.

The mathematical problem

A rectilinear drawing of a graph places each vertex at a point in the plane, in general position (no three points collinear), and represents each edge as a straight line segment. The rectilinear crossing number of a graph $G$, denoted $\overline{cr}(G)$, is the minimum possible number of pairs of crossing edges over all such drawings.

For the complete graph $K_n$, computing $\overline{cr}(K_n)$ is equivalent to finding a set of $n$ points in the plane, in general position, that minimizes the number of convex quadrilaterals formed by the points. Exact values were known only for small $n$ for decades; determining $\overline{cr}(K_n)$ for larger $n$ is NP-hard to decide against a fixed target, and the number of possible point configurations grows explosively with $n$, making the problem well suited to distributed search.

Progress on the problem before the BOINC project was slow: only values up to $n=9$ were known before 2000, $n=10$ was settled in 2001, and $n=11$ in 2004, using a technique called abstract order type extension developed by Aichholzer, Aurenhammer and Krasser. By the time the same method had pushed the known range up to $n\le 17$, and had also produced (not-yet-published) results for $n=19$ and $n=21$, the case $n=18$ remained the most tantalizing unsolved instance, and became the specific target of the BOINC project.

History

The rectilinear crossing number project, nicknamed "cape5" after the server directory in which it was hosted (dist.ist.tugraz.at/cape5), was developed by the Institute for Software Technology at Graz University of Technology and built on prior mathematical work by Oswin Aichholzer, Franz Aurenhammer and Hannes Krasser. The project distributed workunits, dubbed "cape-crossing" jobs, that tested candidate point configurations for the complete graph K18, aiming to prove that no configuration could beat the best drawings already found by other means.

Volunteer participation grew quickly after launch. By mid-2007 the project reported issuing over 525,000 workunits for a single generation of the search, and its community had reached a combined output of roughly three CPU-years of computation in a single day. Some individual workunits ran for exceptionally long periods on volunteers' machines, with one participant reporting a single completed workunit that had run for 542 hours. The project's success led the team to acquire a second dedicated server, which they intended to reuse for a planned successor project, provisionally named "SUDOKU," that would search for the smallest possible starting configuration of the puzzle; it is not confirmed whether this successor project was ultimately released.

In January of a later year the project introduced a second, Linux-only scientific application named "rcross," which added checkpointing and progress-bar support; this application was initially limited to Linux crunchers before being extended to other platforms.

The project credited several volunteers by name for contributions beyond crunching, including a project logo designed by a volunteer known as "Cori," an image of Delaunay and Voronoi diagrams contributed by M. Sanner, a favicon by "Rebirther," translations into Russian, Polish and Italian by volunteer translators, and an official screensaver programmed by a volunteer known as "S@NL FilmFreak."

Screensaver

The project's official BOINC screensaver, created by community volunteer "S@NL FilmFreak," visualized the crossing-minimization search in real time. A recorded playthrough of the screensaver has been preserved on video:

Load video

YouTube

YouTube might collect personal data. Privacy Policy

Continue Dismiss

Rectilinear Crossing Number Project screensaver

Results

The project's principal scientific result was the determination that the rectilinear crossing number of the complete graph on 18 vertices is

$\overline{cr}(K_{18})=1029$,

a value the team described as having been found "after months of distributed computing." This settled what had been, at the time, the smallest open case of the rectilinear crossing number problem.

The K18 value was subsequently confirmed and extended by other researchers, who additionally determined the values for $n=20$ and $n=22$ through $n=27$ using independent, non-distributed analytical methods; as of that work, the next unresolved case, $n=28$, was narrowed to either 7233 or 7234. An updated table of best known values for larger $n$ continues to be maintained by Oswin Aichholzer.

The known values of $\overline{cr}(K_n)$ for small $n$, including the K18 result attributed to the project, are catalogued in the On-Line Encyclopedia of Integer Sequences as sequence A014540.

Publications

Papers that used data computed by the project

• (2008).The maximum number of halving lines and the rectilinear crossing number of Kn for n≤27. Electronic Notes in Discrete Mathematics. pp. 261-266. - Confirmed the project's K18 result and extended exact values to K20 and K22 through K27.

Related background and methodology papers

• (2006).On the Crossing Number of Complete Graphs. Computing. pp. 165-176. DOI: 10.1007/s00607-005-0133-3. - Describes the abstract order type extension method underlying the project's search strategy, and establishes $\overline{cr}(K_{11})=102$ and $\overline{cr}(K_{12})=153$.
• (2020).An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants. Journal of Graph Algorithms and Applications. pp. 421-432. - Later continuation of research into asymptotic crossing constants building on the same problem area.

See also

• BOINC
• Crossing number (graph theory)
• Complete graph
• Computational geometry

External links

• https://web.archive.org/web/20090101000000*/dist.ist.tugraz.at/cape5
• http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/
• https://oeis.org/A014540