Deciding first-order properties for sparse graphs

Abstract

We show that every FOL property can be tested in linear time for graphs with bounded expansion.

Keywords

• FOL properties
• graphs with bounded expansion
• algorithmic metatheorems