Éric COLIN de VERDIÈRE

Born May 8, 1977. CNRS researcher in the GéCoaL team of the Computer Science Department of École normale supérieure (Paris). Topics of interest: computational geometry, computational topology of surfaces, shortest path, homotopy, deformation, parameterization, mesh. My CV.

École normale supérieure, Département d'Informatique 45 rue d'Ulm, F-75230 Paris Cedex 05, 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, room 7 E-mail: , GPG key

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

Research

• Sergio Cabello, Éric Colin de Verdière, and Francis Lazarus. Output-sensitive algorithm for the edge-width of an embedded graph. Submitted.

• Sergio Cabello, Éric Colin de Verdière, and Francis Lazarus. Finding shortest non-trivial cycles in directed graphs on surfaces. Submitted.

• Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, and Shripad Thite. Homotopic Fréchet distance between curves --- or, Walking your dog in the woods in polynomial time.
  Proc. ACM. Symp. on Computational Geometry (SOCG'08), June 2008, pp. 101-109 (pdf, bib).
  Full version to appear in Computational Geometry: Theory and Applications, vol. 43, p. 295-311, 2010.
  Preliminary version in Proc. Fall Workshop on Computational Geometry (FWCG'07), Nov. 2007.

• Éric Colin de Verdière and Alexander Schrijver. Shortest vertex-disjoint two-face paths in planar graphs.
  Proc. Int. Symp. on Theoretical Aspects of Computer Science (STACS'08), Feb. 2008, pp. 181-192 (ps.gz, pdf, bib).
  Journal version to appear in ACM Transactions on Algorithms.

• Erin W. Chambers, Éric Colin de Verdière, Jeff Erickson, Francis Lazarus, and Kim Whittlesey. Splitting (complicated) surfaces is hard.
  Computational Geometry: Theory and Applications, vol. 41, pp. 94-110, Oct. 2008 (ps.gz, pdf, bib).
  Conference version in Proc. ACM Symp. on Computational Geometry (SOCG'06), June 2006.
  Preliminary version in Proc. European Workshop on Computational Geometry (EWCG'06), Mar. 2006.

• Éric Colin de Verdière and Jeff Erickson. Tightening non-simple paths and cycles on surfaces.
  Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA'06), Jan. 2006, pp. 192-201 (ps.gz, pdf, bib). Full version submitted to journal.

• Éric Colin de Verdière. Shortening of curves and decomposition of surfaces.
  PhD thesis of University Paris 7, defended 8 December 2003. Details and downloading.
  Thesis award from the Association Française d'Informatique Fondamentale (formerly AFIT). Accessit of the Specif thesis award.

• Éric Colin de Verdière and Francis Lazarus. Optimal pants decompositions and shortest homotopic cycles on an orientable surface.
  Journal of the ACM, vol. 54, no 4, art. 18, July 2007 (ps.gz, pdf, bib).
  Conference version in Proc. Int. Symp. on Graph Drawing (GD'03), Sept. 2003.
  Preliminary version in Proc. European Workshop on Computational Geometry (EuroCG'03), March 2003.

• Pierre Alliez, Éric Colin de Verdière, Olivier Devillers, and Martin Isenburg. Centroidal Voronoi diagrams for isotropic surface remeshing.
  Graphical Models, vol. 67, no 3, pp. 204-231, May 2005 (pdf, bib).
  Conference version in Proc. Int. Conf. on Shape Modelling and Applications (SMI'03), May 2003.

• Éric Colin de Verdière and Francis Lazarus. Optimal system of loops on an orientable surface.
  Discrete and Computational Geometry, vol. 33, no 3, pp. 507-534, Mar. 2005 (ps.gz, pdf, bib). See my Ph.D. thesis, Ch. 3.
  Conference version in Proc. IEEE Symp. on Foundations of Computer Science (FOCS'02), Nov. 2002, pp. 627-636.
  Preliminary version in Proc. European Workshop on Computational Geometry (EWCG'02), Apr. 2002.

• David Cohen-Steiner, Éric Colin de Verdière, and Mariette Yvinec. Conforming Delaunay triangulations in 3D.
  Computational Geometry: Theory and Applications, vol. 28, no 2-3, pp. 217-233, June 2004 (ps.gz, pdf, bib).
  Conference version in Proc. ACM Symp. on Computational Geometry (SOCG'02), June 2002, pp. 199-208.

• Éric Colin de Verdière, Michel Pocchiola et Gert Vegter. Tutte's barycenter method applied to isotopies.
  Computational Geometry: Theory and Applications, vol. 26, no 1, pp. 81-97, Aug. 2003 (ps.gz, pdf, bib, companion page).
  Conference version in Proc. Canadian Conf. on Computational Geometry (CCCG'01), Aug. 2001 (ps.gz, pdf, bib).

• Some older things ([mainly French]): D.E.A. stage, programming stage, maîtrise talk, TIPE.

• 2009-2010 and 2008-2009: Course at Master Parisien de Recherche en Informatique (MPRI) 2nd year, Algorithms for graphs on surfaces. Course notes.
• 2007-2008 and 2006-2007: Exercise sessions at MPRI 1st year. Discrete and computational geometry.

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