Abstract FR:

La représentation implicite de graphes a été introduite en 1966 par Breuer afin de calculer l'adjacence dans les graphes à partir de données locales encodées par chaque sommet. Dans ce document, on s'est intéressé à cette notion pour de nombreuses familles de graphes et en particulier pour les graphes sur surfaces. Afin de pouvoir utiliser les représentations implicites existantes sur les forêts, on montre tout d'abord l'existence d'une partition des arêtes des graphes de genre d'Euler g en trois forêts plus un ensemble d'au plus 3g - 3 arêtes. On présente une représentation implicite pour les arbres de degré interne borné par d̂ ayant n sommets avec des étiquettes de log n + O (log d̂) bits. Enfin, on décrit une représentation implicite pour les graphes planaires et les graphes de genre borné en (2 + 0(1)) log n bits déduite d'une représentation implicite pour les graphes de largeur arborescente bornée avec des étiquettes de (1 + 0(1)) log n bits. On utilise une technique similaire afin d'obtenir un schéma k-relationnel sur les arbres.