{
  "id": "2501.04166",
  "version": "v1",
  "published": "2025-01-07T22:27:31.000Z",
  "updated": "2025-01-07T22:27:31.000Z",
  "title": "Graph classes through the lens of logic",
  "authors": [
    "Michał Pilipczuk"
  ],
  "comment": "Survey. 67 pages, 11 figures",
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.DS",
    "cs.LO"
  ],
  "abstract": "Graph transformations definable in logic can be described using the notion of transductions. By understanding transductions as a basic embedding mechanism, which captures the possibility of encoding one graph in another graph by means of logical formulas, we obtain a new perspective on the landscape of graph classes and of their properties. The aim of this survey is to give a comprehensive presentation of this angle on structural graph theory. We first give a logic-focused overview of classic graph-theoretic concepts, such as treedepth, shrubdepth, treewidth, cliquewidth, twin-width, bounded expansion, and nowhere denseness. Then, we present recent developments related to notions defined purely through transductions, such as monadic stability, monadic dependence, and classes of structurally sparse graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-01-07T22:27:31.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "graph classes",
      "classic graph-theoretic concepts",
      "structural graph theory",
      "transductions",
      "structurally sparse graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 67,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}