Ionona Ranaivoson (GREYC, Caen)

La notion de cycle est essentielle dans les graphes. C’est aussi la principale cause de complexité des problèmes de graphes. C’est pourquoi il est important d’étudier la structure de l’espace des cycles d’un graphe (espace dont la taille peut être exponentielle par rapport à celle du graphe). Nous présentons une méthode, en trois étapes, pour déterminer la structure de l’espace des cycles:

  1. Choisir un ensemble de cycles « pertinents » (ex. l’ensemble des faces d’un graphe plongé dans un plan, l’ensemble des éléments d’une base minimum de cycles de l’espace des cycles etc.)
  2. Etudier les relations entre ces cycles “pertinents”, par exemple à l’aide de graphes d’adjacence entre ces cycles « pertinents », que nous appelons graphes globaux.
  3. Dégager des propriétés du graphe original à partir des graphes globaux (ex. reconnaître une classe de graphe, étudier la similarité ou l’isomorphisme de deux graphes à partir de graphes globaux).

Les choix des cycles “pertinents” et de la relation d’adjacence entre ces cycles déterminent la « complexité descriptive et de calcul » de ces graphes globaux. Les cycles d’un graphe sont contenus dans ses composantes biconvexes. Nous définissons et prouvons l’existence de ce que nous appelons une couverture par trous (un trou est un cycle sans corde) pour tout graphe biconvexe. Nous choisissons ces trous comme sommets des graphes globaux parce qu’ils sont faciles à comprendre et à calculer. Nous étudions deux relations d’adjacence entre ces trous. La première, la plus naturelle, où deux trous sont adjacents ssi ils ont au moins une arête en commun, permet de retrouver des résultats déjà prouvés sur les graphes planaires extérieurs (outerplanar graph) mais s’avère vite être inexploitable. La deuxième conserve les propriétés de la première et est plus «expressive». Nous nous en servons pour donner une caractérisation de la classe des graphes série-parallèles et, de la même manière, de ses sous-classes majeures. Nous utilisons aussi cette caractérisation et l’algorithme de calcul des trous pour reconnaître non seulement en temps linéaire mais aussi en espace linéaire (ce qui n’est pas le cas des algorithmes classiques connus à ce propos) les graphes série- parallèles.