Planarisation de graphes dans les réseaux ad-hoc

Abstract : We propose a radically new family of geometric graphs, i.e., Hypocomb, Reduced Hypocomb and Local Hypocomb. The first two are extracted from a complete graph; the last is extracted from a Unit Disk Graph (UDG). We analytically study their properties including connectivity, planarity and degree bound. All these graphs are connected (provided the original graph is connected) planar. Hypocomb has unbounded degree while Reduced Hypocomb and Local Hypocomb have maximum degree 6 and 8, respectively. To our knowledge, Local Hypocomb is the first strictly-localized, degree-bounded planar graph computed using merely 1-hop neighbor position information. We present a construction algorithm for these graphs and analyze its time complexity. Hypocomb family graphs are promising for wireless ad hoc networking. We report our numerical results on their average degree and their impact on FACE routing. We discuss their potential applications and pinpoint some interesting open problems for future research.
Type de document :
[Research Report] RR-7340, INRIA. 2010
Liste complète des métadonnées
Contributeur : Nathalie Mitton <>
Soumis le : jeudi 22 juillet 2010 - 09:52:29
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : jeudi 30 mars 2017 - 01:14:19


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00504683, version 2



Xu Li, Nathalie Mitton, Isabelle Simplot-Ryl, David Simplot-Ryl. Planarisation de graphes dans les réseaux ad-hoc. [Research Report] RR-7340, INRIA. 2010. 〈inria-00504683v2〉



Consultations de la notice


Téléchargements de fichiers