Internships (équipe Combinatoire, LIX, Ecole Polytechnique)

Internships 2024-25 ("stages de recherche")


Past internship students (M1/M2)


Jyh-Chwen KO, (2024, MPRI): Schnyder Woods for Higher Genus Surfaces with Applications to Graph Drawing
(to appear in the Proc. of 41th Int. Symposium on Computational Geometry (SocG 2025).
Joao Goncalves (2020): Compression adaptative de grands graphes

Gabriel Beauplet (2019, MPRI): Tétraèdres en Diamants : Structure de Données Compacte pour Maillages Tétraèdriques

Gaspard Denis (2017): Fast spherical drawing of planar triangulations
(published in the Proc. of 17th Int. Symposium on Experimental Algorithms (SEA 2018), LIPIcs, vol. 103, p. 24:1-24:14, 2018, link).
Martin Jocqueviel (2016): Plongement d'un graphe triangulaire sur le tore (co-advisor: Maks Ovsjanikov)

Kevin Bienvenu (2015): Using a spectral multi-scaled aging method to visualize and analyze dynamic networks (co-advisor: Maks Ovsjanikov)

David Uribe (2015): Drawing triangulations with a prescribed inner face in linear time and polynomial resolution.

Alexandre Nolin (2014): Efficient and practical tree preconditioning for solving Laplacian systems (co-advisor: Maks Ovsjanikov).
(published in the Proc. of 14th Int. Symposium on Experimental Algorithms (SEA 2015), Springer LNCS, vol. 9125, p. 219-231, 2015, link).
Anatolii Kostrygin (2013): Periodic planar straight-frame drawings with polynomial resolution (co-advisor: Eric Fusy).
(published in the Proc. of 11th Latin American Theoretical INformatics Symposium (LATIN 2014), Springer LNCS, vol. 8392, p. 168-179, 2014, link).

1) Forêts de Schnyder pour des graphes en genre supérieur, avec applications au dessin (sujet détaillé)

L’objet de ce stage sera l’étude combinatoire et algorithmique d’une cer- taine classe de propriétés caractérisant la notion de planarité des graphes: ces propriétés (connues sous le nom de forêts de Schnyder ) ont eu dans les trois dernières décennies des fortes répercussions et ont conduit à de nombreuses applications dans plusieurs do- maines, notamment le dessin et le codage de graphes. Dans ce stage il s’agira d’étudier les généralisations de ces propriétés et leurs applications au cas de graphes plongés sur des surfaces: en particulier on s’intéressera au problème de dessiner un graphe de genre g sur une grille planaire avec resolution polynomiale (ce problème est ouvert pour g ≥ 2). Un problème crucial sera celui de fournir une définition satisfaisante, permettant de bien décrire et caractériser la structure des graphes plongés sur des surfaces: cela nous con- duira ainsi à explorer des questions très profondes et intéressantes faisant intervenir des propriétés topologiques, combinatoires et algorithmiques de ces objets.

Lieu du stage:LIX (Ecole Polytechnique)

Responsable:
Luca Castelli Aleardi (LIX, Ecole Polytechnique)