Local certification of graphs on surfaces - Optimisation Combinatoire
Article Dans Une Revue Theoretical Computer Science Année : 2022

Local certification of graphs on surfaces

Louis Esperet
Benjamin Lévêque

Résumé

A proof labelling scheme for a graph class $\mathcal{C}$ is an assignment of certificates to the vertices of any graph in the class $\mathcal{C}$, such that upon reading its certificate and the certificate of its neighbors, every vertex from a graph $G\in \mathcal{C}$ accepts the instance, while if $G\not\in \mathcal{C}$, for every possible assignment of certificates, at least one vertex rejects the instance. It was proved recently that for any fixed surface $\Sigma$, the class of graphs embeddable in $\Sigma$ has a proof labelling scheme in which each vertex of an $n$-vertex graph receives a certificate of at most $O(\log n)$ bits. The proof is quite long and intricate and heavily relies on an earlier result for planar graphs. Here we give a very short proof for any surface. The main idea is to encode a rotation system locally, together with a spanning tree supporting the local computation of the genus via Euler's formula.
Fichier principal
Vignette du fichier
S0304397522000354.pdf (501.88 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03135544 , version 1 (22-07-2024)

Licence

Identifiants

Citer

Louis Esperet, Benjamin Lévêque. Local certification of graphs on surfaces. Theoretical Computer Science, 2022, 909, pp.68-75. ⟨10.1016/j.tcs.2022.01.023⟩. ⟨hal-03135544⟩
54 Consultations
25 Téléchargements

Altmetric

Partager

More