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

Approximate proof labeling schemes were introduced by Censor-Hillel, Paz and Perry [3]. Roughly speaking, a graph property P can be verified by an approximate proof labeling scheme in constant-time if the vertices of a graph having the property can be convinced, in a short period of time not dependi...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series A 2022-10, Vol.191, p.105643, Article 105643
Main Author: Elek, Gábor
Format: Article
Language:English
Subjects:
Approximate proof labeling schemes
Hyperfiniteness
Planar graphs
Property A
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Approximate proof labeling schemes were introduced by Censor-Hillel, Paz and Perry [3]. Roughly speaking, a graph property P can be verified by an approximate proof labeling scheme in constant-time if the vertices of a graph having the property can be convinced, in a short period of time not depending on the size of the graph, that they are having the property P or at least they are not far from being having the property P. The main result of this paper is that bounded-degree planar graphs (and also outer-planar graphs, bounded genus graphs, knotlessly embeddable graphs etc.) can be verified by an approximate proof labeling scheme in constant-time.
ISSN:0097-3165
1096-0899
DOI:10.1016/j.jcta.2022.105643