Evènement pour le groupe GT Graphes et Applications


Date 2014-03-28  14:00-15:00
TitreGraphe couvrant planaire de degré borné 
Résumé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.  
LieuSalle 178 
OrateurNicolas Bonichon 



Aucun document lié à cet événement.

Retour
Retour à l'index