[inria-00476151, v1] Comment résumer le plan

Author manuscript, published in "12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications(AlgoTel) (2010)"†Commentrésumerleplan‡ ‡§ ‡ ‡Nicolas Bonichon , Cyril Gavoille , Nicolas Hanusse , David Ilcinkas¶and Ljubomir Perkovic´Cet article concerne les graphes de recouvrement d’un ensemble fini de points du plan Euclidien. Un graphe derecouvrement H est de facteur d’étirement t pour un ensemble de points S si, entre deux points quelconques de S,le coût d’un plus court chemin dans H est au plus t fois leur distance Euclidenne. Les graphes de recouvrementd’étirementt (ci-après nommést-spanneurs) sont à la base de nombreux algorithmes de routage et de navigation dansle plan. Le graphe (ou triangulation) de Delaunay, le graphe de Gabriel, le graphe de Yao ou le Theta-graphe sontdes exemples bien connus de t-spanneurs. L’étirement t et le degré maximum des spanneurs sont des paramètresimportant à minimiser pour l’optimisation des ressources. En même temps le caractère planaire des constructions serévèle essentiel dans les algorithmes de navigation.Nous présentons une série de résultats dans ce domaine, en particulier: Nous montrons que le grapheQ (le Theta-graphe oùk= 6 cônes d’angleQ = 2p=k par sommet sont utilisées)6 kest l’union de deux spanneurs planaires d’étirement deux. En particulier, nous établissons que l’étirement max-imum du grapheQ est deux, ce qui est optimal. Des bornes supérieures sur l’étirement du grapheQ n’étaient6 ...