2021/02/28 by Louis Esperet, Benjamin Lévêque
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Certificate #Combinatorics #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Mathematics #Planar graph #Vertex (graph theory) #cs.DC #math.CO
paper · pdf · open access · doi:10.1016/j.tcs.2022.01.023
published in Theoretical Computer Science 909, 68-75 (Elsevier BV) · 10 pages, 5 figures - v4: final version
openalex created_date 2021/02/15 · arxiv created 2022/01/18 · openalex publication_date 2022/01/20 · arxiv updated 2022/03/01 · openalex updated_date 2026/08/06
A proof labelling scheme for a graph class C is an assignment of certificates to the vertices of any graph in the class C, such that upon reading its certificate and the certificates of its neighbors, every vertex from a graph G∈ C accepts the instance, while if G\not∈ C, for every possible assignment of certificates, at least one vertex rejects the instance. It was proved recently that for any fixed surface Σ, the class of graphs embeddable in Σ 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.