Représentation de graphes planaires par intersections de L.

Il a récemment été conjecturé que tout graphe planaire admet une représentation ou les sommets correspondent à des L dans le plan (un segment vertical et un segment horizontal, dont les extrémités basses et gauches coïncident) et où deux L s'intersectent si et seulement si les sommets correspondants sont voisins. C'est une conjecture ambitieuse puisqu'elle renforçerait la Conjecture de Scheinerman. Le but de ce stage est de trouver un contre-exemple à cette conjecture (ou bien de donner des indications pour éventuellement aider à sa résolution).

Le stage consistera à tester la conjecture sur de petits graphes planaires générés via plantri en programmant les 2 fonctions suivantes :

Une fonction qui étant donné un entier $n$, énumère toutes les permutations $\sigma$ à $n$ éléments (càd les bijections de $\{1\ldots n\}$ vers $\{1\ldots n\}$).

Une fonction qui étant donné une permutation $\sigma$ et un graphe planaire $G$ dont les sommets sont numérotés de $1$ à $n$, vérifie si il existe un 'système de L' dont le coin du L correspondant au sommet $i$ soit à la coordonnée $(i,\sigma(i))$.

Suivant l'avancée des travaux les stagiaires implémenteront des optimisations améliorant le temps d’exécution de ces tests.