Éric COLIN de VERDIÈRE

CNRS researcher in the Talgo team (formerly GéCoaL) of the Computer Science Department of École normale supérieure (Paris). Topics of interest: algorithms and combinatorics, geometry and topology (computational geometry, computational topology of surfaces, combinatorial optimization, graph algorithms). My CV.

École normale supérieure, Département d'Informatique 45, rue d'Ulm, 75005 Paris, France Phone (+33).1.44.32.20.53 fax (+33).1.44.32.21.56 (send me e-mail about it) "Hauts du DI", Staircase A, 3rd floor E-mail: , GPG key

The website of the French Computational Geometry Days 2010, co-organized with Boris Thibert.

Research

• Topological algorithms for graphs on surfaces.
  Habilitation thesis, defended on May 29, 2012. (pdf, bib, errata).

• Testing graph isotopy on surfaces.
  With Arnaud de Mesmay.
  Proc. ACM Symp. on Computational Geometry (SOCG), 2012, pp. 141–150 (long version: pdf, bib).

• Multinerves and Helly numbers of acyclic families.
  With Grégory Ginot and Xavier Goaoc.
  Proc. ACM Symp. on Computational Geometry (SOCG), 2012, pp. 209–218. Best paper award.
  arXiv version (pdf).

• Irreducible triangulations of surfaces with boundary.
  With Alexandre Boulch and Atsuhiro Nakamoto.
  Graphs and Combinatorics, to appear. ArXiv preprint (pdf, bib).

• Finding cycles with topological properties in embedded graphs.
  With Sergio Cabello and 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.
  With Sergio Cabello and 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.
  With Sergio Cabello and 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.
  With Erin W. Chambers, Jeff Erickson, Sylvain Lazard, Francis Lazarus, and 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.
  With 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.
  With Erin W. Chambers, Jeff Erickson, Francis Lazarus, and 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.
  With Jeff Erickson.
  SIAM Journal on Computing, 2010, 39(8):3784–3813 (pdf, bib).
  Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2006.

• Shortening of curves and decomposition of surfaces.
  Ph.D. thesis, defended on Dec. 8, 2003. Details and downloading.
  Thesis award of the Association Française d'Informatique Fondamentale (formerly AFIT). Accessit of the Specif thesis award.

• Optimal pants decompositions and shortest homotopic cycles on an orientable surface.
  With 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.
  With Pierre Alliez, Olivier Devillers, and 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.
  With Francis Lazarus.
  Discrete and Computational Geometry, 2005, 33(3):507–534 (ps.gz, pdf, bib). See also my thesis, 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.
  With David Cohen-Steiner and 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.
  With Michel Pocchiola and Gert Vegter.
  Computational Geometry: Theory and Applications, 2003, 26(1):81–97 (ps.gz, pdf, bib, companion page).
  Proc. Canadian Conf. on Computational Geometry (CCCG), 2001 (ps.gz, pdf, bib).

• Some older things (in French): D.E.A. internship, programming internship, maîtrise talk, TIPE.

• 2012-2013: Graduate course at MPRI, Algorithms for embedded graphs. Course notes.
• 2008-2012: Graduate course at ENS and/or MPRI, Algorithms for graphs on surfaces. Course notes.
• 2007-2008 and 2006-2007: Exercise sessions at MPRI 1st year, Discrete and computational geometry.

• 2007-2011: Project Triangles (New Challenges in Triangulations), funded by the French National Research Agency, coordinator: Olivier Devillers.
• 2009-2010: Partenariat Hubert Curien Algorithms for embedded graphs with Slovenia (Sergio Cabello).
• 2005-2007: Project Optimization Problems in Computational Topology with University of Illinois at Urbana-Champaign (Jeff Erickson) and several French participants.