HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Fast Robber in Planar Graphs

Nicolas Nisse 1 Karol Suchan 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In the {\it cops and robber game}, two players play alternately by moving their tokens along the edges of a graph. The first one plays with the {\it cops} and the second one with one {\it robber}. The cops aim at capturing the robber, while the robber tries to infinitely evade the cops. The main problem consists in minimizing the number of cops used to capture the robber in a graph. This minimum number is called the {\it cop-number} of the graph. If the cops and the robber have the same velocity, $3+\frac{3}{2}g$ cops are sufficient to capture one robber in any graph with genus $g$ (Schröder, 2001). In the particular case of a grid, $2$ cops are sufficient. %In this paper, w We investigate the game in which the robber is slightly faster than the cops. In this setting, we prove that the cop-number of planar graphs becomes unbounded. More precisely, we prove that $\Omega(\sqrt{\log n})$ cops are necessary to capture a fast robber in the $n \times n$ square-grid. This proof consists in designing an elegant evasion-strategy for the robber. Then, it is interesting to ask whether a high value of the cop-number of a planar graph $H$ is related to a large grid $G$ somehow contained in $H$. We prove that it is not the case when the notion of containment is related to the classical transformations of edge removal, vertex removal, and edge contraction. For instance, we prove that there are graphs with cop-number at most $2$ and that are subdivisions of arbitrary large grid. On the positive side, we prove that, if $H$ planar contains a large grid as an induced subgraph, then $H$ has large cop-number. Note that, generally, the cop-number of a graph $H$ is not closed by taking induced subgraphs $G$, even if $H$ is planar and $G$ is an distance-hereditary induced-subgraph.
Document type :
Conference papers
Complete list of metadata

Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Saturday, October 10, 2009 - 1:44:06 PM
Last modification on : Friday, February 4, 2022 - 3:19:21 AM


  • HAL Id : inria-00423451, version 1


Nicolas Nisse, Karol Suchan. Fast Robber in Planar Graphs. International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2008, Durham, United Kingdom. ⟨inria-00423451⟩



Record views