Ce travail de thèse traite du maintien dynamique de représentations géométriques de graphes. Le manuscrit met en avant des connexions fortes entre trois types de représentation de graphes : les décompositions de graphes, les modèles géométriques et les représentations arborescentes à degrés de liberté (PQ-arbres, PC-arbres et autres structures du même type). De nouvelles relations entre ces objets sont mises en évidence et d'autres déjà connues sont approfondies. Notamment, il est établi une équivalence mathématique et algorithmique entre la décomposition modulaire des graphes d'intervalles et le PQ-arbre de leurs cliques maximales.<br /><br />Les connexions entre les trois types de représentation précités sont exploitées pour la conception d'algorithmes de reconnaissance entièrement dynamiques pour les cographes orientés, les graphes de permutation et les graphes d'intervalles. Pour les cographes orientés, l'algorithme présenté est de complexité optimale, il traite les modifications de sommet en temps O(d), où d est le degré du sommet en question, et les modifications d'arête en temps constant. Les algorithmes pour les graphes de permutation et les graphes d'intervalles ont la même complexité : les modifications d'arête et de sommet sont traitées en temps O(n), où n est le nombre de sommets du graphe. Une des contributions du mémoire est de mettre en lumière des similarités très fortes entre les opérations d'ajout d'un sommet dans un graphe de permutation et dans un graphe d'intervalles. <br />L'approche mise en oeuvre dans ce mémoire est assez générale pour laisser entrevoir les mêmes possibilités algorithmiques pour d'autres classes de graphes définies géométriquement.

La géométrie algorithmique a pour but de concevoir et d'analyser des algorithmes pour résoudre des problèmes géométriques. C'est un domaine récent de l'informatique théorique, qui s'est très rapidement développé depuis son apparition dans la thèse de M. I. Shamos en 1978. La randomisation permet d'éviter le recours à des structures compliquées, et s'avère très efficace, tant du point de vue de la complexité théorique, que des résultats pratiques. Nous nous sommes intéressés plus particulièrement à la conception d'algorithmes dynamiques : en pratique, il est fréquent que l'acquisition des données d'un problème soit progressive. Il n'est évidemment pas question de recalculer le résultat à chaque nouvelle donnée, d'où la nécéssité d'utiliser des schémas (semi-)dynamiques. Nous introduisons une structure très générale, le graphe d'influence, qui permet de construire de nombreuses structures géométriques : diagrammes de Voronoï, arrangements de segments... Nous étudions les algorithmes, à la fois du point de vue de la complexité théorique, de leur mise en oeuvre pratique et de l'efficacité des programmes.