Every minor-closed property of sparse graphs is testable

DOI10.1016/J.AIM.2009.10.018zbMATH Open1223.05291arXiv0801.2797OpenAlexW2569976290MaRDI QIDQ962147FDOQ962147

Itai Benjamini, Oded Schramm, Asaf Shapira

Publication date: 6 April 2010

Published in: Advances in Mathematics (Search for Journal in Brave)

Abstract: Suppose $G$ is a graph with degrees bounded by $d$, and one needs to remove more than $epsilonn$ of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around vertices of $G$ is far from the statistics of local neighborhoods around vertices of any planar graph $G^{\prime }$ with the same degree bound. In fact, a similar result is proved for any minor-closed property of bounded degree graphs. As an immediate corollary of the above result we infer that many well studied graph properties, like being planar, outer-planar, series-parallel, bounded genus, bounded tree-width and several others, are testable with a constant number of queries, where the constant may depend on $epsilon$ and $d$, but not on the graph size. None of these properties was previously known to be testable even with $o(n)$ queries.

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

zbMATH Keywords

sparse graphsproperty testingminor closedhyper finite

Mathematics Subject Classification ID

Graph minors (05C83)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Applications of a Planar Separator Theorem
• Graph minors. XX: Wagner's conjecture
• The extremal function for complete minors
• Property testing and its connection to learning and approximation
• An extremal function for contractions of graphs
• Efficient Planarity Testing
• Property testing in bounded degree graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• Self-testing/correcting with applications to numerical problems
• A Separator Theorem for Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Graph minor theory
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• A sublinear bipartiteness tester for bounded degree graphs
• Graph limits and parameter testing
• Testing the expansion of a graph
• Testing the diameter of graphs
• SOFSEM 2005: Theory and Practice of Computer Science
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• On Testing Expansion in Bounded-Degree Graphs
• Local Graph Partitions for Approximation and Testing
• An Expansion Tester for Bounded Degree Graphs
• Hyperfinite graph limits
• The combinatoral cost
• Parameter testing in bounded degree graphs of subexponential growth
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs

Cited In (18)

• Title not available (Why is that?)
• Planarity can be verified by an approximate proof labeling scheme in constant-time
• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• Finite graphs and amenability
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• An analytic approach to stability
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• On the tree-width of even-hole-free graphs
• Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
• Edge Correlations in Random Regular Hypergraphs and Applications to Subgraph Testing
• Faster Property Testers in a Variation of the Bounded Degree Model
• Local 2-separators
• Title not available (Why is that?)
• Testing outerplanarity of bounded degree graphs
• Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
• Planar graphs: Random walks and bipartiteness testing
• Hyperfinite graphings and combinatorial optimization
• Limits of locally-globally convergent graph sequences

This page was built for publication: Every minor-closed property of sparse graphs is testable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q962147)