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.
翻译:图形类 $\ mathcal{ C} $ 的 校对标签方案 : 将证书指派给 $\ mathcal{ C} $ 类中任何图表的顶部, 也就是说, 读取它的证书和邻居的证书时, 每一个图形 $G\ in\ mathcal{ C} $ 接受这个例子, 而如果$G\ not\ in\ mathcal{ C} $, 对于每一个可能指派的证书, 至少有一个顶部拒绝这个例子。 最近证明, 对于任何固定表面 $\ Sigma$ 的顶部, 以 $\ Sigma$ 嵌入的图表类别有一个校对标签方案, 其中每个 $n- verdex 图形 的顶部得到最多为 $O (\ log n) 位的证书 。 证据非常长, 复杂, 并且严重依赖更早的 planar 图形结果 。 这里我们给出一个非常短的表面证据 。 。 。 主要的想法是在当地编码一个旋转系统, 以及一个覆盖树 支持 Euler 公式 本地 。