Un schéma d'étiquetage est une façon de mettre en œuvre de manière distribuée des requêtes portant sur les sommets d'un graphe. Par exemple, un schéma d'étiquetage d'adjacence consiste, dans un premier temps, à attribuer aux sommets d'un graphe une étiquette individuelle (encodage). Puis, dans un deuxième temps, de pouvoir déterminer à l'aide d'un algorithme (décodage) si deux sommets $u$ et $v$ arbiraires du graphe sont adjacents simplement à partir des étiquettes de $u$ et de $v$, et rien d'autre. En particulier l'algorithme de décodage n'a, à aucun moment, accès au graphe ou à une de ses parties, ce qui est un avantage déterminant pour des applications en calcul distribué.
Les schémas d'étiquetage s'étendent à de nombreuses requêtes. Parmi elles: la distance, la distance bornée (est-ce que $u$ et $v$ sont à distance $\le k$? [KV17,AGHP15b]), le routage (quelle est la première arête d'un plus court chemin entre $u$ et $v$ [BC06a]). Il y a même des requêtes impliquant plus de deux sommets, comme l'existence d'un chemin entre $u$ et $v$ dans le graphe privé du sommet $w$ [CGKT09,GH12a] et quelle est longueur du plus courts d'entre-eux [ACGP16]. Il est même possible de considérer des requêtes encore plus générales basées sur la logique du premier ordre [CGK11].
Dans ce stage, on se limitera à l'étude des schémas d'adjacence pour les graphes planaires. Une mesure d'efficacité d'un schéma d'étiquetage est la longueur maximum (en bits) des étiquettes attribuées lors de l'encodage des graphes d'une famille donnée. Dans une article fondateur du domaine [KNR92], il a été montré que les graphes planaires à $n$ sommets ont un schéma d'adjacence avec des étiquettes de $4\log{n}$ bits. Il a également été montré que, de manière générale, tout schéma d'adjacence utilisant des étiquettes de $c\log{n}$ bits implique l'exsitence d'un graphe universel induit de $n^c$ sommets, c'est-à-dire un graphe contenant tous les graphes de la famille comme sous-graphes induits. La borne de $4\log{n}$ de [KNR92] a depuis été améliorée plusieurs fois [GL07,AR14], le record actuel étant de $4/3 \cdot \log{n}$ bits [BGP20], impliquant l'existence d'un graphe universel induit de $n^{4/3}$ sommets pour les graphes planaires à $n$ sommets. Il a été conjecturé que la taille optimale était de seulement $O(n)$, borne qui a été prouvée pour l'instant seulement pour arbres [ADBTK17]. On pourra se reporter à [AAHBx19] pour une liste des plus petits graphes universels induits connus pour diverses familles de graphes.
Dans la recherche d'une borne encore plus serrée pour les graphes planaires, on pourra dans un premier temps essayer de construire des schémas (ou des graphes universels induits) pour des sous-familles de graphes planaires. Parmi elles, les subdivisions de grille rectangulaire, les sous-graphes induits d'une grille, sous-graphes d'une grille, les graphes planaires de degré borné, graphes planaires hamiltoniens [UL97], graphes planaires de pathwidth bornée, et d'autres encore.
Ce sujet se rattache à un domaine de recherche très actif, ayant de nombreuses possibilités d'extensions (soit en terme de famille de graphes, soit en terme de requêtes, soit en terme de liens avec d'autres domaines comme la complexité de communication [Harms19,KUV19]) et peut faire l'objet, selon la motivation et le travail du candidat, d'une poursuite en thèse.
[BC06a] Arthur Brady and Lenore Jennifer Cowen. Exact distance labelings yield additive-stretch compact routing schemes. In 20th International Symposium on Distributed Computing (DISC), volume 4167 of Lecture Notes in Computer Science, pages 339-354. Springer, September 2006.
[GL07] Cyril Gavoille and Arnaud Labourel. Shorter implicit representation for planar graphs and bounded treewidth graphs. In 15th Annual European Symposium on Algorithms (ESA), volume 4698 of Lecture Notes in Computer Science, pages 582-593. Springer, October 2007. Slides available here.
[CGKT09] Bruno Courcelle, Cyril Gavoille, Mamadou Moustapha Kanté, and David Andrew Twigg. Optimal labelling for connectivity checking in planar networks with obstacles. Technical Report hal-00367746, HAL, March 2009.
[CGK11] Bruno Courcelle, Cyril Gavoille, and Mamadou Moustapha Kanté. Compact labelings for efficient first-order model-checking. Journal of Combinatorial Optimization, 21(1):19-46, January 2011.
[GH12a] Cyril Gavoille and Pierre Halftermeyer. Connectivity labeling scheme for graphs on surface. In Bordeaux Graph Workshop (BGW), pages 69-70, November 2012. Slides available here.
[AR14] David Adjiashvili and Noy Rotbart. Labeling schemes for bounded degree graphs. In 41st International Colloquium on Automata, Languages and Programming (ICALP), volume 8573 of Lecture Notes in Computer Science (ARCoSS), pages 375-386. Springer, July 2014.
[AGHP15b] Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen, and Ely Porat. Distance labeling schemes for trees. Technical Report 1507.02618v1 [cs.DS], arXiv, July 2015.
[ACGP16] Ittai Abraham, Shiri Chechik, Cyril Gavoille, and David Peleg. Forbidden-set distance labels for graphs of bounded doubling dimension. ACM Transactions on Algorithms, 12(2):Article No. 22, February 2016.
[KV17] Adrian Kosowski and Laurent Viennot. Beyond highway dimension: Small distance labels using tree skeletons. In 28th Symposium on Discrete Algorithms (SODA), pages 1462-1478. ACM-SIAM, January 2017.
[ADBTK17] Stephen Alstrup, Søren Dahlgaard, and Mathias Bæk Tejs Knudsen. Optimal induced universal graphs and adjacency labeling for trees. Journal of the ACM, 64(4):Article No. 27, August 2017.
[KUV19] Adrian Kosowski, Przemyslaw Uznanski, and Laurent Viennot. Hardness of exact distance queries in sparse graphs through hub labeling. In 38th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 272-279. ACM Press, July 2019.
[AAHBx19] Mikkel Abrahansen, Stephen Alstrup, Jacob Holm, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Near-optimal induced universal graphs for cycles and paths. Discrete Applied Mathematics, November 2019.
[Harms19] Nathaniel Harms. Universal communication, universal graphs, and graph labeling. Technical Report 1911.03757v1 [cs.CC], arXiv, November 2019.
[BGP20] Marthe Bonamy, Cyril Gavoille, and Michał Pilipczuk. Shorter labeling schemes for planar graphs. In 31st Symposium on Discrete Algorithms (SODA). ACM-SIAM, January 2020.
[UL97] Christopher Umans, William Lenhart. Hamiltonian cycles in solid grid graphs. In 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 496-505. IEEE Computer Society Press, October 1997.