Éric COLIN de VERDIÈRE

Chercheur CNRS dans l'équipe GéCoaL du Département d'Informatique de l'École normale supérieure (Paris). Sujets d'intérêt : algorithmes et combinatoire, géométrie et topologie (géométrie algorithmique, topologie algorithmique des surfaces, optimisation combinatoire, algorithmique des graphes). Mon CV.

École normale supérieure, Département d'Informatique 45, rue d'Ulm, 75005 Paris, France Tél. (+33).1.44.32.20.53 fax (+33).1.44.32.21.56 (me prévenir par mail) "Hauts du DI", Esc. A, 3ème étage E-mail: , clé GPG

Le site des Journées de Géométrie Algorithmique 2010, co-organisées avec Boris Thibert.

Recherche

• Testing graph isotopy on surfaces.
  Avec Arnaud de Mesmay.
  Soumis, 2011.

• Irreducible triangulations of surfaces with boundary.
  Avec Alexandre Boulch et Atsuhiro Nakamoto.
  Soumis à un journal, 2011. Version sur arXiv (pdf, bib).

• Helly numbers of acyclic families.
  Avec Grégory Ginot et Xavier Goaoc.
  Soumis, 2011. Version sur arXiv (pdf, bib).

• Finding cycles with topological properties in embedded graphs.
  Avec Sergio Cabello et Francis Lazarus.
  SIAM Journal on Discrete Mathematics, 2011, 25:1600–1614 (pdf, bib).

• Shortest cut graph of a surface with prescribed vertex set.
  Proc. European Symposium on Algorithms (ESA), 2010, vol. 2, p. 100–111 (pdf, bib).

• Algorithms for the edge-width of an embedded graph.
  Avec Sergio Cabello et Francis Lazarus.
  Computational Geometry: Theory and Applications, 2012, 45:215–224 (pdf, bib).
  Proc. ACM Symp. on Computational Geometry (SOCG), 2010.

• Finding shortest non-trivial cycles in directed graphs on surfaces.
  Avec Sergio Cabello et Francis Lazarus.
  Proc. ACM Symp. on Computational Geometry (SOCG), 2010, p. 156–165 (pdf, bib).

• Homotopic Fréchet distance between curves — or, walking your dog in the woods in polynomial time.
  Avec Erin W. Chambers, Jeff Erickson, Sylvain Lazard, Francis Lazarus et Shripad Thite.
  Computational Geometry: Theory and Applications, 2010, 43:295–311 (pdf, bib).
  Proc. ACM Symp. on Computational Geometry (SOCG), 2008.
  Proc. Fall Workshop on Computational Geometry (FWCG), 2007.

• Shortest vertex-disjoint two-face paths in planar graphs.
  Avec Alexander Schrijver.
  ACM Transactions on Algorithms, 2011, 7(2), art. 19 (pdf, bib).
  Proc. Int. Symp. on Theoretical Aspects of Computer Science (STACS), 2008.

• Splitting (complicated) surfaces is hard.
  Avec Erin W. Chambers, Jeff Erickson, Francis Lazarus et Kim Whittlesey.
  Computational Geometry: Theory and Applications, 2008, 41:94–110 (ps.gz, pdf, bib).
  Proc. ACM Symp. on Computational Geometry (SOCG), 2006.
  Proc. European Workshop on Computational Geometry (EWCG), 2006.

• Tightening nonsimple paths and cycles on surfaces.
  Avec Jeff Erickson.
  SIAM Journal on Computing, 2010, 39(8):3784–3813 (pdf, bib).
  Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2006.

• Raccourcissement de courbes et décomposition de surfaces.
  Thèse de doctorat de l'Université Paris 7, soutenue le 8 décembre 2003. Détails et téléchargement.
  Prix de thèse de l'Association Française d'Informatique Fondamentale (anciennement AFIT). Accessit du prix de thèse Specif.

• Optimal pants decompositions and shortest homotopic cycles on an orientable surface.
  Avec Francis Lazarus.
  Journal of the ACM, 2007, 54(4), art. 18 (ps.gz, pdf, bib).
  Proc. Int. Symp. on Graph Drawing (GD), 2003.
  Proc. European Workshop on Computational Geometry (EuroCG), 2003.

• Centroidal Voronoi diagrams for isotropic surface remeshing.
  Avec Pierre Alliez, Olivier Devillers et Martin Isenburg.
  Graphical Models, 2005, 67(3):204–231 (pdf, bib).
  Proc. Int. Conf. on Shape Modelling and Applications (SMI), 2003.

• Optimal system of loops on an orientable surface.
  Avec Francis Lazarus.
  Discrete and Computational Geometry, 2005, 33(3):507–534 (ps.gz, pdf, bib). Voir aussi ma thèse, ch. 3.
  Proc. IEEE Symp. on Foundations of Computer Science (FOCS), 2002.
  Proc. European Workshop on Computational Geometry (EWCG), 2002.

• Conforming Delaunay triangulations in 3D.
  Avec David Cohen-Steiner et Mariette Yvinec.
  Computational Geometry: Theory and Applications, 2004, 28(2–3):217–233 (ps.gz, pdf, bib).
  Proc. ACM Symp. on Computational Geometry (SOCG), 2002.

• Tutte's barycenter method applied to isotopies.
  Avec Michel Pocchiola et Gert Vegter.
  Computational Geometry: Theory and Applications, 2003, 26(1):81–97 (ps.gz, pdf, bib, page de compléments).
  Proc. Canadian Conf. on Computational Geometry (CCCG), 2001 (ps.gz, pdf, bib).

• Des choses plus anciennes : stage de D.E.A., stage de programmation, exposé de maîtrise, TIPE.

• 2008-2012: Cours de M2 à l'ENS et/ou au MPRI, Algorithmique des graphes plongés sur une surface. Notes de cours.
• 2007-2008 et 2006-2007: TD au MPRI 1ère année, Géométrie discrète et algorithmique.

• 2007-2011: Projet Triangles (New Challenges in Triangulations), financé par l'Agence Nationale de la Recherche, coordinateur : Olivier Devillers.
• 2009-2010: Partenariat Hubert Curien Algorithms for embedded graphs avec la Slovénie (Sergio Cabello notamment).
• 2005-2007: Projet Problèmes d'Optimisation en Topologie Algorithmique avec l'université de l'Illinois à Urbana-Champaign (Jeff Erickson) et plusieurs participants français.