Een volledige graaf met 4 knopen kan getekend worden zonder kruisingenEen volledige graaf met 5 knopen heeft minimaal 1 kruising
Rectilinear Crossing Number is een distributed computing project dat onder het BOINC platform draait. Het doel van dit project is om het minimale aantal kruisingen te bepalen in grafen met rechte lijnen.
Aantal kruisingen bepalen
In een graaf met rechte lijnen met n knopen is het enorm moeilijk om het aantal minimale aantal kruisingen te bepalen. Voor kleine grafen, (bijvoorbeeld n = 4 of 5) is het nog eenvoudig, maar als het aantal knopen groter wordt, wordt het al snel moeilijk. Voor een volledige graaf met 20 knopen is het al niet meer bekend. Het is al wel bepaald voor grafen met minder dan 19 en 21 knopen. De moeilijkheid van het berekenen zit hem in het grote aantal verschillende configuraties. voor n = 11 zijn er al 2,334,512,907 verschillende configuraties.
De applicatie
De applicatie is een programma genaamd CAPE (Complete Abstract Pointset Extension). Deze applicatie neemt een beginsituatie van 11 punten en breidt deze vervolgens uit naar 12,13...,20 punten. Na iedere uitbreiding worden de situaties verwijderd waarin het aantal kruisingen zeker niet minimaal zal zijn, zelfs bij verdere uitbreiding. Niet eens alle beginsituaties van 11 punten hoeven gecontroleerd te worden. Hierdoor is de lengte van de "work units" (sets van uit te voeren berekeningen) zeer variabel en kan een work unit enkele minuten of meerdere uren in beslag nemen. Er is een maximum van 10 uur. Een work unit bestaat uit een beginsituatie van 11 punten en enkele getallen die de uitbreiding aangeven. Als blijkt dat dit te lang gaat duren wordt de work unit in meerdere eenheden opgedeeld.
