论文标题
平面性可以通过恒定时间的近似证明标签方案来验证
Planarity can be Verified by an Approximate Proof Labeling Scheme in Constant-Time
论文作者
论文摘要
\\ censor-Hillel，Paz和Perry \ Cite {CPP}引入了近似证明标签方案。粗略地说，如果可以说服具有该属性的图形的顶点，则可以通过恒定时间来验证图形属性〜$ \ cp $，可以通过恒定时间来验证，在短时间内，不取决于图形的大小，他们在属性$ \ cp $或至少与拥有属性$ \ cp $ \ cp $相距不远。本文的主要结果是可以通过恒定时间以近似的证明标记方案来验证有界的平面图（以及外部平面图，有界属图，无结的属图等）。
Approximate proof labeling schemes were introduced by \\Censor-Hillel, Paz and Perry \cite{CPP}. Roughly speaking, a graph property~$\cP$ 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 $\cP$ or at least they are not far from being having the property $\cP$. 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.
