First-Order Logic and Twin-Width for Some Geometric Graphs

Colin Geniet, Gunwoo Kim, Lucas Meijer

For some geometric graph classes, tractability of testing first-order formulas is precisely characterised by the graph parameter twin-width. This was first proved for interval grap…