{
  "id": "0910.3014",
  "version": "v1",
  "published": "2009-10-16T01:26:38.000Z",
  "updated": "2009-10-16T01:26:38.000Z",
  "title": "Bandwidth, expansion, treewidth, separators, and universality for bounded degree graphs",
  "authors": [
    "Julia Böttcher",
    "Klaas P. Pruessmann",
    "Anusch Taraz",
    "Andreas Würfl"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We establish relations between the bandwidth and the treewidth of bounded degree graphs G, and relate these parameters to the size of a separator of G as well as the size of an expanding subgraph of G. Our results imply that if one of these parameters is sublinear in the number of vertices of G then so are all the others. This implies for example that graphs of fixed genus have sublinear bandwidth or, more generally, a corresponding result for graphs with any fixed forbidden minor. As a consequence we establish a simple criterion for universality for such classes of graphs and show for example that for each gamma>0 every n-vertex graph with minimum degree ((3/4)+gamma)n contains a copy of every bounded-degree planar graph on n vertices if n is sufficiently large.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-10-16T01:26:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bounded degree graphs",
      "universality",
      "bounded-degree planar graph",
      "parameters",
      "minimum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0910.3014B"
    }
  }
}