ECOLE DE RECHERCHE
École de printemps d’informatique théorique
Graphes et surfaces : Algorithmique, combinatoire et topologie
9 au 13 mai 2016
Cette École de Printemps d’Informatique Théorique portera sur les graphes topologiques, c’est-à-dire représentés dans le plan ou plus généralement sur des surfaces ou dans l’espace. Les graphes sont un objet fondamental de l’informatique, et bien souvent ceux que nous manipulons sont d’origine géométrique : par exemple, ils sont dessinables dans le plan avec peu ou pas de croisements, ou sur une surface topologiquement simple. De tels graphes possèdent des propriétés structurelles qui permettent de résoudre des problèmes algorithmiques sur ceux-ci plus efficacement que sur des graphes abstraits quelconques. Par ailleurs, des questions spécifiques, de nature combinatoire ou topologique, se posent pour ces graphes.

Cette École se veut être une introduction aux diverses facettes des graphes topologiques : algorithmique, combinatoire, structurelle, topologique, etc., et à leurs interactions. Elle se situe donc à la croisée de différents domaines des mathématiques et de l’informatique théorique : combinatoire énumérative et bijective, topologie de petite dimension, algorithmique et théorie structurelle des graphes, géométrie algorithmique. Elle s’adresse aux étudiants et chercheurs intéressés en mathématiques et informatique théorique, et tout spécialement aux doctorants aux jeunes chercheurs.  Il n’y a aucun prérequis, toutes les notions utiles seront introduites.

Les cours seront donnés en français ou en anglais.  Les supports de cours et transparents seront en anglais.


Comité scientifique

Éric Colin de Verdière (ENS Paris)
Frédéric Magniez (Université Paris Diderot)
Gilles Schaeffer (Ecole polytechnique)

Comité d’organisation

Éric Colin de Verdière (ENS Paris)
Gilles Schaeffer (Ecole polytechnique)

Conférenciers

Cours longs:

Aspects topologiques

  • Bojan Mohar (Simon Fraser University & University of Ljubljana) 

Aspects structurels

Aspects combinatoires

Aspects algorithmiques
 

Cours courts :

Aspects de coloration

Dimension supérieure