Longueur linéaire des graphes planaires extérieurs

International audienceUne décomposition linéaire (path-decomposition) d'un graphe G = (V, E) est une représentation de G comme une séquence de sous-ensembles (appelés sacs) de V vérifiant des propriétés de connexité. La longueur d'une décomposition linéaire est le plus grand diamètre d'un de ses sacs et la longueur linéaire de G est la plus petite longueur d'une de ses décompositions linéaires. Ce paramètre a été étudié pour ses applications algorithmiques dans des problèmes métriques classiques (e.g., plus court chemin d'excentricité minimum, plongement de graphes dans des espaces métriques avec faible distorsion des distances...). Il est connu que décider si la longueur linéaire d'un graphe quelconque est au plus 2 est NP-complet, et le meilleur algorithme d'approximation connu a un rapport d'approximation de 2 (il n'existe pas de c-approximation pour c < 3/2). Dans cet article, nous étudions ce problème dans des sous-classes des graphes planaires. Nous prouvons que la longueur linéaire d'un cycle de n sommets est n/2 et que celle des arbres peut être déterminée en temps linéaire. Notre résultat principal est un algorithme polynomial donnant une +1-approximation de la longueur linéaire des graphes planaires extérieurs 2-connexes. Cet algorithme repose sur le fait que, dans cette classe de graphes, nous prouvons qu'il existe des décompositions (presque) optimales (de longueur minimum à un près) avec des propriétés structurelles spécifiques