English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The problem of characterizing testable graph properties (properties that canbe tested with a number of queries independent of the input size) is afundamental problem in the area of property testing. While there has been someextensive prior research characterizing testable graph properties in the densegraphs model and we have good understanding of the bounded degree graphs model,no similar characterization has been known for general graphs, with no degreebounds. In this paper we take on this major challenge and consider the problemof characterizing all testable graph properties in general planar graphs.  We consider the model in which a general planar graph can be accessed by therandom neighbor oracle that allows access to any given vertex and access to arandom neighbor of a given vertex. We show that, informally, a graph property$P$ is testable with one-sided error for general planar graphs if and only iftesting $P$ can be reduced to testing for a finite family of finite forbiddensubgraphs. While our presentation focuses on planar graphs, our approachextends easily to general minor-free graphs.  Our analysis of the necessary condition relies on a recent construction ofcanonical testers in the random neighbor oracle model that is applied here tothe one-sided error model for testing in planar graphs. The sufficientcondition in the characterization reduces the problem to the task of testing$H$-freeness in planar graphs, and is the main and most challenging technicalcontribution of the paper: we show that for planar graphs (with arbitrarydegrees), the property of being $H$-free is testable with one-sided error forevery finite graph $H$, in the random neighbor oracle model.

A characterization of graph properties testable for general planar graphs with one-sided error (It is all about forbidden subgraphs)