Home > Research > Publications & Outputs > Planarity can be Verified by an Approximate Pro...

Research

Electronic data

  • legujlocal

    Accepted author manuscript, 393 KB, PDF document

    Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

Planarity can be Verified by an Approximate Proof Labeling Scheme in Constant-Time

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Planarity can be Verified by an Approximate Proof Labeling Scheme in Constant-Time. / Elek, Gabor.
In: Journal of Combinatorial Theory, Series A, Vol. 191, 105643, 31.10.2022.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Elek, G 2022, 'Planarity can be Verified by an Approximate Proof Labeling Scheme in Constant-Time', Journal of Combinatorial Theory, Series A, vol. 191, 105643. https://doi.org/10.1016/j.jcta.2022.105643

APA

Elek, G. (2022). Planarity can be Verified by an Approximate Proof Labeling Scheme in Constant-Time. Journal of Combinatorial Theory, Series A, 191, Article 105643. https://doi.org/10.1016/j.jcta.2022.105643

Vancouver

Elek G. Planarity can be Verified by an Approximate Proof Labeling Scheme in Constant-Time. Journal of Combinatorial Theory, Series A. 2022 Oct 31;191:105643. Epub 2022 Jun 10. doi: 10.1016/j.jcta.2022.105643

Author

Elek, Gabor. / Planarity can be Verified by an Approximate Proof Labeling Scheme in Constant-Time. In: Journal of Combinatorial Theory, Series A. 2022 ; Vol. 191.

Bibtex

@article{54ad895b2a184493af91ede8168982cc,
title = "Planarity can be Verified by an Approximate Proof Labeling Scheme in Constant-Time",
abstract = "Approximate proof labeling schemes were introduced by Censor-Hillel, Paz and Perry. 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 oftime not depending on the size of the graph, that they are having the property P or at leastthey 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. ",
keywords = "Approximate proof labeling schemes, Planar graphs, Property A, Hyperfiniteness",
author = "Gabor Elek",
year = "2022",
month = oct,
day = "31",
doi = "10.1016/j.jcta.2022.105643",
language = "English",
volume = "191",
journal = "Journal of Combinatorial Theory, Series A",
issn = "0097-3165",
publisher = "Academic Press Inc.",

}

RIS

TY - JOUR

T1 - Planarity can be Verified by an Approximate Proof Labeling Scheme in Constant-Time

AU - Elek, Gabor

PY - 2022/10/31

Y1 - 2022/10/31

N2 - Approximate proof labeling schemes were introduced by Censor-Hillel, Paz and Perry. 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 oftime not depending on the size of the graph, that they are having the property P or at leastthey 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.

AB - Approximate proof labeling schemes were introduced by Censor-Hillel, Paz and Perry. 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 oftime not depending on the size of the graph, that they are having the property P or at leastthey 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.

KW - Approximate proof labeling schemes

KW - Planar graphs

KW - Property A

KW - Hyperfiniteness

U2 - 10.1016/j.jcta.2022.105643

DO - 10.1016/j.jcta.2022.105643

M3 - Journal article

VL - 191

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

SN - 0097-3165

M1 - 105643

ER -