Les graphiques du «genre délimité par l'extérieur» ont-ils une largeur d'arbre constante?

Soit et notons G k l'ensemble de tous les graphes qui peuvent être incrustés sur une surface du genre k de telle sorte que tous les sommets soient situés sur la face externe . Par exemple, G 0 est l'ensemble des graphes planaires externes. La largeur d'arbre des graphes dans G k peut-elle être supérieure par une fonction de k ?$k\in\mathbb{N}$$G_k$$k$$G_0$$G_k$$k$

L'autre sens ne tient évidemment pas, car une largeur d'arbre constante n'implique même pas un genre constant: Soit l'union de n copies disjointes de K 3 , 3 . La largeur d'arbre de H n est constante, son genre est cependant n .$H_n$$n$$K_{3,3}$$H_n$$n$

Oui.

Ajoutez un sommet au milieu de la face externe, connecté à tous les sommets de la face externe; cela ne change pas le genre et ne diminue pas la largeur de l'arborescence. Maintenant, le graphique a un arbre de recherche très peu profond en premier enraciné au nouveau sommet (tout est adjacent à lui).

Former un arbre couvrant le graphe double dont les bords doubles sont disjoints des bords du premier arbre de recherche étendu. Ensuite, il y a un ensemble d'arêtes O (genre) qui n'appartiennent à aucun des deux arbres. Chacune de ces arêtes induit un cycle court (un triangle) avec un chemin dans le premier arbre de recherche de largeur, et la coupe de la surface le long de ces cycles produit une surface plane (voir mon article "Générateurs dynamiques de graphiques topologiquement intégrés"). Autrement dit, si G 'est le sous-graphique du graphe d'entrée induit par les sommets qui ne sont pas des extrémités des arêtes coupées O (genre), alors G' est planaire, et ses sommets peuvent être couverts par les faces O (genre) de son encastrement plan (les faces dans lesquelles les cycles de découpe coupent la face externe d'origine).

Mais dans un graphe planaire dans lequel tous les sommets appartiennent à k faces, on peut supprimer les autres arêtes O (k) (un arbre couvrant des faces) pour obtenir un graphe planaire externe. La largeur d'arbre de G 'est donc O (genre). Si l'on forme une décomposition arborescente de G 'avec cette largeur, puis ajoute à chaque sac les sommets qui sont les extrémités des bords du cycle de coupe, le résultat est une décomposition arborescente du graphe d'entrée d'origine avec la largeur d'arbre O (genre).

Il semble probable que cela doit déjà être quelque part dans la littérature, mais je ne sais pas où et certaines recherches rapides n'ont pas réussi à trouver une déclaration explicite de ce résultat précis. Cependant, une déclaration plus générale se trouve dans un autre article: dans "Diamètre et largeur d'arbre dans les familles de graphes fermés mineurs", je prouve entre autres que les graphes de genre bornés de diamètre borné ont une largeur d'arbre bornée. Dans ce cas (en ajoutant ce sommet supplémentaire à l'intérieur de la face externe), le diamètre peut être considéré comme étant au maximum deux.