Answers are grounded in this paper and cite their sources.
We introduce the notion of delineation. A graph class C is said delineated by twin-width (or simply, delineated ) if for every hereditary closure D of a subclass of C, it holds that D has bounded twin-width if and only if D is monadically dependent. An effective strengthening of delineation for a class C implies that tractable FO model checking on C is perfectly understood: On hereditary closures D of subclasses of C, FO model checking is fixed-parameter tractable (FPT) exactly when D has bounded twin-width. Ordered graphs [BGOdMSTT, STOC ’22], permutation graphs [BKTW, JACM ’22] and tournaments [GT, European Journal of Combinatorics ’25] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, directed path graphs with boundedly many roots are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated.
No takes yet. Share an insight, caveat, or question.
Bonnet et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: