Je suis actuellement ATER à l'Université Nice Côté d'Azur, rattaché à l'i3S. Les thèmes principaux de mes travaux de recherche sont le dessin de graphes et la topologie des graphes. J'ai également travaillé sur le division et la racine de graphes fonctionnels en rapport avec le produit direct. J'ai obtenu un doctorat en informatique de l'université Côte d'Azur, dirigé par Enrico Formenti.
Téléchargement de ma thèse ici
Les graphes constituent des structures de données éminemment utilisées, tant d'un point de vue théorique que pratique. De par leur importance, il est nécessaire de trouver des outils permettant de les représenter au mieux afin de faire émerger, à partir des données abstraites, les informations latentes qui s'y dissimulent.
Le dessin de graphes est l'un de ces outils et il constitue un domaine de recherche vivace où existent de très nombreux algorithmes, s'intéressant chacun à des propriétés précises du graphe ou de sa représentation. On peut citer, entre autres, l'angle minimal que forment deux arêtes adjacentes, l'homogénéité de la longueur des arêtes, le nombre de brisures des arêtes ou encore leur nombre de croisements. Pour certains de ces paramètres, le fait de les optimiser est une tâche ardue. C'est le cas tout particulièrement du problème de minimisation du nombre de croisements d'arêtes, qui s'avère être, en général, au moins NP-Complet.
Plusieurs approches peuvent être explorées pour s'attaquer à ce problème, soit par le biais d'algorithmes généralistes, soit par le biais d'heuristiques plus spécialisées, chacun offrant un équilibre différent entre résultat et performances. Dans cette thèse, nous définissons une nouvelle heuristique, basée sur le repositionnement itératif de sommets, et offrant une paramétrisation visant à régler de manière fine cet équilibre entre croisements et temps d'exécution.
Pour aller encore plus loin, une question légitime est de se demander ce que donneraient ces algorithmes s'ils étaient appliqués dans des contextes différents, notamment lorsque l'on s'essaye à représenter des graphes sur d'autres surfaces que le plan Euclidien. Ce changement de paradigme apporte de nouveaux degrés de liberté pour la visualisation de graphes, notamment dans la minimisation du nombre de croisements, tout en posant de nouveaux défis dans la façon d'adapter les mécanismes à l’œuvre dans un nouveau modèle de représentation. Nous introduisons deux algorithmes, l'un optant pour une approche dynamique du dessin de graphes sur le tore par simulation de forces, le second faisant le lien entre les représentations combinatoires et géométriques de graphes sur la bouteille de Klein.