Mémoire de M2

Arnaud De Mesmay

Description

• rapport de stage
• rapport de stage - matière potentielle : mpri
• exposé

Déformation de graphes sur les surfaces Arnaud de Mesmay Sous la direction d'Éric Colin de Verdière Laboratoire d'Informatique de l'École Normale Supérieure Août 2011 Le contexte général Mon stage s'inscrit dans le domaine de la topologie algorithmique. Cette discipline encore très jeune vise à formaliser et à résoudre des versions algorithmiques de problèmes issus de la topologie algébrique, ou réciproquement à apporter des outils topologiques pour résoudre des problèmes d'origine informatique, nous renvoyons à [11] pour une présentation détaillée.

• descriptions combinatoires
• homéomorphisme
• recherche algorithmique dans la direction de la classification des homéomorphismes
• isotopie
• graphes
• graphe
• courbes
• courbe
• complexité
• surfaces
• surface
• théorie
• théories

Sujets

• Exposé
• Mapping class group
• Teichmüller
• Robertsport
• Surface
• Courbe
• Graphe
• Algorithmique
• Homéomorphisme
• Complexité

Informations

• Publié par: foeh
• Nombre de lectures: 128
• Langue: Français

Extrait

Déformation de graphes sur les surfaces
Arnaud de Mesmay
Sous la direction d’Éric Colin de Verdière
Laboratoire d’Informatique de l’École Normale Supérieure
Août 2011
Le contexte général
Mon stage s’inscrit dans le domaine de la topologie algorithmique. Cette discipline encore
très jeune vise à formaliser et à résoudre des versions algorithmiques de problèmes issus de la
topologie algébrique, ou réciproquement à apporter des outils topologiques pour résoudre des
problèmes d’origine informatique, nous renvoyons à [11] pour une présentation détaillée.
Le sujet de ce rapport est l’étude des courbes et des graphes sur les surfaces. Durant les
dix dernières années, des avancées significatives ont été faites, et des algorithmes efficaces ont
été développés pour résoudre des problèmes naturels. Par exemple, on sait calculer des courbes
constituant une décomposition topologique de la surface [23,29], décider si deux courbes qui
y sont plongées sont homotopes [10] ou bien raccourcir autant que possible une courbe en la
déformant continûment sur une surface [6].
Ces problèmes sont également reliés à de nombreuses branches des mathématiques et de
l’informatique. Ainsi par exemple, les communautés de géométrie algorithmique s’intéressent
de près aux propriétés topologiques des objets géométriques qu’elles manipulent, l’étude des
graphes plongés sur les surfaces fournit un angle d’attaque différent pour attaquer les problèmes
1combinatoiresdethéoriedesgraphes ,etnaturellementl’étudedestriangulationssurlessurfaces
est essentielle dans les problèmes liés à l’infographie.
Le problème étudié
Durant ce stage, je me suis essentiellement intéressé au problème suivant :
Isotopie de graphes
Entrée : Un graphe G plongé de deux façons différentes sur une surface S.
Question:Lesplongementsdugraphesont-ilsisotopes,i.e.ya-t-ilunedéformationcontinue
de la surface permettant d’aller de l’un vers l’autre?
Deux instances simples de ce problème peuvent servir d’exemples pour l’introduire. La pre-
mière est le cas d’un graphe dessiné de deux façons dans le plan parsemé de nombreux obstacles.
On se demande alors si l’on peut passer d’un graphe à l’autre de façon continue sans traverser
les obstacles. On verra dans ce rapport que même dans ce cas, le problème n’est pas trivial, voir
figure 5.
Un deuxième cas d’application est celui d’une surface triangulée avec un graphe plongé de
deux manières différentes sur cette triangulation. Il ne s’agit alors plus d’éviter ses obstacles
planaires mais plutôt des obstacles topologiques (trous, poignées).
Étonnamment, ce rapport propose à notre connaissance le premier algorithme pour résoudre
le problème, ce qui peut s’expliquer par la jeunesse relative du domaine. De plus, il est lié à
1. Ils interviennent par exemple de façon essentielle dans la preuve du théorème de Robertson-Seymour.
12
la théorie des mapping class groups (cf. infra), sujet possédant une certaine profondeur ma-
thématique, qui n’a presque pas été exploré du point de vue algorithmique. C’est pourtant un
problème naturel qui se place bien dans le contexte plus général de l’étude des graphes sur les
surfaces (voir par exemple [25] pour une introduction au sujet) : tester si deux graphes sont
isotopes permet de tester si deux graphes plongés sont les « mêmes », dans un sens largement
plus fort que le simple isomorphisme combinatoire. L’aspect mathématique du sujet a été en
partie traité par Ladegaillerie [20–22], qui propose dans une série d’articles une caractérisation
topologique et combinatoire de la question, permettant de ramener le test d’isotopie de graphes
au test d’homotopie d’un certain nombre de courbes bien choisies.
La contribution proposée
L’algorithmequenousproposonsdanscerapportreposesurl’observationque,commel’apré-
cédemment montré Ladegaillerie [20], deux conditions naturelles pour que les deux plongements
d’un même graphe sur une surface soient isotopes sont en fait suffisantes. Ceci nous permet,
en utilisant de plus la décomposition en octogones introduite par [7], de fournir un algorithme
efficace pour résoudre le problème posé, en utilisant comme boîte noire un algorithme dû à Dey
et Guha pour tester l’homotopie de deux courbes [10].
La démarche scientifique employée s’articule en plusieurs étapes. D’une part, nous avons
procédé à une lecture critique de l’article de Ladegaillerie [20], que nous avons mise en relief
avec les progrès sur les connaissances et la présentation de la théorie des mapping class groups,
par exemple exposée dans [14]. Ceci nous a permis de simplifier et de moderniser la preuve du
théorème principal, c’est le premier apport de ce travail. Le deuxième a été ensuite de propo-
ser une construction algorithmique des courbes à tester et enfin de s’intéresser aux possibles
améliorations et ouvertures apportées par cette démarche.
Les arguments en faveur de sa validité
Nous présentons dans ce rapport un algorithme qui résout le problème avec une complexité
linéaire donc optimale en genre fixé, et quadratique sinon. La dépendance au genre est courante
et tolérée dans ce genre de problèmes, voir par exemple [4]. Néanmoins, nous ne disposons pas de
borne inférieure prouvant que cette dépendance au genre est nécessaire. La technique employée
pour justifier la correction et la complexité de l’algorithme est assez robuste, nous montrons
ainsi en section 6.1 comment généraliser celui-ci à un problème plus large que celui considéré.
Enfin, l’algorithme est implantable en pratique : Il ne requiert aucune structure de données de
grande complexité et les constantes intervenant dans la notation O() sont très raisonnables.
Le bilan et les perspectives
L’approcheutiliséedanscerapportnoussembleêtreassezgénérale:d’unepartnouslerelions
à des problèmes mathématiques bien compris (la classification des éléments du mapping class
group), d’autre part nous apportons des outils algorithmiques pour s’atteler à ces problèmes.
Plusieurs ouvertures sur le sujet sont possibles, nous en discuterons plus en profondeur en
conclusion. L’algorithme présenté dans ce rapport a une complexité presque optimale : seule la
dépendance en le genre de la surface induit un facteur non linéaire, une amélioration naturelle de
l’algorithme serait de le faire disparaître. Dans le cas des graphes planaires, on peut se demander
si les mêmes techniques peuvent nous permettre d’obtenir des isotopies rectilignes. Ce problème
est brièvement discuté en section 6.2. On peut également se demander comment traiter le cas
non orientable. La question semble particulièrement épineuse, puisqu’elle est reliée à la théorie
des mapping class groups des surfaces non orientables, qui est extrêmement délicate.
A. de Mesmay 2 Rapport de stage MPRI1. Définitions 3
Organisation du rapport
Ce rapport s’organise de la façon suivante. Dans la première partie, nous introduisons les
définitions et les concepts nécessaires. La seconde partie est une présentation générale de l’algo-
rithme, dont les détails et la preuve de correction sont réparties sur les deux parties suivantes.
L’algorithme final est présenté dans la cinquième partie, la sixième discute les généralisations
possibles et les ouvertures liées à ce travail et la septième conclut.
1 Définitions
1.1 Topologie et courbes sur les surfaces
Commençons par définir précisément les notions utilisées dans la suite de ce rapport. De
bonnes références pour approfondir les concepts de topologie algébrique sont [26] et [16].
Une surface S ou 2-variété à bord est un espace topologique séparé tel que le voisinage
de chaque point soit homéomorphe à un plan ou un demi-plan. L’ensemble des points homéo-
morphes au demi-plan constitue le bord de la surface. Une surface est orientable si et seulement
si elle ne contient pas de ruban de Möbius. Dans tout ce qui suit, les surfaces que l’on consi-
dère sont compactes et orientables, sauf si spécifié autrement. La classification des surfaces à
homéomorphisme près, souvent attribuée à Möbius, fait l’objet du théorème suivant :
[1.A] Théorème (Classification des surfaces orientables)
Toute surface compacte orientable est caractérisée à homéomorphisme près par
deux entiers positifs g (le genre) et b (le nombre de bords). U