Journées ANR EGOS 2013

Nous écouterons des exposés dans la matinée et discuterons par groupes dans l'après-midi sur divers sujets liés à l'ANR EGOS. Le programme des exposés est le suivant :

Lundi 28 octobre à 10h Salle Grace Hopper Daniel Goncalves (LIRMM) On attempts to generalize Schnyder woods to other oriented surfaces Schnyder woods, are orientations and edge-colorings (with some properties) of planar or toroidal maps. This structure has many properties and it has been shown that every \(3\)-connected planar or toroidal map admits such a structure. Our aim in this work was to show that every \(3\)-connected map of an oriented surface \(S\) admits a (natural generalization of) Schnyder woods. We will first review what relations link different Schnyder wood of a given map. We will then give a necessary and sufficient condition for an orientation of a map, to be extendable into a Schnyder wood. This will give us an alternative proof for the existence of Schnyder woods in toroidal triangulations. Finally, we will focus on triangulations (of oriented surfaces) and show that they admit orientations such that for every vertex \(v\), \(d^+(v)\) is either \(3\), \(6\),...; which is a necessary condition for admitting a Schnyder wood.

Lundi 28 octobre à 11h30 Salle Grace Hopper Michel Pocchiola (IMJ) Arrangements de double pseudodroites Un arrangement de double pseudodroites est une famille finie de lacets simples triviaux du plan projectif s'intersectant deux-à-deux en quatre points d'intersection transverse et induisant deux-à-deux une décomposition cellulaire du plan projectif.
L'exposé portera sur la combinatoire de ces arrangements en lien avec l'algorithmique des graphes de visibilité.

Mardi 29 octobre à 10h Salle Grace Hopper Kolja Knauer (I3M, Montpellier) Making Octants Colorful We prove that for any positive integer \(k\), every finite set of points in \(\mathbb{R}^3\) can be colored with \(k\) colors so that every translate of the negative octant containing at least \(k^6\) points contains at least one of each color. The best previously known bound was doubly exponential in \(k\). This yields, among other corollaries, the first polynomial bound for the decomposability of multiple covers by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line.

Mardi 29 octobre à 11h30 Salle Grace Hopper Éric Colin de Verdière (DI, ENS) Algorithmes topologiques pour les graphes tracés sur des surfaces Considérons un graphe dessiné sans croisement sur une surface « compliquée » (homéomorphe à une sphère à laquelle on recolle des poignées). Comment trouver la plus courte courbe fermée dans le graphe qu'on ne peut pas contracter en un point en la faisant glisser sur la surface ? Comment trouver un sous-graphe court qui découpe la surface en une région planaire (homéomorphe à un disque) ?
Résoudre ces problèmes algorithmiquement est nécessaire pour étudier des questions plus générales en théorie topologique des graphes et en algorithmique des graphes sur les surfaces. On présentera un panorama des techniques récentes pour résoudre ce type de problèmes dans divers cas (graphe pondéré ou non, orienté ou non), et on donnera des bornes inférieures et supérieures sur la longueur de plus courtes décompositions de surfaces triangulées, en utilisant des résultats de géométrie riemannienne et des triangulations aléatoires de surfaces.
Cet exposé survolera plusieurs résultats dûs à Sergio Cabello, Jeff Erickson, Kyle Fox, Sariel Har-Peled, Alfredo Hubard, Francis Lazarus, Arnaud de Mesmay, Kim Whittlesey, et l'orateur.

Mercredi 30 octobre à 10h Salle Grace Hopper Anatolii Kostrygin (X 2010) Dessin de graphes planaires sur une grille polynomiale avec bord rectangulaire périodique We present a new algorithm to compute periodic (planar) straight-line drawings of toroidal graphs. Our algorithm is the first to achieve two important aesthetic criteria: the drawing fits in a straight rectangular frame, and the grid area is polynomial, precisely the grid size is \(O(n^4 \times n^4)\). This solves the problem of the identifying of the vertices on the opposite sides - one of the main open problems in a recent paper by Duncan et al.

Mercredi 30 octobre à 11h30 Salle Grace Hopper Nicolas Bonichon (LaBRI) Spanners planaires de degré borné This talk considers the question: « What is the smallest maximum degree that can be achieved for a plane spanner of a complete Euclidean graph? » Without the planarity constraint, it is known that the answer is \(3\) which is also the best known lower bound on the degree of any plane spanner. With the planarity requirement, the best known upper bound on the maximum degree is \(6\), the last in a long sequence of results improving the upper bound. In this talk we show that the complete Euclidean graph always contains a plane spanner of maximum degree \(4\).