Pierre Rosenstiehl, directeur d’études

Combinatoire et graphes. Taxiplanie

1On s’intéresse non seulement à maîtriser théoriquement 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’origine naturelle ou culturelle et de nouveaux traitements des objets graphiques de synthèse. C’est l’ensemble de ces activités de représentation et de traitement d’images planes que nous appelons « taxiplanie ».

2Nos travaux 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 : une notion nouvelle dite dimension universelle d’un réseau, définie en compatibilité avec l’homomorphisme de graphe (avec Patrice Ossona de Mendez). Le codage des cartes topologiques par un mot à doubles occurrences. Enfin, un exposé sur les arbres par l’auteur de « The art of computer programming » Donald Knuth, de l’Université Stanford, invité de l’École.
• 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) s’est enrichi une fois affranchi de toute carte graphique particulière. Il est exploité par l’Université de Pékin (Ailin Ru).

Publications

• Avec M. Deza, European journal of combinatorics, Elsevier, 25, 2004, 1376 p.
• Ibid., 26, 2005, 1230 p.