La méthode utilise une représentation du graphe dans le plan à coordonnées entières d'ordre O(n) et des algorithmes de géométrie calculatoire "Planar Point Location".
Le but du projet est d'implanter cette construction, en utilisant les algorithmes de graphes planaires appropriés, si possible de l'améliorer (notamment préciser la constante A), de la tester sur des "grands" graphes choisis aléatoirement.
Ce projet se rattache à un domaine de recherche très actif et peut faire l'objet d'une poursuite en thèse. Les possibilités d'extension sont nombreuses, notamment pour les graphes représentés sur des surfaces non planaires.
Mot-clés : algorithmes, théorie des graphes
Références :
[CGKT09] B. Courcelle, C. Gavoille, M. Kanté, and A. Twigg. Optimal Labeling for Connectivity Checking in Planar Networks with Obstacles (sections 1 à 4).
Ouvrages de géométrie algorithmique cités dans cet article.