/Exposé en anglais/Talk in english/
Given n points in the plane, a spanning tree is a set of n-1 straight line edges connecting them while inducing a tree. We consider only those trees that are non-crossing, i.e. where no two edges are allowed to cross. Our goal is to transform a tree into another using as few operations as possible. Here, the operations consist in adding an edge and removing another so that the resulting graph remains a non-crossing spanning tree. While it is easy to show that there is a transformation between any two non-crossing spanning trees, beating the 2n naive upper bound stood up as an open problem for 25 years. In this talk, we will present the recent improvements on this topic.
This is based on joint works with Nicolas Bousquet, Valentin Gledel, Lucas De Meyer, Jonathan Narboni and Alexandra Wesolek.
[Théo Pierron] (LIRIS )
https://perso.liris.cnrs.fr/tpierron/indexfr.html
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .