Twin-width I: Tractable FO Model Checking

Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA’14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, K t -free unit d -dimensional ball graphs, posets with antichains of bounded siz...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2022-02, Vol.69 (1), p.1-46
Main Authors: Bonnet, Édouard, Kim, Eun Jung, Thomassé, Stéphan, Watrigant, Rémi
Format: Article
Language:English
Subjects:
Algorithms
Computer Science
Graphs
Mathematics
Permutations
Polynomials
Set theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!