Pierre Rosenstiehl, directeur d’études

Combinatoire et graphes. Taxiplanie

1Les ordinateurs graphiques permettent de mieux en mieux de multiplier les visualisations dynamiques, d’expérimenter en trois dimensions, ce qui conduit à formuler des conjectures auparavant inaccessibles. On en est ainsi venu, non seulement à maîtriser topologiquement des objets complexes plongés dans le plan, mais aussi à savoir les déformer algorithmiquement, et de façon efficace, tout en leur imprimant des contraintes géométriques d’alignement, de direction, de distance, d’angle, et de pas entiers. De là apparaît une nouvelle lecture des objets graphiques d’origines naturelle ou culturelle et de nouveaux traitements des objets graphiques de synthèse. C’est l’ensemble de ces activités d’analyse et de traitement d’images planes que nous appelons « taxiplanie ».

2Nos travaux et séminaires ont couvert deux modes d’investigation :

• La recherche de concepts et de propriétés de théorie des graphes efficaces pour la maîtrise des graphes topologiques. En particulier, une nouvelle notion, dite dimension universelle d’un réseau, définie en compatibilité avec l’homomorphisme de graphe (avec Patrice Ossona de Mendez), a été l’objet d’une invitation au Newton Institute (Cambridge, 4-7 août 2003). Diverses généralisations sur les plongements des graphes dans les surfaces ont été également développées (avec Antonio Machi, « La Sapienza », Rome, oct-nov 2003).
• La représentation de réseaux culturels, économiques, technologiques, ainsi que de réseaux produits par l’analyse de données métriques dans l’espace à Ν dimensions. De nouveaux algorithmes ont été intégrés dans le logiciel PIGALE (avec Hubert de Fraysseix et Patrice Ossona de Mendez), logiciel libre, c’est-à-dire mis à la disposition de tous sous sa forme source et utilisé par une centaine de correspondants du réseau « Graph Drawing ». Le logiciel de tissage fil à fil et de simulation de tissus en couleur, PENELOPE (avec Hubert de Fraysseix) a été réécrit pour s’affranchir de toute carte graphique particulière. Il est exploité par l’Université de Pékin (Ailin Ru).

Publications

• Avec M. Deza, dir., European journal of combinatorics, 24, 2003, 1097 p.
• Ibid., 25, 2004, 1134 p.
• Avec P. Ossona de Mendez, « Transitivity and connectivity of permutations », Combinatorica, 24(3), 2004, p. 487-502.