Planarity can be verified by an approximate proof labeling scheme in constant-time

DOI10.1016/j.jcta.2022.105643OpenAlexW4281755042WikidataQ113871615 ScholiaQ113871615MaRDI QIDQ2154327

Gábor Elek

Publication date: 19 July 2022

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

planar graphshyperfinitenessapproximate proof labeling schemesproperty a

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

Local certification of graphs with bounded genus

Cites Work

• Unnamed Item
• Unnamed Item
• General Cheeger inequalities for \(p\)-Laplacians on graphs
• Uniform local amenability
• Every minor-closed property of sparse graphs is testable
• The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space
• Compact distributed certification of planar graphs
• Local certification of graphs on surfaces
• Local certification of graphs with bounded genus
• Proof labeling schemes
• Remarks on Yu’s ‘property A’ for discrete metric spaces and groups
• What Can be Computed Locally?
• Uniform local amenability implies Property A
• Introduction to local certification
• Local Graph Partitions for Approximation and Testing
• On the Impact of Identifiers on Local Decision
• Approximate proof-labeling schemes
• Property testing in bounded degree graphs

This page was built for publication: Planarity can be verified by an approximate proof labeling scheme in constant-time