We study versions of cop and robber pursuit-evasion games on the visibility graphs of polygons, and inside polygons with straight and curved sides. Each player has full information about the other player's location, players take turns, and the robber is captured when the cop arrives at the same point as the robber. In visibility graphs we show the cop can always win because visibility graphs are dismantlable, which is interesting as one of the few results relating visibility graphs to other known graph classes. We extend this to show that the cop wins games in which players move along straight line segments inside any polygon and, more generally, inside any simply connected planar region with a reasonable boundary. Essentially, our problem is a type of pursuit-evasion using the link metric rather than the Euclidean metric, and our result provides an interesting class of infinite cop-win graphs.
We give an algorithmic characterisation of finite cop-win digraphs. The case of k>1 cops and k>=l>=1 robbers is then reduced to the one cop case. Similar characterisations are also possible in many situations where the movements of the cops and or the robbers are somehow restricted. We consider the game of Cops and Robbers played on finite and countably infinite connected graphs. The length of games is considered on cop-win graphs, leading to a new parameter, the capture time of a graph. While the capture time of a cop-win graph on n vertices is bounded above by n-3, half the number of vertices is sufficient for a large class of graphs including chordal graphs. Examples are given of cop-win graphs which have unique corners and have capture time within a small additive constant of the number of vertices. We consider the ratio of the capture time to the number of vertices, and extend this notion of capture time density to infinite graphs. For the infinite random graph, the capture time density can be any real number in [0,1]. We also consider the capture time when more than one cop is required to win. While the capture time can be calculated by a polynomial algorithm if the number k of cops is fixed, it is NP-complete to decide whether k cops can capture the robber in no more than t moves for every fixed t.