Proposition de Stages

Responsables:

Hubert de Fraysseix

&

Patrice Ossona de Mendez

L'équipe Taxiplanie du CAMS - CNRS UMR 8557 propose, pour la période d'été 2006, au sein du laboratoire situé 54 Boulevard Raspail - 75006 Paris, deux stages comprenant:

• une partie d'étude bibliographique
• une partie de recherche théorique
• une partie de programmation au sein de l'environnement Pigale (C++/Qt^©)

Tracé orthogonal

Présentation: Dans un tracé orthogonal, les arêtes joignant les sommets sont représentées par des lignes brisées consituées de segments parallèles aux axes. Les problèmes classiques d'optimisations des tracés orthoganaux portent sur la minimisation du nombre de coudes et/ou sur la minimisation de la surface globale utilisée. References: A Linear Algorithm for Bend-Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs Md. Saidur Rahman, Shin-ichi Nakano and Takao Nishizeki Vol. 3, no. 4, pp. 31-62, 1999. Orthogonal Drawings of Plane Graphs Without Bends Md. Saidur Rahman, Takao Nishizeki and Mahmuda Naznin Vol. 7, no. 4, pp. 335-362, 2003.

Tracé orthogonal d'un graphe planaire 3-régulier.

Augmentations de graphes planaires

Présentation: Les orientations régulières, i.e. les orientations telles que presque tous les sommets aient le même degré entrant, relient de nombreuses propriétés combinatoires et topologiques, telles que l'arboricité, le page number et la planarité. Ces orientations constituent un outil de base dans la résolution de problèmes combinatoires dans lesquels des propriétés topologiques doivent être conservées. L'augmentation de graphes planaires est un exemple simple de tels problèmes. Références: H. de Fraysseix and P. Ossona de Mendez. Regular Orientations, Arboricity and Augmentation. In DIMACS International Workshop, Graph Drawing 94, volume 894 of Lecture notes in Computer Science, pages 111-118, 1995. T. Matsumoto. Orientations contraintes. PhD thesis, Ecole des Hautes Etudes en Sciences Sociales, Paris, 1997.

Augmentation d'un graphe planaire 3-connexe par ajout d'au plus 6 arêtes en chaque sommet.