{
  "id": "1803.01931",
  "version": "v1",
  "published": "2018-03-05T21:22:10.000Z",
  "updated": "2018-03-05T21:22:10.000Z",
  "title": "Structure and generation of crossing-critical graphs",
  "authors": [
    "Zdeněk Dvořák",
    "Petr Hliněný",
    "Bojan Mohar"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For c=1 there are only two such graphs without degree-2 vertices, K_5 and K_3,3, but for any fixed c>1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow \"bands\" or \"fans\" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-03-05T21:22:10.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "generation",
      "bounded path-width",
      "study c-crossing-critical graphs",
      "polynomial time",
      "internally disjoint paths"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}