{
  "id": "1108.5635",
  "version": "v1",
  "published": "2011-08-29T16:26:54.000Z",
  "updated": "2011-08-29T16:26:54.000Z",
  "title": "Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions",
  "authors": [
    "Abhijin Adiga",
    "L. Sunil Chandran"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes just touch at their boundaries. Further, this construction can be realized in linear time.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-08-29T16:26:54.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "intersection graph",
      "axis-parallel boxes",
      "cubic graph",
      "dimensions",
      "axis parallel boxes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1108.5635A"
    }
  }
}