Internships (équipe Combinatoire, LIX, Ecole Polytechnique)

Internships 2025-26 ("stages de recherche")


Past internship students (Bachelor/M1/M2)


Giselle FENG (2025, Bachelor thesis): Computation of Toroidal Schnyder woods starting from a Cylindrical Representation
to appear in the Proc. of the SIAM Symposium on Simplicity in Algorithms (SOSA 2026), Vancouver, Canada, January 12–13, 2026. [conference webpage]
Milana KOMISAROVA (2025, Bachelor thesis): Fast computations of connected toroidal Schnyder woods

Razvan Stefan PUSCASU, (2024, Bachelor thesis): Schynder Woods in the plane and on genus 1 surfaces
published in the Proc. of 41th Int. Symposium on Computational Geometry (SocG 2025), LIPIcs, vol. 332, 30:1--30:19, 2025. link
Laurentiu LAZAR (2024, Bachelor thesis): Adaptive analysis of mesh compression schemes

Jyh-Chwen KO (2024, MPRI): Schnyder Woods for Higher Genus Surfaces with Applications to Graph Drawing
pusblished in the Proc. of 41th Int. Symposium on Computational Geometry (SocG 2025), LIPIcs, vol. 332, 30:1--30:19, 2025. link
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)