14:00
15:00

[gt.go] - "Approximation Schemes for finding multicolored non-crossing structures in the plane and in planar graphs" by François Dross

/Exposé en anglais/Talk in english/

In this presentation, we will talk about connecting colored points via noncrossing structures. Several problems fall into this category. G iven a set of colored terminal points, we want to find a graph for each color that connects all terminals of its color with the restrictio n that no two graphs cross each other. We will look for such graphs with certain specific structure. If the graph is not restrained (or re strained to be a tree), the problem is Multicolored Non-crossing Steiner Tree. If the graph is a cycle, the problem is Multicolored Non-cr ossing Travelling Salesman Problem... We will consider these problems both on the Euclidean plane and in planar graphs. Another linked pro blem that we will talk about is the problem of separating colored points in the plane accoring to their colors, using non-crossing cycles.

The aim of this talk will be to present a method to approximate these problems efficiently, when there is a small number of colors (two o r three, depending on the problem). The trick relies on a way to bound the number of times a given area in the plane, that we will call po rtal, needs to be crossed when there are two colors. The rest of the proof heavily relies on Arora's scheme, that we will also present. We may also have time to talk about the negative side, and, more precisely, complexity results.

[François Dross] (LaBRI )

https://sites.google.com/view/francoisdross/home

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 ] .

https://webconf.u-bordeaux.fr/b/mar-ef4-zed and LaBRI/178