{
  "id": "1610.04741",
  "version": "v1",
  "published": "2016-10-15T14:19:29.000Z",
  "updated": "2016-10-15T14:19:29.000Z",
  "title": "Drawing graphs using a small number of obstacles",
  "authors": [
    "Martin Balko",
    "Josef Cibulka",
    "Pavel Valtr"
  ],
  "comment": "17 pages, 12 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "An obstacle representation of a graph $G$ is a set of points in the plane representing the vertices of $G$, together with a set of polygonal obstacles such that two vertices of $G$ are connected by an edge in $G$ if and only if the line segment between the corresponding points avoids all the obstacles. The obstacle number ${\\rm obs}(G)$ of $G$ is the minimum number of obstacles in an obstacle representation of $G$. We provide the first non-trivial general upper bound on the obstacle number of graphs by showing that every $n$-vertex graph $G$ satisfies ${\\rm obs}(G) \\leq n\\lceil\\log{n}\\rceil-n+1$. This refutes a conjecture of Mukkamala, Pach, and P\\'alv\\\"olgyi. For $n$-vertex graphs with bounded chromatic number, we improve this bound to $O(n)$. Both bounds apply even when the obstacles are required to be convex. We also prove a lower bound $2^{\\Omega(hn)}$ on the number of $n$-vertex graphs with obstacle number at most $h$ for $h<n$ and an asymptotically matching lower bound $\\Omega(n^{4/3}M^{2/3})$ for the complexity of a collection of $M \\geq \\Omega(n\\log^{3/2}{n})$ faces in an arrangement of line segments with $n$ endpoints.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-10-15T14:19:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C62",
      "68R10"
    ],
    "keywords": [
      "small number",
      "drawing graphs",
      "vertex graph",
      "obstacle number",
      "first non-trivial general upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}