{
  "id": "1709.05904",
  "version": "v1",
  "published": "2017-09-18T13:03:29.000Z",
  "updated": "2017-09-18T13:03:29.000Z",
  "title": "Localization game on geometric and planar graphs",
  "authors": [
    "Bartłomiej Bosek",
    "Przemysław Gordinowicz",
    "Jarosław Grytczuk",
    "Nicolas Nisse",
    "Joanna Sokół",
    "Małgorzata Śleszyńska-Nowak"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "The main topic of this paper is motivated by a localization problem in cellular networks. Given a graph $G$ we want to localize a walking agent by checking his distance to as few vertices as possible. The model we introduce is based on a pursuit graph game that resembles the famous Cops and Robbers game. It can be considered as a game theoretic variant of the \\emph{metric dimension} of a graph. We provide upper bounds on the related graph invariant $\\zeta (G)$, defined as the least number of cops needed to localize the robber on a graph $G$, for several classes of graphs (trees, bipartite graphs, etc). Our main result is that, surprisingly, there exists planar graphs of treewidth $2$ and unbounded $\\zeta (G)$. On a positive side, we prove that $\\zeta (G)$ is bounded by the pathwidth of $G$. We then show that the algorithmic problem of determining $\\zeta (G)$ is NP-hard in graphs with diameter at most $2$. Finally, we show that at most one cop can approximate (arbitrary close) the location of the robber in the Euclidean plane.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-09-18T13:03:29.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C57"
    ],
    "keywords": [
      "planar graphs",
      "localization game",
      "game theoretic variant",
      "pursuit graph game",
      "main topic"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}