Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Rook-drawing de graphes planaires
du 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