# Nombre de croisements (théorie des graphes)

En théorie des graphes, le nombre de croisements cr(G) d'un graphe G est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe G. Par exemple, un graphe est planaire si et seulement si son nombre de croisements est nul. La détermination du nombre de croisements tient une place importante dans le tracé de graphes. Un graphe à but informatif représenté avec peu de croisements facilite la compréhension de celui-ci.
L'étude du nombre de croisements trouve son origine dans le problème de l'usine de briques de Turán, dans lequel Pál Turán a demandé un plan d'usine qui minimiserait le nombre de croisements entre les voies reliant les fours à briques aux sites de stockage. Formellement, ce problème revient à trouver le nombre de croisements d'un graphe biparti complet. Le même problème s'est posé indépendamment en sociologie à peu près au même moment, en relation avec la construction de sociogrammes. La formule conjecturée de Turán pour les nombres de croisements de graphes bipartis complets reste à prouver, tout comme une formule analogue pour les graphes complets.
L'inégalité du nombre de croisements (en) indique que, pour les graphes où le nombre e d'arêtes est suffisamment supérieur au nombre n de sommets, le nombre de croisements est au moins proportionnel à e$^3$/n$^2$.
Sans autre précision, le nombre de croisements permet des dessins dans lesquels les arêtes peuvent être représentées par des courbes arbitraires. Une variante de ce concept, le nombre de croisements rectilignes, exige que toutes les arêtes soient des segments et est donc supérieur ou égal au nombre de croisements. En particulier, le nombre de croisements rectilignes d'un graphe complet est sensiblement le même que le nombre minimum de quadrilatères convexes déterminé par un ensemble de n points. Le problème de la détermination de ce nombre est étroitement lié au Happy Ending problem.

## Définitions

Dans le but de définir le nombre de croisements, le tracé d'un graphe non orienté est une application, des sommets du graphe vers des points distincs du plan, et des arêtes du graphe vers des courbes reliant leurs deux extrémités. Aucun sommet ne doit être appliqué sur une arête dont il n'est pas une extrémité, et chaque fois que deux arêtes ont des courbes qui se croisent (autre qu'à une extrémité partagée), leurs intersections doivent former un ensemble fini de croisements. Le nombre de croisements d'un graphe est alors le minimum du nombre de croisements sur tous ces tracés.
Certains auteurs ajoutent plus de contraintes à la définition d'un tracé, par exemple que chaque paire d'arêtes doit avoir au plus un point d'intersection. Pour le nombre de croisements tel que défini ci-dessus, ces contraintes ne font aucune différence, car un tracé qui minimise le nombre de croisements ne peut pas avoir d'arêtes avec plusieurs points d'intersection. Cependant, ces contraintes sont pertinentes pour les définitions de variantes du nombre de croisements qui, par exemple, ne comptent que le nombre de paires d'arêtes qui se croisent plutôt que le nombre de croisements.

## Cas particuliers

Les nombres de croisement sont connus pour très peu de familles de graphes. En particulier, à l'exception de quelques cas, le nombre de croisements de graphes complets, de graphes bipartis complets et de produits de cycles restent tous inconnus, bien qu'il y ait eu quelques progrès sur les bornes inférieures.

### Graphes bipartis complets

Pendant la Seconde Guerre mondiale, le mathématicien hongrois Pál Turán a été contraint de travailler dans une usine de briques, poussant des wagons de briques des fours aux sites de stockage. L'usine avait des pistes de chaque four à chaque site de stockage, et les wagons étaient plus difficiles à pousser aux points où les pistes se croisaient, d'où Turán a été conduit à poser son problème d'usine de brique: comment les fours, les sites de stockage et les pistes être organisé pour minimiser le nombre total de croisements ? Mathématiquement, les fours et les sites de stockage peuvent être formalisés comme les sommets d'un graphe biparti complet, avec les pistes comme arêtes. Un plan d'usine peut être représenté comme un dessin de ce graphe, le problème devient donc : quel est le nombre de croisements d'un graphe biparti complet ?
Kazimierz Zarankiewicz a tenté de résoudre le problème de l'usine de briques de Turán ; sa preuve contenait une erreur, mais il a établi un majorant correct :
    ${\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor$
pour le nombre de croisements du graphe biparti complet K$_{m,n}$. Cette borne est conjecturée être le nombre de croisements pour tous les graphes bipartis complets.

### Graphes complets et coloration de graphes

Le problème de la détermination du nombre de croisements d'un graphe complet a été posé pour la première fois par Anthony Hill en 1960. Hill et son collaborateur John Ernest étaient deux artistes constructivistes fascinés par les mathématiques. Ils ont non seulement formulé ce problème, mais ont également proposé une conjecture pour ce nombre de croisements, que Richard K. Guy a publiée en 1960. On sait qu'il existe toujours un tracé avec
    ${\textrm {cr}}(K_{p})\leq {\frac {1}{4}}\left\lfloor {\frac {p}{2}}\right\rfloor \left\lfloor {\frac {p-1}{2}}\right\rfloor \left\lfloor {\frac {p-2}{2}}\right\rfloor \left\lfloor {\frac {p-3}{2}}\right\rfloor$
croisements. Cette formule donne les valeurs 1, 3, 9, 18, 36, 60, 100, 150 pour p = 5, ..., 12 ; (suite A000241 de l'OEIS). La conjecture est qu'il ne peut y avoir de meilleur tracé, de sorte que cette formule donne le nombre optimal de croisements pour les graphes complets. Une formulation indépendante de la même conjecture a été faite par Thomas L. Saaty en 1964.
Saaty a en outre vérifié que cette formule donne le nombre optimal de croisements pour p ≤ 10 et Pan et Richter ont montré qu'elle était également optimale pour p = 11, 12.
La conjecture d'Albertson, formulée par Michael O. Albertson en 2007, déclare que, parmi tous les graphes de nombre chromatique n, le graphe complet K$_n$ a le nombre minimum de croisements. On sait aujourd'hui que la conjecture d'Albertson est valable pour n ≤ 16.

### Graphes cubiques

Les plus petits graphes cubiques avec les nombres de croisement 1..., 8 et 11 sont connus (suite A110507 de l'OEIS). Le plus petit graphe cubique à 1 croisement est le graphe biparti complet K$_{3,3}$, avec 6 sommets. Le plus petit graphe cubique à 2 croisements est le graphe de Petersen, avec 10 sommets. Le plus petit graphe cubique à 3 croisements est le graphe de Heawood, avec 14 sommets. Le plus petit graphe cubique à 4 croisements est le graphe de Möbius-Kantor, avec 16 sommets. Le plus petit graphe cubique à 5 croisements est le graphe de Pappus, avec 18 sommets. Le plus petit graphe cubique à 6 croisements est le graphe de Desargues, avec 20 sommets. Aucun des quatre graphes cubiques à 7 croisements, avec 22 sommets, n'est parfaitement connu. Les plus petits graphes cubiques à 8 croisements incluent le graphe de Nauru et le graphe de McGee ou (3,7)-cage, avec 24 sommets. Les plus petits graphes cubiques à 11 croisements incluent le graphe de Coxeter avec 28 sommets.
En 2009, Pegg et Exoo ont conjecturé que le plus petit graphe cubique avec un nombre de croisements valant 13 est le graphe de Tutte–Coxeter, valant 170 est le 12-cage de Tutte$^,$.

## Complexité et approximation

En général, la détermination du nombre de croisements d'un graphe est difficile ; Garey et Johnson ont montré en 1983 qu'il s'agissait d'un problème NP-difficile. En fait, le problème reste NP-difficile même lorsqu'il est restreint aux graphes cubiques et aux graphes quasi-planaires (graphes qui deviennent planaires après suppression d'un seul sommet). Un problème étroitement lié, à savoir la détermination du nombre de croisements rectilignes, est complet pour la théorie existentielle sur les réels.
Il existe des algorithmes efficaces pour déterminer si le nombre de croisements est inférieur à une constante fixe k. En d'autres termes, le problème est traitable à paramètre fixe$^,$. Il existe également des algorithmes d'approximation efficaces pour approximer cr(G) sur des graphes de degré borné. En pratique, des algorithmes heuristiques sont utilisés, tels que l'algorithme simple qui commence sans arêtes et ajoute continuellement chaque nouvelle arête d'une manière qui produit le moins de croisements supplémentaires possible. Ces algorithmes sont utilisés dans le projet de calcul distribué Rectilinear Crossing Number.

## L'inégalité du nombre de croisements

Pour un graphe non orienté G avec n sommets et e arêtes tels que e > 7n, le nombre de croisements minoré par
    $\operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}$.
Cette relation entre les arêtes, sommets et nombre de croisements a été trouvé indépendamment par Ajtai, Chvátal, Newborn et Szemerédi et par Leighton. Il est connu sous le nom d'inégalité des nombres de croisement ou de lemme de croisement.
La constante 29 est la meilleure connue à ce jour et est due à Ackerman. La constante 7 peut être abaissée à 4, mais au détriment 64 à la place de 29.$^,$
Székely a montré que cette inégalité donnait des preuves très simples de certains théorèmes importants de la géométrie d'incidence, tels que le théorème de Beck, et le théorème de Szemerédi-Trotter.

## Nombre de croisements rectilignes

Les nombres de croisement rectilignes pour à K$_n$ pour n de 5 à 12 sont 1, 3, 9, 19, 36, 62, 102, 153, (suite A014540 de l'OEIS). Les valeurs sont connues jusqu'à K$_{27}$, et K$_{28}$ à un nombre de croisements rectilignes égal à 7233 ou 7234. D'autres valeurs sont collectées par le projet Rectilinear Crossing Number.