Local certification of graphs on surfaces
| Autor: | Esperet, Louis, Lévêque, Benjamin |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Theoretical Computer Science 909 (2022), 68-75 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.tcs.2022.01.023 |
| Popis: | 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 certificates 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. Comment: 10 pages, 5 figures - v4: final version |
| Databáze: | arXiv |
| Externí odkaz: |
|