Présentation du domaine: les propriétés géométiques et algorithmiques des graphes planaires ont été introduites dans le cours INF562 (Géoméstrie Algorithmique). Comme il a été mentionné en cours, certaines définitions (de carte combinatoire) et propriétés admettent une généralisation naturelle au cas des graphes plongés sur des surfaces.

Les propriétés combinatoires et algorithmiques des surfaces combinatoire constituent l'un des objets d'étude d'un sous-domaine "récent" de la géométrie algorithmique, connu sous le nom de topologie algorithmique (computational topology en anglais). Dans ce cadre on s'intéresse à des surfaces combinatoires: sans fournir ici une définition rigoureuse, on va juste rappeler qu'une carte (topologique) de genre supérieur est donnée par un plongement cellulaire d'un graphe sur une surface (les faces sont toutes homéomorphes à un disque topologique): ainsi une surface combinatoire peut se voir comme obtenue par recollement d'un ensemble de polygones (le long des aretes).
Comme il est facile d'imaginer, la compréhension des résultats dans ce domaine "necessite la connaissance" de certaines notions élémentaires de topologie, telles que: le théorème de classification des surfaces, la notion de schéma polygonal d'une surface (en gros, un polygone dont les cotes sont identifiées), la notion d'homotopie, éventuellement celle de revetement universel (pour certains algorithmes), ...

Motivations et applications: l'une des applications principales est probablement la possibilité, une fois trouvé un système de lacets non contractiles, de calculer éfficacement une planarization du graphe: il suffit de couper la surface le long des lacets pour obtenir un graphe planaire. Ce qui a des applications, par exemple, dans le domaine du paramétrage: trouver une paramétrization planaire d'un graphe permet de plaquer facilement des textures sur une surface (voir la Fig. 3 ci-dessous).

Objectifs du projet: étant donnée la quantité de techniques algorithmiques et des notions de topologie à maitriser, on va considérer à un problème spécifique, celui du calcul du plus court lacet non contractile, qui a fait l'objet de plusieurs travaux.
En particulier on va s'intéresser à l'algorithme proposé par Erickson et Har-Peled[1]: on suggère de suivre la présentation fournie par Eric Colin de Verdière (Chap. 4 dans [2]), ainsi que les notes de cours de J. Erickson [3].
Une première remarque (due à Thomassen), permet d'obtenir facilement un algorithme de complexité O(n^3). L'idée est très simple, et basée sur la propriété suivante:
étant donnés deux points p et q sur une surface S, et 3 chemins qui vont de p à q, alors on a: si ab et bc sont des cycles contractiles, alors le chemain ac est aussi contractile (où ab dénote la concaténation des chemins a et b).

L'algorithme proposé dans [1] est plus éfficace, étant de complexité O(n^2 log n): l'un des ingrédients principaux est le calcul de plus courts chemins dans un graphe.

L'objectif du projet est la "compréhension" des techniques proposées dans [1] (et bien expliquées dans [2] et [3]) nécéssaires pour l'implementation de l'algorithme qui calcule un lacet non contractile de longueur minimale.