Now showing1 - 1 of 1
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Twin-width VIIIa: Delineation(Elsevier, 2026-07-31); ; ; ; 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.Publicationtype: Journal Article34 7