Structure vs métrique dans les graphes

International audienceL'émergence de réseaux de très grande taille oblige à repenser de nombreux problèmes sur les graphes : en apparence simples, mais pour lesquels les algorithmes de résolution connus ne passent plus a l'échelle. Une approche possible est de mieux comprendre les propriétés de ces réseaux complexes, et d'en déduire de nouvelles méthodes plus efficaces. C'est dans ce but que nous démontrons des relations générales entre les propriétés structurelles des graphes et leurs propriétés métriques. Nos relations se déduisent de nouvelles bornes serrées sur le diamètre des séparateurs minimaux dans un graphe. Plus précisément , nous prouvons que dans tout graphe G le diamètre d'un séparateur minimal S dans G est au plus (l(G)/2) · (|S| − 1), avec l(G) la plus grande taille d'un cycle isométrique dans G. Nos preuves reposent sur des propriétés de connexité dans les puissances d'un graphe. Une conséquence de nos résultats est que pour tout graphe G, sa longueur arborescente (treelength) est au plus l(G)/2 fois sa largeur arborescente (treewidth). En complément de cette relation, nous bornons la largeur arborescente par une fonction de la longueur arborescente et du genre du graphe. Cette borne se généralise à la famille des graphes qui excluent un apex-graph H comme mineur. Par conséquent , nous obtenons un algorithme très simple qui, étant donné un graphe excluant un apex-graph fixé comme mineur, calcule sa largeur arborescente en temps O(n²) et avec facteur d'approximation O(l(G))