Evènement pour le groupe GT Graphes et Applications


Date 2015-01-16  14:00-15:00
TitreRook-drawing de graphes planaires 
RésuméLes graphes planaires peuvent être représentés de différentes façons : sur une grille (régulière ou non), avec des arêtes droites ou brisées, par contact de formes, sous forme de graphes de visibilité... Fáry a montré que tout graphe planaire possède une représentation plane dans laquelle les arêtes sont des segments de droite. Schnyder a ensuite amélioré ce résultat en prouvant qu'un graphe planaire de taille n peut être dessiné sur une grille de taille (n-2) x (n-2). Nous présentons un nouveau type de dessin de graphes que nous appelons le "rook-drawing". Étant donné un graphe planaire de taille n, un rook-drawing est une représentation plane de ce graphe dont les sommets sont placés sur une grille régulière n x n, où chaque ligne et chaque colonne porte exactement un sommet, et dont les arêtes sont des segments de droite. Nous présentons tout d'abord un algorithme linéaire permettant de dessiner les graphes planaires extérieurs en rook-drawing. Malheureusement, tous les graphes planaires ne peuvent pas être dessinés en rook-drawing. Nous proposons donc un algorithme linéaire, basé sur la théorie des réaliseurs de Schnyder, qui permet de dessiner tout graphe planaire par rook-drawing en autorisant quelques arêtes brisées. Le dessin final comporte au plus n-2 arêtes brisées.  
LieuSalle 178 
OrateurClaire Pennarun 



Aucun document lié à cet événement.

Retour
Retour à l'index