• Computer Science > Discrete Mathematics [Submitted on 28 Nov 2023 (v1), last revised 24 Feb 2026 (this version, v5)] Title:Local certification of geometric graph classes View PDF HTML (experimental)Abstract:The goal of local certification is to locally convince the vertices of a graph $G$ that $G$ satisfies a given property. • A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view, they must decide whether $G$ satisfies the given property. • If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). • The goal is to minimize the size of the certificates. • In this paper we study the local certification of geometric and topological graph classes. • While it is known that in $n$-vertex graphs, planarity can be certified locally with certificates of size $O(\log n)$, we show that several closely related graph classes require certificates of size $\Omega(n)$.

Article Summaries:

  • Computer Science > Discrete Mathematics [Submitted on 28 Nov 2023 (v1), last revised 24 Feb 2026 (this version, v5)] Title:Local certification of geometric graph classes View PDF HTML (experimental)Abstract:The goal of local certification is to locally convince the vertices of a graph $G$ that $G$ satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view, they must decide whether $G$ satisfies the given property. If the graph i

Sources: