Cops and Robbers for Graphs on Surfaces with Crossings

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}$ [18]. A long-standing conjecture by Schroeder [31] is that $c(G)\le 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 [28]) to $c(G)\le 2g+1$. The current best result is by Clarke et al. [22] 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)\le 3$ for planar graphs [1], it has been known that the geometrical representation of a graph plays an important role in bounding its cop-number. For instance, the strategy for guarding planar graphs was adapted to show that $c(G)\le 9$ for unit disk graphs [8], and $c(G)\le 15$ for string graphs [24]. More recently, the study of cop-numbers for the beyond-planar graph classes was initiated by Durocher et al. [23]. They show that unlike planar graphs, the class of 1-planar graphs – which allow for one crossing per edge – is cop-unbounded. On the positive side, they show 3 cops are sufficient, and sometimes necessary, for a maximal 1-planar graph: a 1-planar graph to which no edge can be added without violating 1-planarity (while staying simple). To prove this, they crucially use the fact that the endpoints of every crossing induce the complete graph $K_4$. In a recent paper, Bose et al. [16] showed that even under the relaxed requirement that no crossing of a 1-plane graph is an $\times$-crossing – a crossing whose endpoints induce a matching – the cop-number remains bounded, and is at most 21. As a corollary, their result implies that 1-planar graphs with large cop-numbers necessarily embed with a large number of $\times$-crossings.

Motivated by [16], we undertake a comprehensive study of how the distance between crossing pairs of edges affects the cop number of graphs. Unlike [16], our aim is to go beyond 1-planar graphs, and look at general graphs drawn on surfaces, under the restriction that every crossing pair of edges can be connected by a path of small length. (A similar approach was undertaken in [10] to generalise results on vertex connectivity from 1-plane graphs without $\times$-crossings to arbitrary graphs drawn on the sphere.) We consider two notions of distance between crossing pairs of edges. For any pair of edges $\{e_1,e_2\}$ that cross in $G$, we say that two endpoints of the crossing are consecutive if one endpoint is a vertex incident with $e_1$ and the other is a vertex incident with $e_2$. For any fixed drawing of a graph $G$ on a surface, let $x(G)$ (resp. $X(G)$) be the smallest integer such that for every crossing in the drawing, there is a path of length at most $x(G)$ (resp. $X(G)$) connecting some (resp. every) pair of consecutive endpoints of the crossing. By the definition above, $x(G)\le X(G)$; furthermore, $X(G)\le x(G)+2$ since there exists a path of length at most $x(G)+2$ at every crossing where the first and last edges of the path are precisely the crossing pair of edges. Notwithstanding the tight relation between $X(G)$ and $x(G)$, we differentiate between the two parameters to capture their varying impact on cop-number. Indeed, one may already notice this for 1-plane graphs. If $G$ is a maximal 1-plane graph, where the endpoints of every crossing induce a $K_4$, we have $X(G)=1$ and $c(G)\le 3$ [23]. On the other hand, if $G$ is a 1-plane graph without $\times$-crossings, we have $x(G)=1$ and $c(G)\le 21$ [16].

Most results that we present in this paper concern Distance $d$ Cops and Robbers – a variant of the classical Cops and Robbers in which the robber is considered to be captured if, at any point in time, there is a cop within distance $d$ of the robber [12]. We use the notation $c_d(G)$ to denote the minimum number of cops required to capture the robber within distance $d$ in the graph $G$. In this paper, we give several interesting results on distance $d$ cop-numbers of graphs $G$, where $d$ is parameterised by $X(G)$ and $x(G)$. We restrict our discussion here only to graphs drawn on the sphere, even though they extend to graphs drawn on surfaces with crossings. Our results not only encompass and improve the existing results on 1-plane graphs [23, 16], but also greatly simplify the existing proofs. The tools that we develop in this paper are equipped to handle beyond 1-planar graphs, such as $k$-plane graphs (where each edge is allowed to cross at most $k$ times), and even arbitrary graphs on surfaces.

We use Theorems 3.3 and 3.4 to define two simple operations for graphs drawn on surfaces, both of which are foundational to this paper. The two operations, called $(\mathrm{\Sigma },1)$-planarisation and kite-augmentation, are described below.

Every graph $G$ drawn on a surface $\mathrm{\Sigma }$ has a $(\mathrm{\Sigma },1)$-planarisation: set $k$ equal to the minimum integer such that every edge is crossed at most $k$ times, and place $(k-1)$ subdivision vertices on each edge around crossing points so that $G^{(k)}$ is $(\mathrm{\Sigma },1)$-planar. Note that $(\mathrm{\Sigma },1)$-planarisation of a graph is not unique, since subdivisions of $(\mathrm{\Sigma },1)$-plane graphs are also $(\mathrm{\Sigma },1)$-plane. When $\mathrm{\Sigma }$ is a sphere, then the resulting graph is 1-plane; in this case we simply write 1-planarisation instead of $(\mathrm{\Sigma },1)$-planarisation. In [23], the process of 1-planarisation was used to prove that 1-planar graphs are cop-unbounded. Briefly, notice that by Theorem 3.4, if $G^{(k)}$ is a 1-planarisation of $G$, then $c(G)\le c(G^{(k)})\le c(G)+1$. Since every graph $G$ has a 1-planarisation $H$, and the universal set of graphs is cop-unbounded, so is the set of all 1-planar graphs.

Recall from Section 2 that a kite edge at a crossing of a $(\mathrm{\Sigma },1)$-plane graph is an uncrossed edge connecting two consecutive endpoints of a crossing such that the edge bounds a face incident to the crossing point. In this paper, we shall see that the presence of kite edges, or paths of uncrossed edges connecting consecutive endpoints of crossings, are especially useful to bound cop-numbers of 1-planar graphs. To this end, we introduce a class of $(\mathrm{\Sigma },1)$-planar drawings on surfaces called kite-augmented $(\mathrm{\Sigma },1)$-planar drawings.

The above definition lends itself to a procedure called kite-augmentation, defined below.

For any graph $G$ drawn on a surface $\mathrm{\Sigma }$, we use the notation $G^{⊠}$ to denote a graph obtained by $(\mathrm{\Sigma },1)$-planarising $G$ and then kite-augmenting the resulting graph (see Figure 1 for an example). If $G^{(k)}$ is a $(\mathrm{\Sigma },1)$-plane graph, and $G^{⊠}$ is obtained by kite-augmenting $G^{(k)}$, then $G^{(k)}$ is a retract of $G^{⊠}$ since there is a homomorphism from each path ${\kappa }_{uv}$ to a shortest $(u,v)$-path in $G^{(k)}$. This observation, together with Theorems 3.3 and 3.4 gives us the following corollary.

Our study of distance $d$ Cops and Robbers for graphs drawn on surfaces focuses primarily on those values of $d$ that in some way capture how close crossing pairs of edges are in the drawing. To this end, we define two parameters $X(G)$ and $x(G)$:

These two parameters are closely related to a structure called ribbon associated with crossings (first defined in [10]): For any crossing pair of edges $e_1$ and $e_2$, a ribbon at the crossing is a path with $e_1$ as the first edge and $e_2$ as the last edge. Every crossing in a graph has a ribbon of length at most $x(G)+2$. Since any pair of consecutive endpoints of a crossing can be connected by a sub-path of a ribbon at the crossing, $X(G)\le x(G)+2$. Therefore, $X(G)\in \{x(G),x(G)+1,x(G)+2\}$. Our intention in differentiating between $x(G)$ and $X(G)$ is to capture the differences arising in cop-numbers due to variations in crossing configurations. For instance, in a maximal 1-planar graph $G$ where the endpoints of every crossing induce $K_4$, we have $x(G)=X(G)=1$, and $c(G)=3$ [23]. However, in a 1-planar graph without $\times$-crossings where the endpoints induce at least 3 edges, we have $x(G)=1$ (and $X(G)\le 3$), and $c(G)\le 21$ [16].

In Lemma 3.11 (proof in full-version [17]), we give useful bounds on $X(G^{(k)})$ and $x(G^{(k)})$ in terms of the corresponding parameters for $G$. These will be used in Theorem 3.12, and in later sections of the paper.

In Theorem 3.12 (proof in full-version [17]), we give a relation between distance $d$ cop-numbers of $G$ and $G^{⊠}$, where $d$ is measured through the parameters $x(G)$ and $X(G)$.

The choice of which shortest path or cycle to guard is made by selecting two vertices, say $s$ and $t$, and then finding a shortest $(s,t)$-path through the unguarded subgraph. Since we require that such a shortest path include at least one vertex from the unguarded subgraph, it may be necessary to exclude the edge $(s,t)$ when both $s$ and $t$ are already guarded and adjacent in $G$. In light of this, we find it convenient to view an unguarded subgraph as an $(s,t)$-subgraph, defined as follows. (For Definition 4.2, recall the notation ${\kappa }_{ab}$ from Definition 3.7 for the path resulting from repeated subdivision of kite-edges.)

In Lemma 4.3, we show that there always exists a shortest $(s,t)$-path in an $(s,t)$-subgraph such that no two edges of the shortest path cross each other. For brevity, we say that a subgraph $H$ of $G$ is self-crossing if there exist a pair of edges of $H$ that cross each other; otherwise, $H$ is non-self-crossing.

We now use Lemma 4.5 on guarding shortest paths to prove Theorem 4.1. For this, we use ideas from [14] for the proof that planar graphs have cop-number at most 3, and from [16] for the modifications needed to handle crossings in 1-planar graphs. We first give an overview of the proof, and then provide a formal description in detail in Lemma 4.6.

We consider three sets of $2\beta +1$ cops, and proceed in iterations, where every iteration begins with a path or a cycle being crossing-guarded at distance $\lceil \alpha d\rceil -1$. (For the rest of this discussion, we use the term “guard” as a shortcut to saying “crossing-guard at distance $\lceil \alpha d\rceil -1$”.) We ensure that the paths and cycles are non-self-crossing, so that they trace simple paths and simple cycles on the sphere. These paths and cycles serve as the frontiers between the guarded subgraph and the unguarded subgraph of $G$, and these are the only subgraphs that are actively guarded at any point in time. A path requires only one set of cops to guard, and a cycle requires two sets of cops; hence at least one of three sets of cops is free at the beginning of every iteration.

Every iteration begins by choosing a shortest path to be guarded by the free set of cops. For this, two special vertices $s$ and $t$ are identified that have a neighbour in the robber territory – the maximal subgraph of $G$ within which the robber can move without getting captured. Then, we consider the $(s,t)$-subgraph formed by the union of the robber territory together with the set of all edges connecting $\{s,t\}$ and the robber territory. Now, we guard a shortest non-self-crossing $(s,t)$-path in the $(s,t)$-subgraph identified above. This path may be the only path actively guarded, or may be combined with a previously guarded path to form a new cycle to be actively guarded (Figure 2). Once the path has been guarded, the current iteration ends, at least one set of cops is freed, and the next iteration begins. At the end of every iteration, we shall maintain the invariant that the shortest $(s,t)$-path chosen to be guarded contains at least one vertex of the robber territory. Therefore, every iteration ends with at least one more vertex of the graph being guarded, and after a finite number of iterations, the robber is captured.

We now give a detailed and formal treatment of the above overview in Lemma 4.6 (proof in full-version [17]).

Lemmas 4.5 and 4.6 together establish Theorem 4.1.

In this section, we discuss the implications of Theorem 4.1 for 1-plane graphs, $k$-plane graphs and general graphs drawn on the sphere. A summary of the results in this section appears in Table 1. To keep notation compact, we let $c_{f(X)}(G)$ and $c_{f(x)}(G)$ be shortcuts to $c_{f(X(G))}(G)$ and $c_{f(x(G))}(G)$, respectively.