Séminaire
|
Date : 12 mars 2026 14:00 - Salle :Amphi 3 - Pôle commun
Algorithms for drawing graphs with no or few crossings in the plane, on surfaces, and beyondEric Colin de Verdière, Directeur de Recherche CNRS - LIGM - Champs-sur-Marne |
Planarity testing, the problem of deciding whether an input graph can be drawn without crossings in the plane, is known to be solvable in linear time since the 1970s. A distinctive feature of this problem is that it lies at the crossroad between topology and algorithms. In this talk, we will survey some natural and recent generalizations: Since some graphs are nonplanar, can we draw them without crossings in more general spaces, such as surfaces, or even more general spaces, obtained by gluing vertices, edges, and triangles together? If a graph cannot be drawn without crossings on a given space, how to draw it with as few crossings as possible? How can we untangle a graph drawn with crossings on a surface, if it is possible?
(Joint works with Vincent Despré, Loïc Dubois, Petr Hliněný, and Thomas Magnard)
http://monge.univ-mlv.fr/~colinde/