2014 · 81 citations · 25 references
Natural SciencesComputer ScienceMathematicsCombinatoricsComputational GeometryDiscrete MathematicsGraph AlgorithmsGraph TheoryComplexity-theoretic HardnessComplexity-theoretic ReductionsComputational Complexity Of Graph AlgorithmsExpansion In GraphsFirst-order Logic ReasoningGraph MinorsPlanar Graphs
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.
25