Local certification of geometric graph classes

DOI10.4230/LIPICS.MFCS.2024.48MaRDI QIDQ7241050zbMATH OpenFDO

Authors Oscar Defrain, L. Esperet, A. Lagoutte, Pat Morin, Jean-Florent Raymond

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2024.48

zbMATH Keywords

geometric intersection graphslocal certificationproof labeling schemes

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• 2-Isomorphic Graphs
• A meta-theorem for distributed certification
• Approximate proof-labeling schemes
• Compact distributed certification of planar graphs
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• Graph minors. XX: Wagner's conjecture
• Interactive distributed proofs
• Introduction to local certification
• Local Certification of Graph Decompositions and Applications to Minor-Free Classes
• Local certification of graphs on surfaces
• Local certification of graphs with bounded genus
• Locally checkable proofs in distributed computing
• Proof labeling schemes
• Sparsity. Graphs, structures, and algorithms
• The number of disk graphs
• The power of distributed verifiers in interactive proofs
• Trade-offs in distributed interactive proofs
• Two notions of unit distance graphs
• What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs

Cited in

(1)

• Reductions in local certification

This page was built for publication: Local certification of geometric graph classes

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