{
  "id": "1706.08581",
  "version": "v1",
  "published": "2017-06-26T20:15:26.000Z",
  "updated": "2017-06-26T20:15:26.000Z",
  "title": "Treewidth Bounds for Planar Graphs Using Three-Sided Brambles",
  "authors": [
    "Karen L. Collins",
    "Brett C. Smith"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Square grids play a pivotal role in Robertson and Seymour's work on graph minors as planar obstructions to small treewidth. We introduce a three-sided bramble in a plane graph called a net, which generalizes the standard bramble of crosses in a square grid. We then characterize any minimal cover of a net as a tree drawn in the plane. We use nets in an $O(n^3)$ time algorithm that computes both upper and lower bounds on the bramble number (hence treewidth) of any planar graph. Let $G$ be a planar graph, $BN(G)$ be its bramble number and $\\lambda(G)$ be the largest order of any net in a subgraph of $G$. Our algorithm outputs a constant, $KB$, so that $\\lambda(G)/4 \\leq KB \\leq BN(G)\\leq 4KB \\leq 4\\lambda(G)$. Let $s(G)$ be the size of a side of the largest square grid minor of $G$. Smith (2015) has shown that $\\lambda(G) \\geq s(G)$. Our upper bound improves that of Grigoriev (2011) when $\\lambda(G)\\leq (5/4)s(G)$. We correct a lower bound of Bodlaender, Grigoriev and Koster (2008) to $s(G)/5$ (instead of $s(G)/4$) and thus the lower bound of $\\lambda(G)/4$ on our approximation is an improvement.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-26T20:15:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "05C83",
      "05C85"
    ],
    "keywords": [
      "planar graph",
      "treewidth bounds",
      "three-sided bramble",
      "lower bound",
      "largest square grid minor"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}