Éric COLIN de VERDIÈRE

English version available

Directeur de recherche CNRS au Laboratoire d'Informatique Gaspard Monge, équipe MoA, Marne-la-Vallée.
Sujets d'intérêt : géométrie et topologie algorithmiques et combinatoires, algorithmique des graphes. En particulier, topologie algorithmique de petite dimension (sur les surfaces et les 3-variétés) et algorithmes d'optimisation pour les graphes dans un cadre géométrique ou topologique.
Mon CV.

Bureau 4B121 (plan, accès)
LIGM, bâtiment Copernic
5, bd Descartes
Champs-sur-Marne
77454 Marne-la-Vallée Cedex 2
Tél. (+33).1.60.95.72.88
E-mail: eric

colindeverdiere

u-pem

[Recherche] [Enseignement]

Directeur du Labex Bézout et de la Fédération Bézout, qui promeuvent les interactions entre mathématiques et informatique à l'est de l'Île-de-France.
Executive Editor du European Journal of Combinatorics.
Coordinateur local du projet SoS (Structures sur les Surfaces), financé par l'ANR et le FNR, coordinatrice: Monique Teillaud.
Participant au projet MinMax, financé par l'ANR, coordinateur: Stéphane Sabourau.

Notes sur l'algorithmique des graphes plongés.

Doctorants et post-doctorants:

Galatée Hémery Vaglica, doctorante, sept. 2018-, co-encadrée avec Xavier Goaoc;
Thomas Magnard, doctorant, sept. 2017-;
Zili Wang, post-doc, 2019-2020, principalement encadrée par Alfredo Hubard et Lionel Pournin;
Salman Parsa, post-doctorant, 2015-2016, actuellement post-doctorant à Saint Louis University, États-Unis;
Arnaud de Mesmay, doctorant, 2011-2014, actuellement chercheur CNRS au LIGM;
Alfredo Hubard, post-doctorant, 2012-2013, actuellement maître de conférences à l'Université Gustave Eiffel.

Recherche

li>Deciding contractibility of a non-simple curve on the boundary of a 3-manifold: A computational Loop Theorem.
Avec

Salman Parsa

pdf

bib

Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2017, p. 2691–2704.

Hardness of minimum barrier shrinkage and minimum activation path.
With Sergio Cabello (pdf, bib).
Embeddability of arrangements of pseudocircles and graphs on surfaces.
Avec Carolina Medina, Edgardo Roldán-Pensado et Gelasio Salazar.
Discrete & Computational Geometry, à paraître (pdf, bib).
Almost tight lower bounds for hard cutting problems in embedded graphs.
Avec Vincent Cohen-Addad, Dániel Marx et Arnaud de Mesmay.
Proc. Int. Symp. on Computational Geometry (SoCG), 2019, best paper award, p. 27:1–27:16 (pdf, bib).
Embedding graphs into two-dimensional simplicial complexes.
Avec Thomas Magnard et Bojan Mohar.
Proc. Int. Symp. on Computational Geometry (SoCG), 2018, p. 27:1–27:14 (pdf, bib).
A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals.
Avec Vincent Cohen-Addad et Arnaud de Mesmay.
Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2018, p. 1439–1458 (pdf, bib).
Computational topology of graphs on surfaces.
Chapitre 23 de la troisième édition du Handbook of Discrete and Computational Geometry,
édité par Jacob E. Goodman, Joseph O'Rourke et Csaba Toth, CRC Press LLC, 2018, p. 605–636 (pdf, bib).
Deciding contractibility of a non-simple curve on the boundary of a 3-manifold.
Avec Salman Parsa.
Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2017, p. 2691–2704 (pdf, bib).
A direct proof of the strong Hanani-Tutte theorem on the projective plane.
Avec Vojtěch Kaluža, Pavel Paták, Zuzana Patáková et 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.
Avec Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu et David Meierfrankenfeld.
Proc. ACM Symp. on Theory of Computing (STOC), 2016, p. 584–597 (pdf, bib).
On the complexity of immersed normal surfaces.
Avec Benjamin A. Burton et Arnaud de Mesmay.
Geometry and Topology, 2016, 20:1061–1083 (pdf, bib).
Finding shortest non-trivial cycles in directed graphs on surfaces.
Avec Sergio Cabello et 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, corrigendum, bib).
Proc. European Symposium on Algorithms (ESA), 2015, p. 373-385.
De la carte au territoire ?
Avec Arnaud de Mesmay.
Images des Mathématiques, CNRS, 2014 (vulgarisation autour de l'article Testing graph isotopy on surfaces ci-dessous) (lien, bib).
Discrete systolic inequalities and decompositions of triangulated surfaces.
Avec Alfredo Hubard et 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.
Avec Grégory Ginot et Xavier Goaoc.
Advances in Mathematics, 2014, 253:163–193 (pdf, bib).
Proc. ACM Symp. on Computational Geometry (SOCG), 2012, p. 209–218. Best paper award.
Topological algorithms for graphs on surfaces.
Habilitation à diriger des recherches, soutenue le 29 mai 2012. (pdf, bib, errata).
Testing graph isotopy on surfaces.
Avec 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.
Avec Alexandre Boulch et Atsuhiro Nakamoto.
Graphs and Combinatorics, 2013, 29(6):1675–1688 (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.
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, 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 & 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).

Enseignement

2019-2020: Cours de M2 au MPRI, algorithmique et combinatoire des graphes géométriques.
2019-2020: TD de M1 à l'Université Gustave Eiffel, Complexité des problèmes.

Liens moins récents

Co-organisateur de l'école Low-Dimensional Geometry and Topology: Discrete and Algorithmic Aspects, Paris (IHP), 18–22 juin 2018.
2013-2017: Projet RDAM (Algorithmic Techniques for Restricted Data Access Models), financé par l'Agence Nationale de la Recherche, coordinateur : Frédéric Magniez.
Anciennement, co-organisateur du Séminaire de Géométrie Algorithmique et Combinatoire de la région parisienne.
Organisateur, avec Gilles Schaeffer, de l'École de Printemps d'Informatique Théorique 2016 intitulée Graphes et Surfaces: Algorithmique, Combinatoire et Topologie (notes de cours).
Organisateur, avec Jean-Marc Schlenker et Monique Teillaud, d'un workshop intitulé Computational geometry in non-Euclidean spaces, à Nancy du 26 au 28 août 2015.
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.
Organisateur, avec Boris Thibert, des Journées de Géométrie Algorithmique 2010.