Molti quesiti in geometria computazionale e combinatoria fanno riferimento allo studio di un gruppo finito di punti nel piano euclideo. Molti problemi di teoria dei grafi si configurano in questa ottica quando i bordi sono lineari. Una problematica rilevante riguarda il numero d'incrocio rettilineo (ad esempio, problemi di trasporto e ottimizzazione dell'impaginazione nella stampa): Qual è il numero minimo di incroci in un grafo completo disegnato tra n punti in un piano? Un grafo completo è quello in cui ogni punto (nodo) è collegato a tutti gli altri. Inoltre si assume la posizione più generica possibile per i nodi, questo comporta che nel grafo non ci siano tre nodi allineati.
Non è difficile vedere che con un numero di nodi minore o uguale a quattro non si verificano incroci nel grafo. Con cinque nodi si possono disegnare diverse configurazioni (qui si possono vedere quelle differenti per order types (introdotto da Goodman e Pollack nel 1983)). Se si disegnano cinque nodi formando una figura convessa ci sono cinque incroci. Il meglio che si può fare è avere un solo incrocio (non c'è modo di tracciare un grafo completo di cinque nodi senza incrocio, anche se i lati fossero curvi). Massimizzare il numero degli incroci è facile: basta posizionare tutti gli n nodi su di una circonferenza per ottenere il numero massimo degli incroci.
La caccia alla scoperta dei numeri d'incrocio di un grafo completo è iniziata con R. Guy negli anni '60. Fino al 2000 solo i valori per n<=9 erano conosciuti, nel 2001 è stato risolto il caso per n=10, mentre nel 2004 è stata la volta di n=11. L'obiettivo principale del seguente progetto è di utilizzare sofisticati metodi matematici (estensione tipi-ordine) per determinare il numero d'incrocio rettilineo per valori di n minori di 50. Finora abbiamo avuto successo per n <= 17. In lavori recenti (non ancora pubblicati) è stato scoperto il numero d'incrocio rettilineo per n=19 e n=21. E' diventato davvero irresistibile il richiamo a risolvere il problema per n=18, questo sarà l'obiettivo principale del progetto.
Un elenco aggiornato per ogni miglior set di n nodi conosciuto può essere consultato qui http://www.ist.tugraz.at/staff/aichholzer/crossings.html.