Local certification of graphs on surfaces

DOI10.1016/J.TCS.2022.01.023MaRDI QIDQ6360106arXivFDO

Authors L. Esperet, Benjamin Lévêque

Publication date 8 February 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2022.01.023

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

arXiv classification

math.COcs.DC

Abstract: A proof labelling scheme for a graph class $mathcalC$ is an assignment of certificates to the vertices of any graph in the class $mathcalC$, such that upon reading its certificate and the certificates of its neighbors, every vertex from a graph $GinmathcalC$ accepts the instance, while if $GotinmathcalC$, 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(logn)$ 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.

This page was built for publication: Local certification of graphs on surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6360106)