Abstract FR:

Nous étudions les N-séparateurs dans les graphes planaires pondérés (un N-séparateur d'un graphe connecté G est un sous-graphe S dont la suppression décompose G en N composantes connexes). Un grand nombre de travaux a été inspiré par l'article fondateur de Lipton et Tarjan sur les 2-séparateurs dans les graphes planaires pondérés. La construction de leur séparateur est un outil majeur dans de nombreux cas d'application de la théorie des graphes tels que VLSI modélisation, réseaux de communication, calcul parallèle. La plupart des publications considère les séparateurs qui divisent le graphe en deux parties, pourtant la division des graphes en un nombre de parties plus grand est nécessaire dans beaucoup d'applications. Notons que l'application récursive du 2-séparateur de Lipton-Tarjan donne une séparation qui est loin d'être optimale. Si cet algorithme est utilisé afin d'obtenir un 4-séparateur, dans ce cas, la plus petite des composantes sera d'au moins 1/9 de la taille du graphe quand l'application de notre méthode nous permet de dire que la plus petite des composantes va être d'au moins 1/7 de la taille du graphe. On optimise la construction du séparateur dans le cas des graphes planaires pondérés. Cette généralisation est importante pour les applications pratiques. Nous étudions les conditions d'existence d'un N-séparateur dans un graphe planaire et obtenons la limite optimale de la taille de la plus petite composante. Nous proposons la solution exacte au problème de degré-diamètre pour les graphes planaires dans le cas de diamètre pair 2d et de degré Delta > 6(12d + 1). De nouveaux exemples de graphes améliorant la borne inférieure sont construits pour Delta >=5.