Twin-width and Limits of Tractability of FO Model Checking on Geometric Graphs

Petr Hliněný, Filip Pokrývka

The complexity of the problem of deciding properties expressible in FO logic on graphs -- the FO model checking problem (parameterized by the respective FO formula), is well-unders…