Éric COLIN de VERDIÈRE

CNRS research director at Laboratoire d'Informatique Gaspard Monge, MoA team, Marne-la-Vallée. Areas of research: computational and combinatorial geometry and topology, graph algorithms. In particular, low-dimensional computational topology (on surfaces and three-manifolds) and optimization algorithms for graphs in a geometric/topological context. My CV.

Office 4B121 (map, access) LIGM, bâtiment Copernic 5, bd Descartes Champs-sur-Marne 77454 Marne-la-Vallée Cedex 2, France Phone: (+33).1.60.95.72.88 E-mail: ericcolindeverdiereu-pemfr

• Head of the Bézout Labex and of the Bézout Federation, fostering interactions between mathematics and computer science in the East of the Paris region.
• Executive Editor of the European Journal of Combinatorics.
• Local coordinator of the project SoS (Structures on Surfaces), funded by ANR and FNR, coordinator: Monique Teillaud.
• Participant of the project MinMax, funded by ANR, coordinator: Stéphane Sabourau.

Notes on algorithms for embedded graphs.

Ph.D. students and post-docs:

• Galatée Hémery Vaglica, Ph.D. student, Sep. 2018-, co-advised with Xavier Goaoc;
• Thomas Magnard, Ph.D. student, Sep. 2017-;
• Zili Wang, post-doc, 2019-2020, co-advised with Alfredo Hubard and Lionel Pournin;
• Salman Parsa, post-doc, 2015-2016, now post-doc at Saint Louis University, USA;
• Arnaud de Mesmay, Ph.D. student, 2011-2014, now CNRS researcher at LIGM;
• Alfredo Hubard, post-doc, 2012-2013, now assistant professor at Université Paris-Est Marne-la-Vallée.

• Hardness of minimum barrier shrinkage and minimum activation path.
  With Sergio Cabello (pdf, bib).

• Embeddability of arrangements of pseudocircles and graphs on surfaces.
  With Carolina Medina, Edgardo Roldán-Pensado, and Gelasio Salazar.
  Discrete & Computational Geometry, to appear (pdf, bib).

• Almost tight lower bounds for hard cutting problems in embedded graphs.
  With Vincent Cohen-Addad, Dániel Marx, and Arnaud de Mesmay.
  Proc. Int. Symp. on Computational Geometry (SoCG), 2019, best paper award, pp. 27:1–27:16 (pdf, bib).

• Embedding graphs into two-dimensional simplicial complexes.
  With Thomas Magnard and Bojan Mohar.
  Proc. Int. Symp. on Computational Geometry (SoCG), 2018, pp. 27:1–27:14 (pdf, bib).

• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals.
  With Vincent Cohen-Addad and Arnaud de Mesmay.
  Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2018, pp. 1439–1458 (pdf, bib).

• Computational topology of graphs on surfaces.
  Chapter 23 of the third edition of the Handbook of Discrete and Computational Geometry,
  edited by Jacob E. Goodman, Joseph O'Rourke, and Csaba Toth, CRC Press LLC, 2018, pp. 605–636 (pdf, bib).

• Deciding contractibility of a non-simple curve on the boundary of a 3-manifold.
  With Salman Parsa.
  Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2017, pp. 2691–2704 (pdf, bib).

• A direct proof of the strong Hanani-Tutte theorem on the projective plane.
  With Vojtěch Kaluža, Pavel Paták, Zuzana Patáková, and Martin Tancer.
  Journal of Graph Algorithms and Applications, 2017, 21(5):939–981 (pdf, bib).
  Proc. Int. Symp. on Graph Drawing and Network Visualization (GD), 2016.

• Approximating connectivity domination in weighted bounded-genus graphs.
  With Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu, and David Meierfrankenfeld.
  Proc. ACM Symp. on Theory of Computing (STOC), 2016, pp. 584–597 (pdf, bib).

• On the complexity of immersed normal surfaces.
  With Benjamin A. Burton and Arnaud de Mesmay.
  Geometry and Topology, 2016, 20:1061–1083 (pdf, bib).

• Finding shortest non-trivial cycles in directed graphs on surfaces.
  With Sergio Cabello and Francis Lazarus.
  Journal of Computational Geometry, 2016, 7(1):123–148 (pdf, bib).
  Proc. ACM Symp. on Computational Geometry (SOCG), 2010.

• Multicuts in planar and bounded-genus graphs with bounded number of terminals.
  Algorithmica, 2017, 78(4):1206–1224 (pdf, bib).
  Proc. European Symposium on Algorithms (ESA), 2015, pp. 373-385.

• De la carte au territoire ? (in French)
  Avec Arnaud de Mesmay.
  Images des Mathématiques, CNRS, 2014 (popularization article around Testing graph isotopy on surfaces below) (link, bib).

• Discrete systolic inequalities and decompositions of triangulated surfaces.
  With Alfredo Hubard and Arnaud de Mesmay.
  Discrete & Computational Geometry, 2015, 53(3):587–620 (pdf, bib).
  Proc. ACM Symp. on Computational Geometry (SOCG), 2014.

• Helly numbers of acyclic families.
  With Grégory Ginot and Xavier Goaoc.
  Advances in Mathematics, 2014, 253:163–193 (pdf, bib).
  Proc. ACM Symp. on Computational Geometry (SOCG), 2012, pp. 209–218. Best paper award.

• 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.
  Discrete & Computational Geometry, 2014, 51(1):171–206 (pdf, bib).
  Proc. ACM Symp. on Computational Geometry (SOCG), 2012.

• Irreducible triangulations of surfaces with boundary.
  With Alexandre Boulch and Atsuhiro Nakamoto.
  Graphs and Combinatorics, 2013, 29(6):1675–1688 (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.

• 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 & 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).

• 2019-2020: Graduate (M2) course at MPRI, algorithms and combinatorics for geometric graphs.
• 2019-2020: Exercise sessions of graduate (M1) course at Université Paris-Est Marne-la-Vallée, Complexity of problems.