Deciding first-order properties of nowhere dense graphs

Martin Grohe, Stephan Kreutzer, Sebastian Siebertz

2014 · 81 citations · 25 references

Concepts

Abstract

Nowhere dense graph classes, introduced by Nešetřil and Ossona de Mendez [30], form a large variety of classes of "sparse graphs" including the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs and graph classes of bounded expansion.

References

25