BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20240331T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20241027T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20240123T100000
DTEND;TZID=Europe/Paris:20240123T110000
DTSTAMP:20260422T211804
CREATED:20231215T143227Z
LAST-MODIFIED:20240108T095104Z
UID:11368-1706004000-1706007600@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Untangling Graphs on Surfaces »\, Loïc Dubois (LIGM\, Univ. G.Eiffel)
DESCRIPTION:Consider a graph drawn on a surface (for example\, the plane minus a finite set of obstacle points)\, possibly with crossings. We provide a polynomial time algorithm to decide whether such a drawing can be untangled\, namely\, if one can slide the vertices and edges of the graph on the surface (avoiding the obstacles) to remove all crossings; in other words\, whether the drawing is homotopic to an embedding. While the problem boils down to planarity testing when the surface is the sphere or the disk (or equivalently the plane without any obstacle)\, the other cases have never been studied before\, except when the input graph is a cycle\, in an abundant literature in topology and more recently by Despré and Lazarus [SoCG 2017\, J. ACM 2019].
URL:https://www.greyc.fr/event/seminaire-algorithmique-loic-dubois-ligm-univ-g-eiffel/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
END:VCALENDAR