Cops and Robbers for Graphs on Surfaces with Crossings

Prosenjit Bose, Pat Morin, Karthik Murali · 2025

Read Cops and Robbers for Graphs on Surfaces with Crossings by Prosenjit Bose, Pat Morin, Karthik Murali (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-13813.txt.

Introduction

Prosenjit Bose and co-authors play cops and robbers on graphs drawn with crossings in this 2025 paper. In the game, cops move along edges to catch a robber on a vertex. The cop number is the smallest crew that always wins. Graphs drawn cleanly on bounded-genus surfaces need only bounded crews.

Graphs that allow one crossing per edge break that rule entirely. The paper asks whether the distance between crossing edges restores order. In a variant where a cop within a few steps counts as a catch, bounded numbers return when crossing pairs sit close together. The authors cover several drawing classes and link crossing geometry to pursuit power.

Catalog record

CREATORProsenjit Bose, Pat Morin, Karthik Murali
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-13813

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cops and Robbers for Graphs on Surfaces with Crossings Prosenjit Bose, Pat Morin, Karthik Murali Abstract Cops and Robbers is a game played on a graph where a set of cops attempt to capture a single robber. The game proceeds in rounds, where each round first consists of the cops’ turn, followed by the robber’s turn. In the first round, the cops place themselves on a subset of vertices, after which the robber chooses a vertex to place himself. From the next round onwards, in the cops’ turn, every cop can choose to either stay on the same vertex or move to an adjacent vertex, and likewise the robber in his turn. The robber is considered to be captured if, at any point in time, there is some cop on the same vertex as the robber. The cops win if they can capture the robber within a finite number of rounds; else the robber wins. A natural question in this game concerns the cop-number of a graph—the minimum number of cops needed to capture a robber. It has long been known that graphs embeddable (without crossings) on surfaces of bounded genus have bounded cop-number. In contrast, it was shown recently that the class of 1-planar graphs—graphs that can be drawn on the plane with at most one crossing per edge—does not have bounded cop-number. This paper initiates an investigation into how the distance between crossing pairs of edges influences a graph’s cop number. In particular, we look at Distance d d Cops and Robbers , a variant of the classical game, where the robber is considered to be captured if there is a cop within distance d d of the robber. Let c d ​ ( G ) c_{d}(G) denote the minimum number of cops required in the graph G G to capture a robber within distance d d . We look at various classes of graphs, such as 1-plane graphs, k k -plane graphs (graphs where each edge is crossed at most k k times), and even general graph drawings, and show that if every crossing pair of edges can be connected by a path of small length, then c d ​ ( G ) c_{d}(G) is bounded, for small values of d d . For example, we show that if a graph G G admits a drawing in which every pair of crossing edges is contained in a path of length 3, then c 4 ​ ( G ) ≤ 21 c_{4}(G)\leq 21 . And if the drawing permits a stronger assumption that the endpoints of every crossing induce the complete graph K 4 K_{4} , then c 3 ​ ( G ) ≤ 9 c_{3}(G)\leq 9 . The tools and techniques that we develop in this paper are sufficiently general, enabling us to examine graphs drawn not only on the sphere but also on orientable and non-orientable surfaces. School of Computer Science, Carleton University, Ottawa, [email protected]://orcid.org/0000-0002-8906-0573 School of Computer Science, Carleton University, Ottawa, [email protected]://orcid.org/0000-0003-0471-4118 School of Computer Science, Carleton University, Ottawa, [email protected]://orcid.org/0009-0003-3985-3609 ccs Discrete mathematics Graph theory keywords Cops and Robbers, Crossings, 1-Planar, Surfaces † † runningauthor: P. Bose, P. Morin and K. Murali † † copyright: Prosenjit Bose, Pat Morin and Karthik Murali † † funding: Research supported in part by NSERC. 1 Introduction Pursuit-evasion is a general mathematical framework for problems that involve a set of pursuers attempting to capture a set of evaders . Such problems have many applications in robotics [ 20 ] , network security [ 15 ] , surveillance [ 9 ] , etc. The game of Cops and Robbers , introduced independently by Quilliot [ 30 ] , and Nowakowski and Winkler [ 28 ] , belongs to the family of pursuit-evasion problems where a set of cops (the pursuers) attempt to capture a single robber (the evader) on a graph. The game is played in rounds, with each round consisting first of the cops’ turn , followed by the robber’s turn . Initially, the cops first position themselves on a set of vertices, after which the robber chooses a vertex to place himself. In subsequent rounds, the cops’ turn consists of each cop either staying on the same vertex or moving to a neighbouring vertex, and likewise the robber in his turn. The game ends when the robber is captured by a cop; this happens when the robber is on the same vertex as some cop. If the robber has a strategy to permanently evade the cops, then the robber wins; else the cops win. (See the book [ 14 ] by Bonato and Nowakowski for an extensive introduction to Cops and Robbers.) One of the central questions in Cops and Robbers is to identify graph classes that require few cops to capture the robber. Formally, the cop-number of a graph G , denoted by c(G) , is defined as the minimum number of cops required to capture the robber. A graph class \mathcal{G} is said to be cop-bounded if c(G)\leq p for some integer p and all graphs G\in\mathcal{G} ; else \mathcal{G} is cop-unbounded . Many graph classes are known to be cop-bounded; for example, chordal graphs [ 28 , 30 ] , planar graphs [ 1 ] , graphs of bounded genus [ 31 ] , H -minor-free graphs [ 3 ] and H -(subgraph)-free graphs [ 26 ] . On the other hand, examples of graph classes that are cop-unbounded include bipartite graphs [ 14 ] , d -regular graphs, for all d\geq 3 [ 2 ] , 1-planar graphs [ 22 ] , and graphs of diameter 2 [ 12 ] . One of the deepest open problems on cop-number is Meyniel’s conjecture which states that c(G)\in O(\sqrt{n}) for all n -vertex graphs G (see [ 4 ] for a survey paper on Meyniel’s conjecture). 1.1 Survey of Related Results. In this paper, we are interested in the cop-number of graphs drawn on (orientable and non-orientable) surfaces with crossings. Most results in this area are concerned with cop-number of graphs embedded without crossings on surfaces with genus g . For planar graphs, which are graphs embeddable on the sphere ( g=0 ), Aigner and Fromme [ 1 ] proved that 3 cops are sufficient, and sometimes necessary. For graphs with (orientable) genus g>0 , the best known bound on the cop-number is \frac{4}{3}g+\frac{10}{3} [ 17 ] . A long-standing conjecture by Schroeder [ 32 ] is that c(G)\leq g+3 for all values of g . For non-orientable surfaces of genus g , Andreae [ 3 ] gave the first result that c(G)\in O(g) , which was later improved by Nowakowski and Schröder (in an unpublished work [ 29 ] ) to c(G)\leq 2g+1 . The current best result is by Clarke et al. [ 21 ] who show that c(G) is at most the maximum of all cop-numbers of graphs embeddable on an orientable surface of genus g-1 . (Refer to [ 13 ] for a survey of results, conjectures and open problems for cop-numbers of graphs on surfaces.) Ever since the appearance of the proof that c(G)\leq 3 for planar graphs [ 1 ] , it has been known that the geometrical representation of

Read the complete text