Visualisation et Algorithmes de Graphes
Séminaire/Groupe de Travail

Maurice Pouzet (Université Claude Bernard Lyon1)
" Profil des graphes et des relations, un survol. "

Résumé de l'exposé

Binh-Minh Bui-Xuan
" Vous avez apprécié les modules, vous aimerez les u-modules. "
(travail effectué avec MM. Habib, Limouzy et de Montgolfier)

Nous sommes parti de l'étude des familles de modules de graphes (non-orientés). Un module M est un ensemble de sommets tel que pour tout triplet de sommets x et y appartenant à M et z n'appartenant pas à M, l'adjacence entre z et x est la même que celle entre z et y.
Nous avons proposé un point de vue basé sur la dualité différenciation v.s. homogénéité, permettant d'étudier la structure de ces familles tout en s'abstrayant de toute notion d'adjacence, et par conséquent, de celle de graphe. Ce faisant, nous avons pu, en un premier temps, généraliser la notion de départ à un contexte bien plus général. Puis, nous avons pu dégager deux propriétés essentielles que les modules de graphes vérifient, alors qu'il n'est pas forcément le cas dans le contexte général. La première propriété, étroitement liée aux définitions populaires de la notion de "module", a hérité du même nom. La seconde a été appellée la propriété du "umodule".
Sans surprise, les familles correspodantes, dites de umodules, ne semblent pas avoir de structure dans les cas les plus généraux. Ceci étant, lors que ces familles vérifient certaines conditions de régularité, toutes assez simples à énoncer, des structures de décomposition (en arbre) se dégagent.
A la réunion du 14 Juin, je présenterai les notions en question, les axiomes de décomposition, ainsi que les propriétés struturelles qui en découlent. La présentation sera accompagnée des exemples sur différents niveaux (cas général, cas des graphes, etc), afin que nous puissions en discuter/faire des critiques.

Jan van den Heuvel
" Hirsch conjecture and the transportation polytope "

Florian Huc
" 4-cycles orientés dans les mixed-digraphs "

It is well known that ex(n;C3) = (n2)/4 (maximal number of arcs in a graph on n vertices without cycle of length 3), and the extremal graph is the complete bipartite graph. For excluded 4-cycle graphs, the exact value of ex(n;C_4) is known for all values of n of the form n = q2 + q + 1, where q is a power of 2, or a prime power exceeding 13. In this talk we recall how to drive an easy bound of type O(n^(3/2)) and the aim is to study in some sense analogue questions for directed case. Since acyclic digraphs can have a lot of arcs, conditioning only on the number of arcs can not garanty anything about the existence of directed cycles. On the other hand, if a graph has a lot of k-cycles, taking a random orientation should provide a directed k-cycle. This leads us to define a new notion of pseudo-randomness for oriented graphs. Oriented graphs having this pseudo-randomness property are what we call mixed digraphs. For this family of digraphs, we prove that a simple condition on the number of arcs can garanty the existence of 4-cycles.

Nancy Rodriguez
" Les graphes dans les environnements virtuels "

Transparents de l'exposé

Stéphan Thomassé
" Une preuve alternative de la dualité Tree-width Bramble "

Emeric Gioan
" Partitions des arêtes d'un graphe ordonné associées aux orientations et aux arbres couvrants. "
(en collaboration avec Michel Las Vergnas)

Etant donné un ordre total sur l'ensemble des arêtes d'un graphe, de nombreuses structures et propriétés apparaissent liées numériquement au polynôme de Tutte. En particulier, à toute orientation on peut associer naturellement une partition de l'ensemble des arêtes, revenant à décomposer l'orientation en orientations bipolaires dans des mineurs. Ces partitions sont énumérées par les coefficients du polynôme de Tutte. Une construction similaire existe pour les arbres couvrants, compatible avec celle pour les orientations, permettant d'induire une correspondance entre arbres et orientations. Ces partitions se généralisent aux matroïdes orientés, et généralisent par ailleurs la notion de composantes d'orientations acycliques pour un ordre sur les sommets.

Daniel Gonçalves (LaBRI)
" Sur la représentation en courbes d'un graphe planaire. "
(travail effectué en collaboration avec J. Chalopin et P. Ochem et présenté à SODA '07)

Cet exposé portera sur la représentation des graphes planaires par des modèles d'intersections. Un graphe G=(V,E) est un graphe courbe (resp. un graphe segment) si les éléments de V sont des courbes (resp. des segments) dans le plan et si les éléments de E sont les paires de courbes qui s'intersectent. Les graphes segments forment donc un sous-ensembles des graphes courbes.
On sait que tout graphe planaire est isomorphe à un graphe courbe et Scheinerman a conjecturé en '84 que tout graphe planaire est isomorphe a un graphe segment. Dans la représentation en courbes classique d'un graphe planaire G, il est fréquent que les deux courbes correspondant à deux sommets adjacents de G se croisent deux fois. Or dans une représentation en segments, deux segments ne s'intersectent qu'une fois au plus.
On s'interesse donc aux graphes 1-courbes. Ces graphes sont les graphes courbes tels que l'intersection de deux courbes quelconques se fait en au plus un points. Notre contribution a été de montrer que tout graphe planaire est isomorphe à un graphe 1-courbe.

Les modules et la décomposition modulaire sont des éléments récurrents en théorie et algorithmique de graphes. Les modules interviennent dans beaucoup de démonstrations, et la décomposition modulaire sert de base à de nombreux d'algorithmes sur les graphes. Cette décomposition est unique, peut être calculée en temps linéaire, et se généralise à d'autres structures (graphes orientés, hypergraphes...). La décomposition bi-joint, introduite récemment, est une décomposition de graphes non orientés généralisant la décomposition modulaire.
Après quelques rappels sur la décomposition modulaire, on s'intéressera dans un premier temps à la décomposition bi-joint. On montra une forte relation entre cette décomposition et la décomposition modulaire. Cette relation nous donnera différentes caractérisations des graphes entièrement décomposables, et un algorithme linéaire de décomposition. On donnera également un théorème de décomposition des graphes sans gem et co-gem induits utilisant la décomposition bi-joint.
Dans la seconde partie, on présentera une famille de décompositions de 2-structures généralisant la décomposition modulaire. La décomposition bi-joint des graphes non orientés et des tournois en sont des cas particuliers. On verra que deux décompositions de cette famille généralisent les décompositions bi-joint (des graphes non orientés et des tournois) aux graphes orientés. Ces deux décompositions sont mutuellement exclusives, c'est à dire qu'il existe un graphe premier pour l'une et complètement décomposable pour l'autre, et vice versa. Enfin on verra que toutes ces décompositions peuvent être calculées en temps O(n3) (pour une décomposition fixée dans la famille).

Le critère ratio-cut et le critère de densité, traditionnellement utilisés comme critère d'optimisation pour le clustering de graphes peuvent tous deux être approché par une loi normale. On en conclut que "tout" critère proposant une combinaison de ces critères suit aussi une normale. Le résultat s'avère utile pour évaluer de manière "absolue" la performance d'un algorithme de clustering, en terme de "qualité" du résultat produit.

Binh Minh Bui Xuan
" Les relations d'homogénéité : structure algébrique pour l'étude des décompositions ? "
(travaux effectués en collaboration avec M. Habib, V. Limouzy, et F. de Montgolfier)

L'année 2006-2007 sera belle et porteuse de nouvelles choses ! Si si... Pour la fêter, je vous propose de nous intéresser à l'aspect suivant des... umm... modules de graphe, heu... (ok j'ai un peu honte je l'avoue). Soit A un ensemble de sommets, un sommet s extérieur à A casse A s'il existe deux sommets de A tels que s ne soit pas relié de la même façon à ces deux sommets (``splitter'' en anglais). Un module est un sous-ensemble de sommets sans casseur.
Si les tomates ne sont pas encore lancées, je vous présenterai deux visions équivalentes, distinction versus homogénéité, d'une généralisation commune des graphes, tournois, graphes orientés, et autres 2-structures. Il s'agit des relations trinaires, dits d'homogénéité, sur X: étant donnés un élément s et un couple d'éléments tous deux différents à s, s distingue-t-il le premier au second du couple ? Nous verrons comment ces relations représentent les quatre structures mentionnées (graphes, tournois, etc). Un théorème de caractérisation sera donné pour trancher quand une relation d'homogénéité peut être associable à un graphe, ou à un tournoi.
Soit maintenant A un sous ensemble de X. Nous avons étudié la question suivante. Si s est extérieur à A, existe-il couple d'éléments de A tel que s le distingue ? Si nul ne répond à la question, on dit que A vérifie la propriété du module, comme le cas des graphes. Naturellement, la théorie qui en découle contient les décompositions modulaires des structures mentionnées. Cependant elle ne s'arrête pas là. Par exemple, nous verrons que, dans le cas des graphes, notre terme ``module'' permet aussi d'inclure les sous ensembles de sommets semblables aux composantes 2-connexes, ceux semblables aux ``star cutsets'', et bien d'autres encore.
S'il nous reste du temps et si cela vous intéresse encore (!!! et comment ?), je vous parlerai des cas où un théorème de décomposition est donné, et des algorithmes de décomposition proposés. Sur ce point, les VIPs viendront des familles (faiblement) partitives.