| Résumé | Savoir comment transmettre une information est fondamental
dans un réseau. Il est essentiel que chaque entité du réseau soit
capable de décider localement, avec sa vue du réseau, du chemin par
lequel l'information doit passer. Ainsi, il est souvent utile
d'étudier la topologie du réseau, modélisée par un graphe, pour
répondre à ces exigences.
Nous nous intéressons dans un premier temps, à la décomposition
arborescente des graphes planaires. En effet, comme dans beaucoup
de problèmes de graphes, l'étude de la topologie des graphes nous
conduit à procéder à une décomposition du graphe afin d'exploiter
les propriétés structurelles qui en découlent.
En suite, nous nous sommes aussi intéressés à la structure des graphes qui
excluent un mineur $H$, en particulier le graphe $K_{2,r}$. Ces
travaux nous ont permis d'améliorer les bornes actuelles connues sur
la largeur arborescente de ces graphes.
Dans la dernière partie, nous abordons le problème du routage
compact. Nous nous sommes intéressés aux schémas de routage de
plus courts chemins utilisant des adresses, des tables
de routage de tailles optimales de $O(log n)$ bits, où $n$ est
le nombre de sommets du graphe. Nous proposons un tel schéma de
routage pour une famille de graphes valués contenant les arbres
et les graphes planaire-extérieurs. |