Local certification of graphs on surfaces

DOI10.1016/j.tcs.2022.01.023OpenAlexW4205780172MaRDI QIDQ2078616

Louis Esperet, Benjamin Lévêque

Publication date: 1 March 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.04133

zbMATH Keywords

planar graphsgraphs on surfaceslocal certificationproof labelling schemes

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (3)

Planarity can be verified by an approximate proof labeling scheme in constant-time ⋮ Lower bound for constant-size local certification ⋮ Local certification of graphs with bounded genus

Cites Work

• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• The local detection paradigm and its applications to self-stabilization
• Distributed coloring in sparse graphs with fewer colors
• Proof labeling schemes
• The Power of Distributed Verifiers in Interactive Proofs
• Compact Distributed Certification of Planar Graphs

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