Étude des triangulations sur les surfaces à $g\ge 2$ trous


Les Schnyder wood sont une structure définis pour les triangulations planaires. Elle a été introduite en 1989 par W. Schnyder pour donner une nouvelle caractérisation des graphes planaires via la théorie des ordres [Sch89]. Cette structure a ensuite eu beaucoup de succès puisque elle a permis la conception d'algorithmes pour le dessin compact de graphes [Sch90], de nouvelles représentations de graphes via intersections d'objets géométriques [FOR94], ainsi que la mise en lumière de bijections entre triangulations et arbres bourgeonnants [PS06]. Cette dernière permettant le codage compact et la génération aléatoire des triangulations planaires.


Depuis quelques années, différentes équipes de recherches cherchent à étendre à d'autres types de triangulations, les Schnyder wood et leurs applications. Le premier résultat dans cette direction a permis la conception de codages compactes des triangulations des surfaces orientables sans bord [CFL09]. Ensuite, 2 algorithmes de dessins compactes des triangulations toriques ont été conçus [CDF13,GL14]. Et enfin récemment nous avons mis en lumière une bijection entre les triangulations toriques et les arbres toriques bourgeonnants [DGL15], ouvrant la voie à la conception d'algorithmes de génération aléatoires pour ces triangulations.


L'objectif de cette thèse serait de poursuivre ces travaux dans les directions suivantes :


  • Généraliser les travaux de [DGL15] en exhibant une bijection entre les triangulations d'une surface $S_g$ et les arbres bourgeonnants de $S_g$. Une façon de faire serait de modifier la preuve de [AGK15] afin d'y interdire certains types de coupes.


  • Voir au delà du cas des triangulations. Dans le cas planaire, des travaux similaires ont été menés sur les graphes planaires 3-connexes [Fel01], ou sur les graphes planaires dont les faces ont une taille $k$ donnée [BF12]. Les généralisations de ces classes au cas torique forment des objets d'étude prometteurs.


  • Enfin, un autre objectif pourrait être la conception d'algorithmes de dessin de graphes sur les surfaces à $g\ge 2$ trous. Ces dessins devront vérifier certains critères de lisibilité tel que borner le ratio entre l'arête la plus courte et la plus longue (contrairement aux méthodes existantes).



Biblio


[AGK15] B. Albar, D. Gonçalves, K. Knauer, Orienting triangulations, J. of Graph Theory, to appear.


[BF12] O. Bernardi, É. Fusy, A bijection for triangulations, quadrangulations, pentagulations, etc, Journal of Combinatorial Theory, Series A 119 (2012) 218-244.


[CFL09] L. Castelli Aleardi , É. Fusy, and T. Lewiner. Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to Encoding, Discrete & Computational Geometry, 42 (2009), 489-516.


[CDF13] L. Castelli Aleardi, O. Devillers, É. Fusy, Canonical ordering for triangulations on the cylinder, with applications to periodic straight-line drawings, Proceedings of Graph Drawing, (2013).


[DGL15] V. Despré, D. Gonçalves, B. Lévêque, Encoding toroidal triangulations, ArXiv:1507.05461.


[Fel01] S. Felsner, Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes, Order 18 (2001) 19-37.


[FOR94] H. de Fraysseix, P. Ossona de Mendez, P. Rosenstiehl, On Triangle Contact Graphs, Combinatorics, Probability and Computing 3 (1994) 233-246.


[GL14] D. Gonçalves, B. Levêque, Toroidal maps : Schnyder woods, orthogonal surfaces and straight-line representations, Discrete and Computational Geometry 51 (2014) 67-131.


[Sch89] W. Schnyder, Planar graphs and poset dimension, Order 5 (1989) 323-343.


[Sch90] W. Schnyder, Embedding planar graphs on the grid, in Proceedings of SODA (1990), 138-148.


[PS06] D. Poulalhon, G. Schaeffer, Optimal coding and sampling of triangulations, Algorithmica 46 (2006) 505-527.