Deciding first-order properties of nowhere dense graphs

2014/05/31 by Martin Grohe, Stephan Kreutzer, Sebastian Siebertz · 7 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory

paper · doi:10.1145/2591796.2591851

openalex publication_date 2014/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

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.

Citations

• Domination Problems in Nowhere-Dense Classes of Graphs
• Deciding first-order properties of nowhere dense graphs
• Sparsity

Cited by

• Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
• FO Value Discovery and Partial Vertex Cover Discovery
• Variants of Merge-Width and Applications
• FO and MSO Model Checking on Temporal Graphs
• Solving Partial Dominating Set and Related Problems Using Twin-Width
• Complexity of Token Swapping and Its Variants
• Logic of graphs [wikipedia]

Related

• Deciding first-order properties of nowhere dense graphs
• Nowhere dense graph classes and algorithmic applications. A tutorial at Highlights of Logic, Games and Automata 2019
• Directed Nowhere Dense Classes of Graphs
• Nowhere Dense Graph Classes and Dimension
• Testing first-order properties for subclasses of sparse graphs