Abstract:
The notion of structural sparsity is discussed, and its relation to the ‘nowhere dense/somewhere dense’ dichotomy introduced by the authors for classes of graphs is examined. The numerous facets of this dichotomy are surveyed, along with its connections to several concepts like stability, independence, VC-dimension, regularity partitions, entropy, class speed, low tree-depth decomposition, quasi-wideness, neighbourhood covering, subgraph statistics, and so on, as well as algorithmic complexity issues like fixed-parameter tractability of first-order model checking.
Bibliography: 78 titles.
Fulltext:
PDF file (1344 kB)
