Chers amis

Le prochain gt combinatoire du lix aura lieu ce lundi 4 juin mars à 11h dans la salle de séminaire du laboratoire: nous aurons le plaisir d'écouter Eric Fusy qui parlera de dessin de graphes.

Désolé pour l'annonce un peu tardive...
Amicalement,
Gilles Schaeffer

titre: *Dessin périodique de triangulations sur le cylindre et sur le tore*

resume: Nous étendons l'algorithme incrémental de dessin de De Fraysseix, Pollack et Pach (initialement pour triangulations planaires) au cas des triangulations cylindriques. La grille du dessin obtenu (grille x-périodique) est de la forme Z/wZ \times [0..h] avec w\leq 2n et h \leq n(2d+1), n étant le nombre de sommets et de la distance (distance de graphe) entre les deux bords. Dans un second temps, et par une réduction simple au cas du cylindre (utilisant la notion de tambourin) nous montrons comment dessiner toute triangulation torique sur une grille (x-périodique et y-périodique) de la forme Z/wZ\times Z/hZ avec w\leq 2n et h\leq n(2c-1)+1, n étant le nombre de sommets et c la longueur d'un plus court cycle non contractible. Comme c\leq (2n)^{1/2}, l'aire de la grille obtenue est O(n^{5/2}). Travail en commun avec Luca Castelli Aleardi et Olivier Devillers