11institutetext: Dept. Computer Science, University of Manitoba, Winnipeg,
Manitoba, Canada
<EMAIL_ADDRESS>{liuf3412, mashghda, zamaninp,
<EMAIL_ADDRESS>22institutetext: Dept. Electrical Engineering and
Computer Science, York University, Toronto, Ontario, Canada
<EMAIL_ADDRESS>
# Cops and Robbers on 1-Planar Graphs††thanks: This research is funded in part
by the Natural Sciences and Engineering Research Council of Canada (NSERC).

Stephane Durocher 11 Shahin Kamali 22 Myroslav Kryven 11 0000-0003-4778-3703
Fengyi Liu 11 Amirhossein Mashghdoust 11 Avery Miller 11 Pouria Zamani Nezhad
11 Ikaro Penha Costa 11 Timothy Zapp 11

###### Abstract

_Cops and Robbers_ is a well-studied pursuit-evasion game in which a set of
cops seeks to catch a robber in a graph $G$, where cops and robber move along
edges of $G$. The _cop number_ of $G$ is the minimum number of cops that is
sufficient to catch the robber. Every planar graph has cop number at most
three, and there are planar graphs for which three cops are necessary [Aigner
and Fromme, DAM 1984]. We study the problem for _1-planar graphs_ , that is,
graphs that can be drawn in the plane with at most one crossing per edge. In
contrast to planar graphs, we show that some 1-planar graphs have unbounded
cop number. Meanwhile, for maximal 1-planar graphs, we prove that three cops
are always sufficient and sometimes necessary. In addition, we completely
determine the cop number of outer 1-planar graphs.

###### Keywords:

Beyond Planarity $1$-Planar Graphs Pursuit–Evasion Cops and Robbers

##  1 Introduction

_Pursuit–evasion_ is a family of problems (also called games) in which one
group seeks to capture members of another group in a given environment. There
are many variants of pursuit–evasion games, depending on the game environment,
information available to each player about the environment and other players,
and restrictions on the freedom or speed at which players can move.

One of the most common and well-studied pursuit-evasion problems is the game
of _Cops and Robbers_ on graphs, which was formalized by Quilliot [26] and
Nowakowski and Winkler [25] in the 1980s; see also the recent book by Bonato
and Nowakowski [6]. The game is played in a graph by two players: the robber
player and the cop player. The common assumption that we also adopt here is
that each player has full information about the graph and the other player’s
moves. The game consists of rounds (or steps) on a given graph. In the initial
round, the cop player selects starting vertices for a set of cops, and then
the robber player selects a starting vertex for a robber. In the subsequent
rounds, the players alternate turns; during the cops’ turn, the cop player may
move some of the cops to adjacent vertices. Similarly, the robber player may
move the robber to an adjacent vertex during the robber’s turn. The cop player
wins if the robber and any of the cops are simultaneously on the same vertex;
otherwise, when the game continues indefinitely, the robber player wins. If a
single cop suffices to catch the robber in a graph $G$, even when the robber
plays adversarially,color=cyan!10]is “adversarial” is the right word?, PZ: Do
you think we should use Optimally? SD: adversarially is more general than
optimally. Let’s keep adversarially. then $G$ is a _cop-win graph_ ;
otherwise, $G$ is a _robber-win graph_. The minimum number of cops necessary
to catch the robber in $G$, denoted $c(G)$, is called the _cop number_ of $G$,
and $G$ is a _$c(G)$ -cop win graph_.

#### Related work

Various characterizations of $c$-cop win graphs are known [11]. For example,
every cop-win graph has a _domination elimination ordering sequence_ [26]
(also known as _dismantling ordering_), i.e., an ordering of the vertices such
that, if the vertices are removed in this order, each vertex (except the last)
is dominated at the time it is removed. This characterization helped identify
classes of cop-win graphs, such as chordal graphs (as every elimination
ordering of a chordal graph is also a dismantling ordering) and visibility
graphs [22].

For some classes of graphs, a cop strategy comes directly from the graph’s
structural properties. For example, Aigner and Fromme [1] showed that every
planar graph has a cop number of at most three by implicitly using the Jordan
curve property, and, the fact that a cycle in a _plane graph_ (a graph drawn
in the plane without edge crossings) partitions the graph into interior and
exterior regions. Some classes of planar graphs have cop number two (e.g.,
series-parallel graphs [19] and outerplanar graphs). On the other hand, planar
graphs with cop number three are known, e.g., the _dodecahedron_ , which is
the skeleton of the platonic solid with faces of degree five. It is
conjectured that the dodecahedron is the smallest planar graph with cop number
three [1]. Maurer et al. [23] give an example of a _triangulation_ (i.e.,
maximal planar graph) with cop number three.

Aigner and Fromme [1] also asked whether the result concerning planar graphs
can be generalized to graphs of higher _orientable genus_ , which is the
minimum number of handles attached to a sphere so that the graph could be
drawn without crossings on the resulting surface. Shortly after, Quilliot [27]
gave an upper bound of $2g+3$ on the cop number of graphs of genus $g$.
Schröder [29] improved this bound to $1.5g+3$ and conjectured that there is a
tighter upper bound of $g+3$. The current best upper bound of approximately
$1.268g$ is due to Erde and Lehner [14]; find details in the survey of Bonato
and Mohar [8]. inline,color=cyan!10]Do “genus” and “orientable genus” refer to
the same thing? MK: the question as posed by Aigner and Fromme [1] was
concerning only drawings on orientable surfaces, by specifying “orientable
genus” we highlight that

Having established the cop number of planar graphs, a natural next question
concerns the cop number of graphs that are _almost planar_. Proximity to being
planar for a given graph $G$ can be parameterized by the minimum number of
crossings per edge among all drawings of $G$ in the plane, where a planar
graph requires zero crossings per edge. inline,color=cyan!10]Technically, you
minimum maximum number of crossing, where minimum is taken over all drawings
and max is taken over all edges. SD: True, but the sense comes across in the
current wording, and I don’t have a better way to express this concisely. In
recent years, there has been an increasing interest in the family of graphs
that generalize planar graphs, called _beyond-planar graphs_ , that is, graphs
that can be drawn with few crossings [18]. A common subclass of beyond-planar
graphs is $k$-_planar graphs_ , that is, graphs that can be drawn in the plane
with at most $k$ crossings per edge. Various properties of $k$-_planar graphs_
are known: their maximum edge density, relation to other families of beyond-
planar graphs, as well as the complexity of many algorithmic problems [12].
The special case of $1$-_planar graphs_ has been extensively studied, for
example, their maximum edge density is $4n-8$ [30], which is tight, and they
can be colored with at most seven colors [28]. Even though this might seem to
generalize planar graphs only slightly, in contrast to planar graphs,
determining whether a given graph is $1$-planar is NP-hard [17, 21]. Moreover,
their relation to other families of beyond-planar graphs is well understood
[4]. inline,color=cyan!10]We need to continue this paragraph with a summary of
results on 1-planar graphs. E.g., cite the existing results on their coloring
number and a few other results to highlight their siginificance. SD: Let’s
save this for the final version. MK: mentioned some more results (coloring,
edge density, and relation to other beyond-planar graphs) about 1-planar
graphs for motivation. In this paper we only consider _simple_ drawings, that
is, edges can cross at most once and adjacent edges do not cross.

#### Our results

The upper bound of Quilliot [27] on the cop number of graphs with bounded
genus was one of the first steps in the study of the Cops and Robbers game on
beyond-planar graphs. In this work, we extend this direction by studying
bounds on the cop number in another prominent family of beyond planar graphs:
$k$-planar graphs. Graphs of bounded genus and $k$-planar graphs are
unrelated; i.e., there are 1-planar graphs with arbitrary large genus, and
graphs that have genus one but require arbitrarily many crossings per edge to
be drawn in the plane [13]. We show in Section 2 that, despite the fact that
planar graphs have cop number at most three, 1-planar graphs may have
unbounded cop number; see Theorem 2.1. Constructing 1-planar graphs with large
cop number, as described in the proof of Theorem 2.1, results in sparse
1-planar graphs with many vertices of degree two. With this in mind, we
consider dense 1-planar graphs, particularly maximal 1-planar graphs, in
Section 4. A 1-planar graph is said to be _maximal_ if no edge can be added
such that the resulting graph remains 1-planar. Maximal 1-planar graphs with
$n$ vertices and the maximum number $4n-8$ of edges [31] are called _optimal
1-planar_. Maximal 1-planar graphs can have fewer than $4n-8$ edges, e.g.,
there exist maximal 1-planar graphs that have as few as $2.65n$ edges [9]. In
Section 3, we construct a _planar quadrangulation_ (a plane graph in which
each face has exactly four edges) with cop number three. Using this
quadrangulation, in Section 4.1, we show how to construct a maximal 1-planar
graph (which is also an optimal 1-planar graph) for which three cops are
necessary to catch a robber. In Section 4.2, we show that each maximal
1-planar graph has cop number at most three using the Jordan arc property, as
used by Aigner and Fromme [1], and structural properties of maximal 1-planar
graphs.

In Section 5, we consider _outer $k$-planar graphs_ [2, 10], where, in
addition to each edge being crossed at most $k$ times, we also restrict the
vertices to be in convex position on the outer boundary. The cop number of an
outer $k$-planar graph is bounded by $1.5k+6.5$ due to its relation to
treewidth [19] (if the treewidth of a graph is at most $t$, then its cop
number is at most $t/2+1$ [19]). This is an interesting contrast to general
$k$-planar graphs, which can have unbounded cop number. Finally, we examine
outer 1-planar graphs, which have cop number at most two due to the upper
bound via their treewidth, and characterize those that are cop-win.
inline,color=cyan!10]I suggest removing the discussion on k-outerplanar graphs
in the main paper and only mentioning that -along with the treewidth results-
in the conclusion section and a topic for future work.

inline,color=cyan!10]The paper can benefit from a table with a summary of all
results, including previous work (results on planar and bounded genus graphs)
along with our contributions on I) (general) 1-planar graphs II) maximal
outer-planar graphs III) outer 1-planar graphs IV) the trivial upper bound for
k-outerplanar graphs. We can link to the theorems in each case for better
navigation of the paper.

##  2 $1$-Planar Graphs May Have Unbounded Cop Number

In this section we show that there exist 1-planar graphs with unbounded cop
number.

###### Theorem 2.1

For every $c\in\mathbb{N}$, there exists a 1-planar graph with cop number at
least $c$.

###### Proof

For any $c$, there exists a graph $G$ with cop number $c$ [24, Theorem 2.6].
Choose a $k$-planar drawing of $G$ for some $k$. Define a graph $G^{\prime}$
that is obtained from $G$ by subdividing each edge $k-1$ times if $k$ is odd,
or $k$ times if $k$ is even; see Figure 1. Berarducci and Intrigila [5,
Theorem 5.6] showed that replacing each edge with the same odd-length path
does not decrease the cop number, so it follows that $c(G^{\prime})\geq c(G)$.
Also, $G^{\prime}$ is 1-planar as we can obtain a 1-planar drawing of
$G^{\prime}$ from the $k$-planar drawing of $G$: between every two consecutive
crossings on an edge in $G$, place one of the added subdivision vertices in
$G^{\prime}$. inline,color=cyan!10]Is it important to start from the drawing
with min crossing? if not, we do not emphasize on that. Also, should’nt we
subdivide each edge exactly k times? FL: we are trying to introduce as fewer
vertices as possible, original we want $c(G)=\theta(\sqrt{n})$
inline,color=cyan!10]I suggest adding a figure and moving the proof to in its
own section rather than the contribution section. ∎

Figure 1: Subdividing each edge an equal number of times does not reduce the
cop number of the resulting graph.

##  3 Cop Number of Quadrangulations

In this section, we study the cop number of _quadrangulations_ , that is,
plane graphs in which every face has exactly four edges and four vertices. A
graph $G$ can be drawn as a quadrangulation in the plane if and only if $G$ is
a maximal planar bipartite graph [20]. Since quadrangulations are planar, they
have cop number at most three [1]. We show that there exists a quadrangulation
$Q$ for which three cops are necessary; see Theorem 3.1. We will use this
result in Section 4 to prove that there are maximal 1-planar graphs with cop
number three. To construct our quadrangulation $Q$ we first construct a
triangulation $T$ [23] which is based on the dodecahedron graph $D$; see
Figure 2. The triangulation $T$ is constructed by adding vertices and edges to
each face of $D$ in such a way that each resulting face is a triangle; see
Figure 2(b). The original dodecahedron edges are in black and the new
triangulation edges are in dark green. We construct our quadrangulation $Q$ by
adding one vertex and three edges to each face of this triangulation in such a
way that each resulting face is a quadrangle; see Figure 2(b). The new
quadrangulation edges are in light green. After quadrangulating the
triangulation, we have subdivided the original edges of the dodecahedron once,
so the vertices of the dodecahedron that were initially adjacent are now at
distance two from each other. Let $V^{\prime}\subset V(Q)$ be the set of such
vertices of $Q$ that subdivide the original edges of the dodecahedron.

###### Theorem 3.1

The quadrangulation $Q$ has cop number three.

###### Proof

Because the quadrangulation $Q$ is a planar graph, its cop number is at most
three [1]. We will show that $Q$ has cop number at least three. In particular,
we show that if there are only two cops, there are vertices in $V(D)\cup
V^{\prime}\subset V(Q)$ that the robber can choose to move to without being
caught, using the following strategy. For any vertex $v$, denote by $N[v]$ the
set of vertices within distance at most one from $v$, and denote by $N^{2}[v]$
the set of vertices within distance at most two from $v$. The robber begins on
a vertex $r$ of the dodecahedron $D$, and remains on this vertex until a cop
moves to a vertex adjacent to $r$ in $Q$. inline]MK: this is not necessary, we
can show an even stronger result, namely, that the robber can be active, that
is, move every time on its turn For each neighbour $d$ of $r$ in the
dodecahedron $D$, denote by $d^{\prime}\in V^{\prime}$ the vertex that
subdivides the edge $rd$. inline]MK: for notation consistency let’s use simply
$rd$ to denote an edge, previously it was $\\{r,d\\}$ The robber inspects the
neighbors of $r$ in the dodecahedron $D$ and chooses such a neighbor $d$ that
$N[d^{\prime}]\cup N^{2}[d]$ contains no cops, and the robber’s next two turns
consist of moving to $d^{\prime}$ then $d$. Once the robber arrives at the
dodecahedron vertex $d$, it repeats the above strategy.

We now prove by induction that the robber can follow the strategy indefinitely
and will never be captured by any of the two cops. Suppose we’re at the start
of round $k$, the robber is at a vertex $r\in V(D)$, and it is not yet caught.
This means that neither of the two cops is at $r$. If there are no cops
adjacent to $r$, then the robber stays where it is, so it is not yet caught
and it is located at a vertex in $V(D)$ at the start of round $k+1$.
Otherwise, suppose there is at least one cop adjacent to $r$. Let the three
neighbors of $r$ in $D$ be $d_{1},d_{2}$, and $d_{3}$ and the corresponding
dodecahedron subdivision vertices be $d^{\prime}_{1},d^{\prime}_{2}$, and
$d^{\prime}_{3}$; see Figure 3. For each $i,j\in\\{1,2,3\\}$ such that $i\neq
j$, the only vertex shared by $N[d^{\prime}_{i}]\cup N^{2}[d_{i}]$ and
$N[d^{\prime}_{j}]\cup N^{2}[d_{j}]$ (see the gray regions in Figure 3) is $r$
which, by the induction assumption, is not occupied by any of the cops.
Therefore, each cop can be in at most one vertex in $N[d^{\prime}_{i}]\cup
N^{2}[d_{i}]$, for $i\in\\{1,2,3\\}$. Since there are only two cops, it
follows that, for some $j\in\\{1,2,3\\}$, the set of vertices
$N[d^{\prime}_{j}]\cup N^{2}[d_{j}]$ is cop-free. Therefore, the robber can
follow the given strategy, i.e., moving to $d_{j}^{\prime}$ in round $k$ then
$d_{j}$ in round $k+1$. No cop can capture the robber at $d_{j}^{\prime}$ in
round $k$ since there were no cops in $N[d^{\prime}_{j}]$ at the start of
round $k$, and, no cop can capture the robber at $d_{j}$ in round $k+1$ since
there were no cops in $N^{2}[d_{j}]$ at the start of round $k$. Thus, the
robber is not yet caught and it is located at a vertex in $V(D)$ at the start
of round $k+2$. color=cyan!10]Made some changes to clarify the proof. It still
needs more attention. color=green!10]I’ve made a pass through the proof,
hopefully good now? ∎

inline,color=cyan!10]If (a) depicts $D$, add it to the figure. Same for (b)
and Q. Also, show its triangulation that is used to form (b). Keep the scale
of (a) in (b); it is a bit confusing now. (that is, (b) must be a larger
graph).

(a) The dodecahedron graph $D$.

(b) Each face of the dodecahedron graph $D$ in the quadrangulation $Q$.

Figure 2: Construction of a quadrangulation $Q$ with cop number three from the
dodecahedron graph $D$ (the skeleton of a dodecahedron). Figure 3: Three faces
of the dodecahedron graph $D$ in quadrangulation $Q$. The edges of $D$ in
black, of $T$ in dark green, and of $Q$ in light green.

inline,color=cyan!10]Fig.2: Make the vertices larger if possible. It is not
clear that $d^{\prime}_{2}$ is indeed a vertex. (MK: increased the vertex
sizes) Btw, does the proof work for a single $Q$ or for three $Q$s as
subgraphs? Is it clarified in the proof? MK: not sure if I understand the
question correctly. We use only one copy of $Q$ in the proof

##  4 Cop Number of Maximal 1-Planar Graphs

###  4.1 Lower Bound

We prove that there exists a maximal 1-planar graph, which is also optimal
1-planar, with cop number at least three. The structure of optimal 1-planar
graphs is well known:

######  Lemma 1 (Suzuki [32])

For any embedded graph $G$, denote by $Q(G)$ the subgraph of $G$ induced by
the non-crossing edges. Then: (1) If $G$ is an embedded optimal 1-planar
graph, then $Q(G)$ is a plane quadrangulation; and, (2) Let $H$ be an
arbitrary simple planar quadrangulation. There exists a simple optimal
1-planar graph $G$ such that $H=Q(G)$ if and only if $H$ is $3$-connected.

Observe that the quadrangulation $Q$ defined in Section 3 is 3-connected.
Therefore, according to the proof of Lemma 1 in [32], we can construct an
optimal 1-planar graph $Q^{\prime}$ from $Q$ by adding the crossing diagonal
edges in each quadrangular face, as illustrated by the brown edges in Figure
4.

Figure 4: $Q^{\prime}$ is formed from $Q$ by adding crossing diagonal edges
(brown).

inline,color=cyan!10]It may be better to change Theorem 2’s statement to:
There are maximal 1-planar graphs with cop number at least 3. Refer to
$Q^{\prime}$ in the proof and before stating theorem. MK: I see the point if
this being a more general statement but we say this in the introduction and
here we make a statement which is more informative, namely, states exactly
which graph we mean

###### Theorem 4.1

The maximal 1-planar graph $Q^{\prime}$ has cop number at least three.

###### Proof

The proof uses the same robber strategy and induction proof as Theorem 3.1.
The only difference is that the closed neighborhood $N[d^{\prime}_{i}]$ of
$d^{\prime}_{i}$ and the closed distance-two neighborhood $N^{2}[d_{i}]$ of
$d_{i}$, for each $i=1,2,3$, are larger, but it still holds that the only
vertex shared by $N[d^{\prime}_{i}]\cup N^{2}[d_{i}]$ and
$N[d^{\prime}_{j}]\cup N^{2}[d_{j}]$ (see the gray regions in Figure 4) is
$r$. Therefore, for some $j\in\\{1,2,3\\}$, the set of vertices
$N[d^{\prime}_{j}]\cup N^{2}[d_{j}]$ is cop-free, and the robber can move to
vertex $d_{j}\in V(D)$ via $d^{\prime}_{j}$ without being caught.
inline,color=cyan!10]Even if you use the same induction, it may be good to re-
state in a complete proof in the appendix (call this proof a sketch). ∎

###  4.2 Upper Bound

Aigner and Fromme [1, Theorem 6] proved that planar graphs have cop number at
most three. One of the main arguments in their proof is the _Jordan curve
property_ , i.e., that a Jordan curve partitions the surface into two
connected regions: interior and exterior. Bonato and Mohar [8] noted that this
approach could also be used for designing a three-cop strategy for other
families of graphs that share this property, i.e., graphs with drawings in
which there exist special separating cycles (that will play the role of the
Jordan curves) that divide the drawing into interior and exterior. Once we
introduce crossings, however, it becomes unclear how to identify such
separating cycles, and this approach fails for 1-planar graphs (see Theorem
2.1). In this section, we show that we can still use the Jordan curve property
to devise a three-cop strategy for maximal 1-planar graphs; see Theorem 4.2.
We will take advantage of the structure of maximal 1-planar graphs, in
particular, the fact that in every maximal 1-planar drawing, every pair of
crossing edges $ab$ and $cd$ is enclosed in a quadrangle $acbd$ with four
uncrossed edges (forming a _kite_ together with the pair of crossing edges)
[3]; see Figure 5. Our proof strategy will follow closely that of Bonato and
Nowakowski [6, Theorem 4.25]; however, we will need different building blocks
that take into account the structure of maximal 1-planar graphs.

Figure 5: In a maximal 1-planar graph, every pair of crossing edges induces a
kite.

###### Lemma 2

Let $H$ be an induced subgraph of a maximal 1-planar graph, let $u,v\in V(H)$
be distinct, and let $P$ be a shortest path between $u$ and $v$ in $H$. Then
no two edges of $P$ cross.

###### Proof

Assume for the sake of contradiction that two edges $ab$ and $cd$ of $P$
cross. Then there is a kite $acbd$ and there is a shorter path that takes one
of the side edges ($ac$, $cb$, $bd$, or $da$) of the kite instead of the two
crossing edges. ∎

###### Lemma 3

Let $H$ be an induced subgraph of a maximal 1-planar graph such that the
robber can only move in $H$, let $u,v\in V(H)$ be distinct, and let $P$ be a
shortest path between $u$ and $v$ in $H$. Then a single cop on $P$ can, after
a finite number of moves: (a) prevent the robber from entering $P$, that is,
the robber will be immediately caught if they move onto $P$; and, (b) catch
the robber immediately after it traverses an edge that crosses an edge of $P$.

###### Proof

The proof of (a) holds for general graphs and can be found in the book of
Bonato and Nowakowski [6, Theorem 1.7]. The idea behind the proof is as
follows. Because the shortest path $P$ does not have shortcuts, after a finite
number of moves, the cop can follow the “projection” of the robber onto the
path, and thus, always remain close to the vertex of the path where the robber
might enter.

To prove (b), suppose that after sufficiently many moves, one of the cops
guards the path $P$ in the sense of (a). Assume the robber is at one of the
endpoints of some edge $ab$, say $a$, crossing some edge $v_{i}v_{i+1}$ of the
path $P$. Since $H$ is an induced subgraph of a maximal 1-planar graph, $ab$
together with $v_{i}v_{i+1}$ form a kite $av_{i}bv_{i+1}$. Consider a cop
strategy in which $P$ is guarded by one cop in the sense of (a). That is, the
cop moves in a way to catch the robber as soon as the robber enters $P$. So,
after a finite number of moves, if the robber is at $a$, the cop will be at
$v_{i}$ or $v_{i+1}$, in anticipation of the robber moving to any of these
vertices (note that the edges between $a$ and $v_{i}$ and $v_{i+1}$ exist due
to the kite structure). That is, when the robber moves from $a$ to $b$, the
cop will be at either $v_{i}$ or $v_{i+1}$ and can move to $b$ to catch the
robber in the next step. color=cyan!10]I rewrote this part for clarity. ∎

In light of Lemma 3, we say that a cop _guards_ the shortest path $P$ between
two vertices (referred to also as an _isometric path_) if after a finite
number of moves, it can prevent the robber from entering or crossing $P$.
Observe that, according to Lemma 2, no two edges of $P$ cross.

###### Lemma 4

Let $H$ be an induced subgraph of a maximal 1-planar graph such that the
robber can only move in $H$, let $u,v\in V(H)$ be distinct, and let $P_{1}$
and $P_{2}$ be two internally disjoint paths from $u$ to $v$ such that $P_{1}$
is isometric in $H$, $P_{2}$ is isometric in $H-(V(P_{1})\setminus\\{u,v\\})$,
and no edge of $P_{1}$ crosses an edge of $P_{2}$. Then $P_{1}\cup P_{2}$ can
be guarded by two cops in $H$.

###### Proof

According to Lemma 3, since $P_{1}$ is isometric in $H$, it can be guarded by
one cop. Similarly, since $P_{2}$ is isometric in
$H-(V(P_{1})\setminus\\{u,v\\})$ it can also be guarded by one cop.∎

######  Theorem 4.2 ()

Any maximal 1-planar graph $G$ has cop number at most three.

###### Proof

We provide a sketch of the proof here; see the complete proof in Appendix 0.A.

Given that $G$ is a maximal 1-planar graph, it is 2-connected and thus must
contain two internally disjoint shortest paths $P_{1}$ and $P_{2}$ between two
vertices $v,w\in G$, where $P_{1}$ is isometric in $G$, $P_{2}$ is isometric
in $G\setminus(V(P_{1})\setminus\\{u,v\\})$, and no edge of $P_{1}$ crosses an
edge of $P_{2}$. We let two cops $C_{1}$ and $C_{2}$ guard the two paths
$P_{1}$ and $P_{2}$, respectively, as described in Lemma 4. Therefore, after a
finite number of $t$ steps, the robber must avoid edges that are located on
these paths and must avoid crossing them. Define the _robber territory_ $H$ as
the subgraph induced by the vertices in the interior or exterior of the cycle
$P_{1}\cup P_{2}$, whichever contains the robber at step $t$. Given that the
robber territory is non-empty and $G$ is a maximal 1-planar graph, one can
consider a third isometric path $P_{3}$ between $v$ and $w$ that contains a
vertex in the robber territory; this path can share some vertices with $P_{1}$
or $P_{2}$ (or both). We let the third cop $C_{3}$ guard $P_{3}$, as in Lemma
3. Therefore, after a finite number of steps, the robber’s “safe zone” becomes
limited to one of the parts of the partition of the robber’s territory created
by $P_{3}$. We show that two cops can guard this area so that the robber stays
confined to it, and the third cop can be used to repeat this process in the
smaller subgraph that forms the safe zone of the robber.∎

##  5 Characterization of Cop-Win Outer 1-Planar Graphs

A graph $G$ is _outer $k$-planar_ if it can be drawn in the plane so that all
the vertices are in convex position on the outer boundary and each edge is
crossed at most $k$ times. In this section, we provide a complete
characterization of the cop number of outer 1-planar graphs.

First, we briefly discuss the cop number of general outer $k$-planar graphs.
Joret et al. [19] showed that the cop number of a graph can be bounded in
terms of its treewidth. In particular, if the treewidth of a graph is at most
$t$, then its cop number is at most $t/2+1$ [19]. Every outer $k$-planar graph
has treewidth at most $3k+11$ [33, Proposition 8.5], so, its cop number is at
most $1.5k+6.5$.

Restricting attention to outer 1-planar graphs, Auer et al. [2] showed that
every outer 1-planar graph has treewidth at most three, which implies that the
cop number of outer 1-planar graphs is at most two. Bonato et al. [7] showed
that an outerplanar graph $G$ is cop-win if and only if $G$ is chordal. We
generalize this result to outer 1-planar graphs, which completes our
characterization of $c$-cop-win outer 1-planar graphs for all $c\in\\{1,2\\}$.

Let $V=(v_{1},\ldots,v_{n})$ be the cyclic ordering of vertices of an outer
1-planar graph $G=(V,E)$. Let $V[v_{i},v_{j}]$, be the set of vertices
$(v_{i},v_{i+1},\ldots,v_{j})$, for $i\leq j$, and $V(v_{i},v_{j})$ be the set
of vertices $(v_{i+1},v_{i+2},\ldots,v_{j-1})$, for $i<j$.

###### Proposition 1

Let $G=(V,E)$ be an outer 1-planar graph. Consider $U\subset V$ such that
$G[U]$ forms a cycle. For every pair of vertices $u,w\in U$ such that
$V[u,w]\cap U=\\{u,w\\}$, it holds that if $u$ and $w$ are not adjacent, then
there are two edges $e_{u},e_{w}\in E(U)$ incident to $u$ and $w$,
respectively, such that $e_{u}$ and $e_{w}$ cross.

###### Proof

Consider such a pair $u,w\in V$, and assume that neither of the cycle edges
$uu_{1}$ nor $uu_{2}$ crosses any of the cycle edges $ww_{1}$ and $ww_{2}$;
see Figure 6. Consider the path $P_{1}=(w_{1},\ldots,u)$ in $G[U]$ from
$w_{1}$ to $u$ such that $w\notin P_{1}$. It follows that $w_{2}\notin P_{1}$,
and so there must be an edge $e_{1}=w_{1}^{\prime}w_{1}^{\prime\prime}\in
E(P_{1})$ such that $w_{1}^{\prime}\in V[w_{1},w_{2}]$ and
$w_{1}^{\prime\prime}\in V[w_{2},u_{1}]$ (note that the edge $e_{1}$ crosses
$ww_{2}$). Next, consider the path $P_{2}=(w_{2},\ldots,u)$ in $G[U]$ from
$w_{2}$ to $u$ such that $w,w_{1}\notin P_{2}$. There must be an edge
$e_{2}=w_{2}^{\prime}w_{2}^{\prime\prime}\in E(P_{2})$ such that
$w_{2}^{\prime}\in V[w_{1}^{\prime},w_{1}^{\prime\prime}]$ and
$w_{2}^{\prime\prime}\in V[w_{1}^{\prime\prime},u_{1}]$ (note that the edge
$e_{2}$ crosses $e_{1}$). Therefore, $e_{1}$ is crossed by two edges, $ww_{2}$
and $w_{2}^{\prime}w_{2}^{\prime\prime}$, contradicting the fact that $G$ is
outer 1-planar. ∎

Figure 6: Illustration in support of Proposition 1.

###### Corollary 1

Let $G=(V,E)$ be an outer 1-planar graph. Consider $U\subset V$ such that
$G[U]$ forms a cycle of order $k\geq 4$. For every $u,w\in U$ such that
$V(u,w)\cap U=\varnothing$, the number of vertices in $V\setminus V(u,w)$ that
are adjacent to at least one vertex in $V(u,w)$ is at most three.

###### Proof

By Proposition 1, either $u$ and $w$ are adjacent, or, there are two edges
$e_{u}$ and $e_{w}$ incident to $u$ and $w$, respectively, that cross. First,
suppose that $u$ and $w$ are adjacent. Then, each edge $vv^{\prime}\in E(G)$
such that $v\in{V}(u,w)$ and $v^{\prime}\in V\setminus{V}(u,w)$ and
$v^{\prime}\not\in\\{u,w\\}$ must cross the edge $uw$, so there can be at most
one such edge $vv^{\prime}$ since $G$ is outer 1-planar. Next, suppose that
$u$ and $w$ are not adjacent. Consequently, for any $v\in{V}(u,w)$ and any
$v^{\prime}\in V\setminus{V}(u,w)$ with $v^{\prime}\not\in\\{u,w\\}$, an edge
$vv^{\prime}$ would have to cross either $e_{u}$ or $e_{w}$. But since $G$ is
outer 1-planar and there is a crossing between $e_{u}$ and $e_{w}$, it follows
that no such edge $vv^{\prime}$ exists. So, in both cases above, we proved
that there is at most one vertex $v^{\prime}\in V\setminus{V}(u,w)$ with
$v^{\prime}\not\in\\{u,w\\}$ such that $v^{\prime}$ is adjacent to at least
one vertex in ${V}(u,w)$. The fact that $u$ and/or $w$ might be adjacent to at
least one vertex in ${V}(u,w)$ gives the desired upper bound of three.∎

###### Theorem 5.1

A connected outer 1-planar graph $G=(V,E)$ is cop-win if and only if it is
chordal.

###### Proof

It is known that if $G$ is chordal, then it is cop-win (in fact, this is true
for any graph [26]). Thus it remains to show that, if $G$ is not chordal, then
there is a robber strategy to escape one cop.

Suppose that $G$ is not chordal. Then there is a set $U\subset V$ so that
$|U|\geq 4$ and $G[U]$ is a cycle. Let $v_{1},\dots,v_{n}$ be the cyclic
ordering of $G$. For all $i\leq j$, let $V(v_{i},v_{j})$ be the set of
vertices $(v_{i+1},v_{i+2},\dots,v_{j-1})$. The robber’s strategy is to
maintain the following invariants at the end of each of its turns, and will
only move if one of them is violated at the start of its turn:

  1. 1.

If the cop is on a vertex $u\in U$, then the robber is on a vertex in
$U\setminus N[u]$, where $N[u]$ is the closed neighborhood of $u$.

  2. 2.

If, for some $u,w\in U$ such that $V(u,w)\cap U=\varnothing$, the cop is on a
vertex in $V(u,w)$, then the robber is on a vertex in $U$ that is not adjacent
to any vertex in $V(u,w)$.

Now, we show that this is always possible. We begin by considering the initial
position of the cop and robber. First, if the cop is on a vertex $u\in U$, we
have that $|N[u]\cap U|=3$. Then since $|U|\geq 4$, the robber can choose an
initial vertex in $U\setminus N[u]$. Second, if the cop is on a vertex in
$V(u,w)$ for some $u,w\in U$ such that $V(u,w)\cap U=\varnothing$, then, since
there are at most three vertices in $V\setminus V(u,w)$ that are adjacent to
at least one vertex in $V(u,w)$ by Corollary 1, and $|U|\geq 4$, the robber
can choose an initial vertex in $U$ that is not adjacent to any vertex in
$V(u,w)$. Now we must show that the robber can maintain these invariants. Let
$r\geq 1$ and suppose that the invariants are true at the end of the robber’s
turn in the $r$’th round. This implies that the cop and robber are not
adjacent, so the cop cannot catch the robber on its $(r+1)$’st turn. If
neither invariant is violated at the beginning of the robber’s $(r+1)$’st
turn, then we are done, so suppose that one of the invariants is violated.
Suppose that the first invariant is violated, i.e., the cop is on a vertex
$u_{1}\in U$ and the robber is on a vertex $u_{2}\in U\cap N(u_{1})$. Then,
since $|U|\geq 4$, there must be a vertex $u\in N(u_{2})\setminus N(u_{1})$,
so the robber can move to $u$ and the first invariant is satisfied at the end
of the robber’s turn. Next, suppose that the second invariant is violated,
i.e., the cop is on a vertex in $V(u,w)$ for some $u,w\in U$ such that
$V(u,w)\cap U=\varnothing$, and the robber is on a vertex $v\in U$ that is
adjacent to at least one vertex in $V(u,w)$. We will show that there is a
vertex $v^{\prime}\in U\cap N(v)$ that is not adjacent to a vertex in
$V(u,w)$. Suppose, for the sake of a contradiction, that there is no such
vertex $v^{\prime}$. Let $\\{v_{1},v_{2}\\}=N(v)\cap U$. Then $v,v_{1},v_{2}$
are all adjacent to vertices in $V(u,w)$ by assumption. Now, since neither of
the invariants were violated at the end of the robber’s $r$’th turn, then we
know that at the start of the cop’s $(r+1)$’st turn, the cop was not on
$v_{1}$, $v$, or $v_{2}$, nor was it in $V(u,w)$. But, by assumption, after
the cop’s $(r+1)$’st turn, the cop is on a vertex in $V(u,w)$. Thus, at the
start of the cop’s $(r+1)$’st turn, it must be the case that the cop was on a
vertex in $V\setminus\\{v_{1},v,v_{2}\\}$ that is adjacent to at least one
vertex in $V(u,w)$. However, this implies that there are at least four
vertices in $V\setminus V(u,w)$ that are adjacent to at least one vertex in
$V(u,w)$, which contradicts Corollary 1. By reaching a contradiction, we have
proved that there exists a vertex $v^{\prime}\in U\cap N(v)$ that is not
adjacent to a vertex in $V(u,w)$. Thus, the robber can move to this
$v^{\prime}$ and the second invariant is satisfied at the end of the robber’s
turn.∎

##  6 Discussion and Directions for Future Research

The cop number of an outer $k$-planar is at most $3k/2+13/2$ due to the fact
that its treewidth is bounded by $3k+11$ and the relation between the cop
number and treewidth of a graph [19]. Two questions follow naturally. Is there
a non-trivial lower bound expressed as a function of $k$? Can we reduce the
multiplicative factor of $3/2$ in the upper bound?

Determining whether a graph $G$ is $k$-cop-win is NP-hard, and $W[2]$-hard
parameterized by $k$ [15]. Very recently Gahlawat and Zehavi [16] showed that
the problem is fixed parameter tractable (FPT) in vertex cover. We would like
to restate their open question: whether the problem is FPT in feedback vertex
set, treewidth, or treedepth.

## References

  * [1] Aigner, M., Fromme, M.: A game of cops and robbers. Discrete Applied Mathematics 8(1), 1–12 (1984)
  * [2] Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Outer $1$-planar graphs. Algorithmica 74(4), 1293–1320 (2016)
  * [3] Barát, J., Tóth, G.: Improvements on the density of maximal 1-planar graphs. Journal of Graph Theory 88(1), 101–109 (2018)
  * [4] Bekos, M.A., Didimo, W., Liotta, G., Mehrabi, S., Montecchiani, F.: On rac drawings of 1-planar graphs. Theoretical Computer Science 689, 48–57 (2017). https://doi.org/https://doi.org/10.1016/j.tcs.2017.05.039, https://www.sciencedirect.com/science/article/pii/S0304397517304851
  * [5] Berarducci, A., Intrigila, B.: On the cop number of a graph. Advances in Applied Mathematics 14, 389–403 (1993)
  * [6] Bonato, A., Nowakowski, R.: The Game of Cops and Robbers on Graphs. Student mathematical library, American Mathematical Society (2011)
  * [7] Bonato, A., Breen, J., Brimkov, B., Carlson, J., English, S., Geneson, J.T., Hogben, L., Perry, K.E., Reinhart, C.: Optimizing the trade-off between number of cops and capture time in cops and robbers. Journal of Combinatorics 13(1), 79–203 (2019)
  * [8] Bonato, A., Mohar, B.: Topological directions in cops and robbers. Journal of Combinatorics 11, 47–64 (2020)
  * [9] Brandenburg, F.J., Eppstein, D., Gleißner, A., Goodrich, M.T., Hanauer, K., Reislhuber, J.: On the density of maximal 1-planar graphs. In: Graph Drawing. pp. 327–338. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)
  * [10] Chaplick, S., Kryven, M., Liotta, G., Löffler, A., Wolff, A.: Beyond outerplanarity. In: In Proceedings of the International Symposium on Graph Drawing and Network Visualization (GD). pp. 546–559. Springer (2018)
  * [11] Clarke, N.E., MacGillivray, G.: Characterizations of k-cop win graphs. Discrete Mathematics 312(8), 1421–1425 (2012)
  * [12] Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph drawing beyond planarity. ACM Computing Surveys 52(1), 1–37 (2019)
  * [13] Eppstein, D.: $k$-planar graphs and genus. Computer Science Stack Exchange (2015), https://mathoverflow.net/questions/221968/k-planar-graphs-and-genus Accessed: 2023-06-06
  * [14] Erde, J., Lehner, F.: Improved bounds on the cop number of a graph drawn on a surface. In: Extended Abstracts of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb). pp. 111–116. Springer International Publishing (2021)
  * [15] Fomin, F.V., Golovach, P.A., Kratochvíl, J., Nisse, N., Suchan, K.: Pursuing a fast robber on a graph. Theoretical Computer Science 411(7), 1167–1181 (2010). https://doi.org/https://doi.org/10.1016/j.tcs.2009.12.010, https://www.sciencedirect.com/science/article/pii/S0304397509008342
  * [16] Gahlawat, H., Zehavi, M.: Parameterized Analysis of the Cops and Robber Game. In: Leroux, J., Lombardy, S., Peleg, D. (eds.) 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 272, pp. 49:1–49:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2023). https://doi.org/10.4230/LIPIcs.MFCS.2023.49, https://drops.dagstuhl.de/opus/volltexte/2023/18583
  * [17] Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1–11 (2007)
  * [18] Hong, S.H., Tokuyama, T.: Beyond Planar Graphs. Communications of NII Shonan Meetings (2020)
  * [19] Joret, G., Kamiński, M., Theis, D.O.: The cops and robber game on graphs with forbidden (induced) subgraphs. Contributions to Discrete Mathematics 5(2), 40–51 (2010)
  * [20] Kalai, G., Nevo, E., Novik, I.: Bipartite rigidity. Transactions of the American Mathematical Society 368(8), 5515–5545 (2016), https://www.jstor.org/stable/tranamermathsoci.368.8.5515
  * [21] Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. In: Proceedings of the 16th International Symposium on Graph Drawing (GD). Lecture Notes in Computer Science, vol. 5417, pp. 302–312. Springer (2008)
  * [22] Lubiw, A., Snoeyink, J., Vosoughpour, H.: Visibility graphs, dismantlability, and the cops and robbers game. Computational Geometry 66, 14–27 (2017)
  * [23] Maurer, A., McCauley, J., Valeva, S., Beveridge, A., Islar, V., Saraswat, V.: Cops and Robbers on Planar Graphs. In: Summer 2010 Interdisciplinary Research Experience for Undergraduates (2010)
  * [24] Neufeld, S., Nowakowski, R.: A game of cops and robbers played on products of graphs. Discrete Mathematics 186(1), 253–268 (1998)
  * [25] Nowakowski, R.J., Winkler, P.: Vertex-to-vertex pursuit in a graph. Discrete Mathematics 43, 235–239 (1983)
  * [26] Quilliot, A.: Jeux et pointes fixes sur les graphes. Ph.D. thesis, Université de Paris VI (1978)
  * [27] Quilliot, A.: A short note about pursuit games played on a graph with a given genus. Journal of Combinatorial Theory, Series B 38(1), 89–92 (1985)
  * [28] Ringel, G.: Ein sechsfarbenproblem auf der kugel. In: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. vol. 29, pp. 107–117. Springer (1965)
  * [29] Schröder, B.S.W.: The Copnumber of a Graph is Bounded by [3/2 genus (G)] + 3, pp. 243–263. Birkhäuser Boston (2001)
  * [30] Schumacher, V.H.: Zur struktur 1-planarer graphen. Mathematische Nachrichten 125(1), 291–300 (1986). https://doi.org/https://doi.org/10.1002/mana.19861250122, https://onlinelibrary.wiley.com/doi/abs/10.1002/mana.19861250122
  * [31] Schumacher, V.H.: Zur struktur 1-planarer graphen. Mathematische Nachrichten 125(1), 291–300 (1986)
  * [32] Suzuki, Y.: Re-embeddings of maximum 1-planar graphs. SIAM Journal on Discrete Mathematics 24, 1527–1540 (2010)
  * [33] Wood, D.R., Telle, J.A.: Planar decompositions and the crossing number of graphs with an excluded minor. In: Proceedings of the 14th International Symposium on Graph Drawing (GD). pp. 150–161. Springer (2007)

##  Appendix 0.A Proof of Theorem 4.2

Let us define some additional useful notation. Let $X$ be a cycle without edge
crossings in a maximal 1-planar graph $G$, and let $u$ be a vertex of $G-X$.
The cycle $X$ partitions the plane into two regions: $A_{1}$ that contains $u$
and $A_{2}$ which does not. Let $V_{1}$ denote the vertices contained in
$A_{1}$, called the interior of $X$ with respect to $u$, and $V_{2}$ those in
$A_{2}$ which we call the exterior of $X$ with respect to $u$. The subgraph
induced by $V(X)\cup V_{1}$ is called _the internal subgraph_ determined by
$X$, and written $\mbox{int}({X})$. The subgraph induced by $V(X)\cup V_{2}$
is called _the external subgraph_ determined by $X$, and written
$\mbox{ext}({X})$. We note that the only way for the robber to pass from the
interior to the exterior (or vice versa), is to pass through a vertex of the
cycle $X$ or cross an edge of $X$.

See 4.2

###### Proof

Let $G^{\prime}$ be an induced subgraph of the maximal 1-planar graph $G$.
Consider the following steps.

Inductive argument: $G^{\prime}$ is 2-connected and thus must contain two
internally disjoint shortest paths $P_{1}$ and $P_{2}$ between two vertices
$v,w\in G^{\prime}$, where $P_{1}$ is isometric in $G^{\prime}$, $P_{2}$ is
isometric in $G^{\prime}\setminus(V(P_{1})\setminus\\{u,v\\})$, and no edge of
$P_{1}$ crosses an edge of $P_{2}$. We let two cops $C_{1}$ and $C_{2}$ guard
the two paths $P_{1}$ and $P_{2}$, respectively, as described in Lemma 4. In
the light of Lemma 3, after a finite number of $t$ steps, the robber must
avoid edges that are located on these paths and must avoid crossing them.

Define the _robber territory_ $H$ as the subgraph induced by the vertices in
the interior or exterior of the cycle $P_{1}\cup P_{2}$, whichever contains
the robber. Define the _cop territory_ as $G^{\prime}\setminus H$. Note that
any path from the robber to the cop territory $T$ crosses $P_{1}\cup P_{2}$
(either at a vertex or via an edge crossing). Therefore, the robber must
choose to move to or stay at a vertex in $H$ if it wants to avoid capture.

color=cyan!10]I added a note that “H is a 1-maximal planar graph that is
smaller than G’”

We show by induction on the size of $H$ that in a finite number of steps, the
three cops $C_{1},C_{2}$, and $C_{3}$ can move so that the robber territory
$H$ decreases by at least one vertex, and we are again in the situation as
described in our inductive assumption with $G^{\prime}=H$. Therefore, by the
induction hypothesis, the three cops can catch the robber, given that $H$ has
smaller size than $G^{\prime}$.

Base case: When $H$ is formed by only one vertex $v$, the robber will be
trivially caught by the cops in a finite number of rounds; if it crosses
$P_{1}$ or $P_{2}$, it will be caught by the above observation, and if it
stays in $v$, the cops eventually approach the robber and catch it at $v$.

Inductive step: Now suppose the induction assumption holds. Without loss of
generality, we may assume the robber is located in $\mbox{int}({X})$, where
$X=P_{1}\cup P_{2}$, and the subgraph $\mbox{ext}({X})$ is guarded by $C_{1}$
and $C_{2}$. Now $G^{\prime}$ is the subgraph induced on $V(\mbox{int}({X}))$
and $H$ is the subgraph induced on $V(\mbox{int}({X}))\setminus V(X)$. Let
$P_{3}$ be a simple shortest path between $v$ and $w$ in $G^{\prime}$ that has
at least one vertex of $H$. Given that $H$ is non-empty and $G^{\prime}$ is
2-connected, such path $P_{3}$ must exist. color=green!10]Fengyi pointed out
to me: the proof that $P_{3}$ exists is not rigorous enough (and Shahin also
commented on this on Tuesday?) According to Lemma 2, $P_{3}$ does not self-
cross (neither at a vertex nor via an edge crossing). Therefore, the path
$P_{3}$ partitions $G^{\prime}$ into induced subgraphs $G^{\prime}_{i}$
(sharing only the vertices of $P_{3}$), for $i=1,\dots,\ell$, that are bounded
by a contiguous part of $P_{3}$ and a contiguous part of either $P_{1}$ or
$P_{2}$; see Figure 7. After a finite number of moves, when $C_{3}$ can guard
$P_{3}$, the robber is trapped in one of such subgraphs, say $G^{\prime}_{i}$,
as we will describe next.

Assume $G^{\prime}_{i}$ is bounded by $P_{1}$ and $P_{3}$, and $P_{3}$ leaves
$P_{1}$ at some vertex $v_{1}$ (possibly $v_{1}=v$) and enters back at some
vertex $w_{1}$ (possibly $w_{1}=w$). Let $P^{\prime}_{1}$ be the part of
$P_{1}$ between $v_{1}$ and $w_{1}$ and $P^{\prime}_{2}$ be the part of
$P_{3}$ between $v_{1}$ and $w_{1}$. Observe that $P^{\prime}_{1}$ is a
shortest path between $v_{1}$ and $w_{1}$ in $G^{\prime}_{i}$ and
$P^{\prime}_{2}$ is a shortest path between $v_{1}$ and $w_{1}$ that is vertex
disjoint from $P^{\prime}_{1}$. Therefore, we are back to our induction
assumption with $G^{\prime}=G^{\prime}_{i}$, $P_{1}=P^{\prime}_{1}$,
$P_{2}=P^{\prime}_{2}$, and $H=G^{\prime}_{i}-P^{\prime}_{1}-P^{\prime}_{2}$.
By the induction hypothesis, the three cops will eventually catch the robber,
given that $H$ is a maximal 1-planar graph that is smaller than $G^{\prime}$.

Assume now that $G^{\prime}_{i}$ is bounded by $P_{2}$ and $P_{3}$, and
$P_{3}$ leaves $P_{2}$ at some vertex $v_{2}$ (possibly $v_{2}=v$) and enters
back at some vertex $w_{2}$ (possibly $w_{2}=w$). Let $P^{\prime}_{1}$ be the
part of $P_{3}$ between $v_{2}$ and $w_{2}$ and $P^{\prime}_{2}$ be the part
of $P_{2}$ between $v_{2}$ and $w_{2}$. The path $P^{\prime}_{1}$ is a
shortest $v_{2}w_{2}$-path in $G^{\prime}_{i}$; otherwise, $P_{3}$ would have
a shortcut. Therefore, we are again back to our induction assumption with
$G^{\prime}=G^{\prime}_{i}$, $P_{1}=P^{\prime}_{1}$, $P_{2}=P^{\prime}_{2}$,
and $H=G^{\prime}_{i}-P^{\prime}_{1}-P^{\prime}_{2}$. Again, by the induction
hypothesis, the three cops will eventually catch the robber, given that $H$ is
a maximal 1-planar graph that is smaller than $G^{\prime}$.∎

Figure 7: The path $P_{3}$ partitions $G^{\prime}$ into induced subgraphs
$G^{\prime}_{i}$ (sharing only the vertices of $P_{3}$).


# A Machine Learning Approach to the Detection of Ghosting and Scattered Light
Artifacts in Dark Energy Survey Images

Chihway Chang  Alex Drlica-Wagner  Stephen M. Kent  Brian Nord  Donah Michelle
Wang  Michael H. L. S. Wang<EMAIL_ADDRESS>University of Chicago, Chicago, IL
60637, USA  Kavli Institute for Cosmological Physics, University of Chicago,
Chicago, IL 60637, USA  Fermi National Accelerator Laboratory, Batavia, IL
60510, USA  Illinois Mathematics and Science Academy, Aurora, IL 60506, USA

###### Abstract

Astronomical images are often plagued by unwanted artifacts that arise from a
number of sources including imperfect optics, faulty image sensors, cosmic ray
hits, and even airplanes and artificial satellites. Spurious reflections
(known as “ghosts”) and the scattering of light off the surfaces of a camera
and/or telescope are particularly difficult to avoid. Detecting ghosts and
scattered light efficiently in large cosmological surveys that will acquire
petabytes of data can be a daunting task. In this paper, we use data from the
Dark Energy Survey to develop, train, and validate a machine learning model to
detect ghosts and scattered light using convolutional neural networks. The
model architecture and training procedure is discussed in detail, and the
performance on the training and validation set is presented. Testing is
performed on data and results are compared with those from a ray-tracing
algorithm. As a proof of principle, we have shown that our method is promising
for the Rubin Observatory and beyond.

###### keywords:

Machine Learning , Image Artifacts

††journal: Astronomy and Computing

##  1 Introduction

When the Dark Energy Survey (DES) [1, 2] completed its mission in January
2019, it had mapped $\sim$5000 square degrees of the southern sky using the
570 megapixel Dark Energy Camera (DECam) [3] mounted on the Blanco 4-m
telescope at the Cerro Tololo Inter-American Observatory in the Chilean Andes.
Over the course of 758 nights of data taking spread across 6 years, DES
generated a massive $\sim$2 petabytes of data. Due to the nature of the DECam
optical systems, the DES data are subject to imaging artifacts caused by
spurious reflections (commonly referred to as “ghosts”) and scattered light
[4] (see Figure 1). While all astronomical objects observed by DECam produce
ghosts and scattered light at some level, this study specifically focuses on
identifying artifacts from bright stars that are prominent enough to have a
negative impact on object detection, background estimation, and photometric
measurements. In particular, ghosts/scattered light present a major source of
contamination for studies of low-surface-brightness galaxies and present a
major challenge for precision photometry of faint objects [5]. Thus, much
effort has been devoted to the mitigation of such effects. For example, after
the DES science verification data set was collected, light baffles were
installed around all the filters to block a scattered-light path. After the
first year of DES, the cylindrical interior surfaces near the optical aperture
of the filter changer and shutter were painted with a black, anti-reflective
paint. This paint reduced the number of possible scattered-light paths and
improved the quality of subsequent data sets [3, 4]. In this article, we seek
to identify residual ghosts and scattered light artifacts in the DES data. We
use the term “ghosts/scattered light” to broadly refer to all artifacts that
result from spurious reflections and scattered light without distinguishing
between the various sources of these artifacts.

|  |
---|---|---
(a) | (b) | (c)
Figure 1: Example full focal plane DECam images that exhibit ghosts and
scattered light artifacts.

Due to the large volume of DES data, the identification of ghosts and
scattered light by eye is impractical. DES has automated the detection of
these artifacts through the development of a ray-tracing algorithm that
combines a model of the camera optics, the telescope pointing, and the known
locations and brightness of stars to predict the presence and location of
ghosts/scattered light in an exposure (Section 2). While this algorithm
correctly identifies and localizes a significant number of ghosts/scattered
light artifacts, it is limited by the accuracy of the optical model, the
telescope telemetry, and external catalogs of bright stars. Because the ray-
tracing algorithm does not use the DES imaging data directly, it can miss a
substantial number of ghosts/scattered light artifacts. There is clearly a
need for more effective methods to address this problem, especially in light
of future cosmic surveys like the Rubin Observatory Legacy Survey of Space and
Time (LSST), which will have a field of view three times as large as DECam and
will acquire $\sim$20 terabytes of data per night ($\sim$60 petabytes over ten
years) [6].

This paper explores the use of modern machine learning (ML) methods as a
potential solution to the problem of efficiently detecting ghosts/scattered
light in large optical imaging surveys. Though ML methods have been in use for
over half a century [7], we are referring specifically to the advances in
computer vision made in the past two decades. These advances were made
possible by the confluence of several key factors that included (1) a deeper
understanding of the internal workings of the visual cortex [8], (2) the
introduction of convolutional neural networks (CNNs) inspired by the visual
cortex [9], (3) the development of practical techniques to train such networks
[10], and (4) the availability of vastly increased computational power from
devices like graphics processing units (GPUs).

Attempts have been made to apply such ML techniques to the identification of
telescope artifacts. In an unpublished report, a CNN was found to
significantly outperform a classical ML algorithm (i.e., a support vector
machine) when both were applied to DES images to identify artifacts belonging
to 28 different classes [11]. However, in this study the CNN showed evidence
of overfitting, which the authors suggested could be mitigated with additional
training data. Instead of dealing with multiple classes of artifacts at once,
another effort relied on a CNN-based architecture to identify artifacts caused
by cosmic rays in Hubble Space Telescope images [12]. These authors showed
that a CNN-based approach could provide a significant improvement over the
current state-of-the-art method. In our work, we focus specifically on
ghosts/scattered light to demonstrate a proof-of-principle for the viability
of modern ML techniques for this purpose in large cosmological surveys.

Figure 2: Architecture of neural network with four convolutional+maxpool
layers followed by two fully connected layers.

##  2 Conventional Approach

The conventional approach to ghosts/scattered light artifact identification in
DES uses optical ray tracing. A standard optical design program is used to
perform sequential ray tracing to model the performance of the telescope and
optical corrector. Scattered light comes from grazing incidence scatters off
of surfaces such as the camera filter changer and shutter mechanism [4].
Ghosts are typically produced by reflections between two glass surfaces within
the corrector, and for each possible combination of surfaces, ghosts were
modeled by introducing two extra mirrored surfaces at the appropriate
positions into the optical design. The model is quite accurate at predicting
the locations of ghosts, but it has difficulty predicting their intensities,
since those depend on details of reflectivities from antireflection coatings
and filters, which in turn depend on the incidence angle and wavelength of
each ray. The reflectivities were calibrated empirically from ${\sim}100$ DES
images that contained bright stars of known intensity. In making predictions
for a validation image, the locations of all known stars were determined in
advance, intensities for all potential ghosts were estimated, and, if the
intensity for a particular ghost exceeded a preset threshold, the area covered
by the ghost was estimated by tracing about 2000 rays sampling the entrance
pupil of the telescope, and all CCDs illuminated by those rays were flagged as
being affected.

While the ray tracing algorithm correctly identifies and localizes a
significant number of ghosts/scattered light artifacts, it is limited by the
accuracy of the optical model and telescope pointing telemetry. The ray
tracing algorithm also depends on predetermined fluxes of bright stars to
predict the intensity of ghosts/scattered light artifacts. These fluxes are
taken from external catalogs, where they are reported in bands that differ
from those observed by DES. Furthermore, the fluxes of these stars are assumed
to be constant in time, while bright stars are often variable. Because of
these factors, the ray tracing algorithm can miss a substantial number of
ghosts/scattered light artifacts. For this reason, every image that was
flagged by the ray-tracing program was visually inspected, and in some cases,
the list of flagged CCDs was adjusted by hand.

Figure 3: Evolution of the accuracy (left) and loss (right) as a function of
epoch as evaluated on the training and validation samples.

##  3 Machine Learning Approach

Construction, training, and testing of the CNN-based ML model used in this
paper were all done using the Tensorflow and Keras machine learning frameworks
[13, 14].

###  3.1 Model Architecture

The choice of network architecture used in this work was guided by our
ultimate goal of investigating whether ML techniques were feasible for
detecting ghosts/scattered light artifacts, and if so, how they would compare
with the conventional technique based on ray tracing. Since the main objective
was a proof-of-concept demonstration, we opted for a relatively simple CNN
architecture that: (1) was straightforward to implement in a common ML
framework, (2) did not require significant computing resources to train, and
(3) had good performance on standard image classification data sets that would
carry over to artifact detection in DES exposures. The CNN architecture we
settled on was very similar to AlexNet [15], in its use of stacked 2D
convolutional layers with rectified linear unit (ReLU) activation functions
that alternate with max-pooling layers, and eventually terminated in fully
connected layers with SoftMax outputs. It differed from AlexNet in terms of
hyperparameters, such as the number of hidden layers, the number of kernels
and their sizes, stride lengths, and dropout values.

The detailed design of the CNN we used is shown in Figure 2. The network is
composed of four 2D convolutional layers, each followed by a maximum pooling
layer [9, 15]. The number of output filters in the sequence of four
convolutional layers are 16, 32, 32, and 64, respectively. Filters in all four
convolutional layers have kernel sizes of $3\times 3$, stride lengths of one,
and use ReLU activation functions. The pool sizes used in the pooling layers
are $4\times 4$ for the first layer and $2\times 2$ for all subsequent layers.
Stride lengths for all pooling layers correspond to their pool sizes. The
final two layers of the network, following the fourth pooling layer, are fully
connected (FC) layers. The first FC layer has 128 neurons with ReLU activation
functions and the last FC layer has 2 output neurons using SoftMax activation
functions. The larger of these two outputs, which sum to a value of one, was
selected to determine the model prediction. “Dropouts” are performed prior to
each FC layer in which a fraction (0.4 and 0.8 for the first and second FC
layers, respectively) of the inputs are randomly ignored. This method lessens
the chances of overfitting by minimizing co-adaptations between layers that do
not generalize well to unseen data [16]. The total number of parameters in the
model is 1,212,578.

###  3.2 Training the Model

The images used for training the model were derived from $800\times 723$
pixel, 8-bit grayscale images in the portable network graphics format,
covering the full DECam focal plane. These images were produced with the STIFF
program [17], assuming a power-law intensity transfer curve with index
$\gamma=2.2$. Minimum and maximum intensity values were set to the 0.005 and
0.98 percentiles of the pixel value distribution, respectively. The training
set consisted, initially, of equal portions of images that had
ghosts/scattered light (positives) and images that did not (negatives). The
positive sample consisted of 2,389 images that the ray-tracing program
identified as likely to have ghosts/scattered light artifacts and was drawn
from the full set of $\sim$132k images from all DES observing periods. After
excluding the images flagged by ray-tracing program, an equal number of images
were randomly selected from the remainder of the full data set to form the
negative sample of the training set.

Prior to feeding the images to the network, they were first downsampled to
$400\times 400$ pixels, which is the input size of the first convolutional
layer. The pixel values in each image were then normalized to a range whose
minimum and maximum corresponded, respectively, to the first quartile
$Q_{1}(x)$ and third quartile $Q_{3}(x)$ of the full distribution in the
image, by multiplying each pixel value, $x_{i}$, by a factor
$s_{i}=\frac{x_{i}-Q_{1}(x)}{Q_{3}(x)-Q_{1}(x)}$. To improve the model’s
ability to correctly identify images that contain ghosts/scattered light
artifacts, the training images were also randomly flipped either along the
horizontal axis by reversing the ordering of pixel rows, or along the vertical
axes by reversing the ordering of pixel columns. This was done using the
ImageDataGenerator class in Keras, which does an in-place substitution of the
input images with the flipped versions, without changing the total size of the
data sample [14].

####  3.2.1 Model Training Procedure

The model was trained using 80% of the sample described in the previous
section and the remaining fraction was set aside for validation. Apart from
this training/validation sample was a separate test sample used to evaluate
the model, which is described in Section 3.3. Optimal weights for the model
were obtained using Adam [18], a version of the mini-batch stochastic gradient
method that uses dedicated learning rates for each parameter and adapts their
values based on their history. The weights were updated iteratively in
randomly picked batches of 32 images (_batch size_), completing a full pass
over the entire sample in one _epoch_. A total of 30 training epochs were
performed. The loss function used was categorical cross-entropy, calculated
according to $L=-\sum_{i=1}^{N}\sum_{j=1}^{M}y_{ij}\cdot log(p_{ij})$, where
the index $i$ runs over the number of observations, $N$, and the index $j$ is
taken over the number of classes, $M$. $p_{ij}$ is the probability and
$y_{ij}$ is either 0 or 1, depending on whether class $j$ is the correct
classification for observation $i$. In our case, we have two classes ($M=2$)
corresponding to whether or not an image contains a ghost/scattered light
artifact.

Upon visual examination of the false positives and false negatives after
training, it was found that some images were mislabeled. This was because
images labeled as lacking ghosts/scattered light artifacts were initially
selected based on the ray-tracing program output. As it turned out, many
“clean” images actually contained ghosts/scattered light. When images that
were positively identified by the ray-tracing program were inspected, the
opposite case was also found to be true – some images labeled as having
ghosts/scattered light did not exhibit detectable artifacts. Therefore,
several iterations were required in order to fix the mislabeled images and
repeat the 30-epoch training process.

####  3.2.2 Training and Validation Results

Figure 4: ROC curves and the associated areas under the ROC curves (AUCs) are
shown separately for the training, validation, and independent test samples.
The green dash-dotted line represents the reference case of no discriminating
power (AUC=0.5).

The final results of training are shown in Figures 3, 4, and 5. The two panels
in Figure 3 show the evolution of the training accuracy (left) and loss
(right) over the epochs. The validation curves follow the training curves
closely, indicating no overfitting. Accuracies of over 94% are achieved on
both training and validation sets at the end of 30 epochs.

|  |
---|---|---
(a) | (b) | (c)
Figure 5: The confusion matrices are shown separately for the (a) training,
(b) validation, and (c) independent test samples. In each matrix, the number
of true negatives and positives are shown, respectively, in the upper left and
right boxes, while the number of false positives and negatives are shown,
respectively, in the upper right and lower left boxes. Performance Summary
---
Sample | Accuracy | Precision | Recall | AUC
training | 0.963 | 0.959 | 0.967 | 0.990
validation | 0.944 | 0.927 | 0.959 | 0.987
test | 0.861 | 0.837 | 0.897 | 0.917
Table 1: Summary of performance metrics for each sample. Accuracy, precision,
and recall are calculated as described in Section 3.3 using the values in
Figure 5. The AUCs are the areas under the ROC curves in Figure 4.

Figure 4 plots the receiver operating characteristic curve (ROC) for the
trained model, showing the true postive rate versus the false positive rate.
The curves resulting from the application of this model to the training (light
blue dotted line) and validation (solid blue line) samples are shown
separately. The area under the ROC curve (AUC) for the validation sample is
0.987, indicating good separation between the two classes of images. For
comparison, the diagonal green dash-dotted line shows the case when a model
has absolutely no discriminating power between classes where AUC=0.5.

Figures 5a and 5b plot the confusion matrices for the training and validation
samples, respectively. In each matrix, the values in the first row represent
the number of true negatives in the first column and the number of false
positives in the second column. The values in the second row represent the
number of false negatives in the first column and the number of true positives
in the second column.

###  3.3 Evaluating the Model

The validation set was not used directly to train the model, however, it
served as an early indicator of model performance in the training process. In
this respect, it could have influenced the model and hyperparameter choices.
The performance of the fully trained model was therefore evaluated in an
unbiased way using an independent test data sample. This sample was
constructed by visually selecting an equal number of images containing
ghosts/scattered light artifacts and those without them, and labeling them
according to their true class. It consisted of 1,761 DECam images spread
across all DES data taking periods. It also excluded all the images used for
training and validation, and was $\sim$37% of that sample in size. The fully
trained model was applied to this sample to predict which class they belonged
to. The ROC curve for the test data sample is represented by the dashed red
line in Figure 4 with AUC=0.917, indicating good discrimination between the
two classes. From the confusion matrix shown in Figure 5c, one calculates
$accuracy=\mathrm{\frac{TP+TN}{Total}}=0.861$,
$precision=p=\mathrm{\frac{TP}{TP+FP}}=0.837$,
$recall=r=\mathrm{\frac{TP}{TP+FN}}=0.897$, and $F_{1}=2\cdot\frac{p\cdot
r}{p+r}=0.866$, where TP, FP, TN, and FN are, respectively, the number of true
positives, false positives, true negatives and false negatives. These results
are summarized in Table 1 together with those for the training and validation
samples.

Typical examples of misclassified images from the test sample, in the form of
false positives and false negatives, are shown in Figures 6 and 7,
respectively. Although the images in the first class of false positives
represented by Figures 6a–6c do not bear an obvious resemblance to those
containing ghosting/scattered light artifacts, they all exhibit poor data
quality from nearly a magnitude of extinction due to clouds that may be
confusing the CNN. These images do not pass the high-level DES data quality
criteria. The second class of false positives contain objects that exhibit
features similar to those found in ghosting artifacts (Figures 6d–6f) and
scattered light artifacts (Figures 6g & 6h), making them intuitively easier to
appreciate. The third class of false positives, represented by Figure 6i, are
in some sense true positives, because they contain faint artifacts close to
the human detection threshold. In this image, there is a ghost artifact
faintly visible in the 4th and 5th columns from the left, in the two middle
rows of CCDs. The false negatives in Figure 7 are easier to understand because
they all contain ghost artifacts that are not too difficult to see (their
locations are described in the figure caption).

Our application involves a large data set where images with ghosts/scattered
light constitute a relatively small fraction of the entire sample. False
negatives carry a high cost due to their detrimental effects on astronomical
measurement and the difficulty of manual identification in a data set of this
size. On the other hand, false positives are less of a problem since they are
easier to identify from the smaller sample predicted by the model to be
ghosts/scattered light. Our model’s true positive rate or $recall$ of
$\sim$90% shows it is able to identify a significant fraction of all images
with ghosts/scattered light, and its $precision$ of $\sim$84% indicates that
false positives are also kept under control, both of which are favorable
characteristics for this application. As indicated by the AUC, our model
performs better on the training and validation set than on the test set. This
may be an indication of biases introduced in the construction of the former
set, which is based on images identified by the ray-tracing program.

|  |
---|---|---
(a) | (b) | (c)
|  |
(d) | (e) | (f)
|  |
(g) | (h) | (i)
Figure 6: Example false positives found by the trained model in the test set described in Section 3.3. The exposures shown in panels (a), (b), and (c) have poor data quality due to heavy cloud cover which contributes to misclassification by the CNN. The barred spiral NGC 1365 in the Fornax galaxy cluster (d), Galactic cirrus (e), and the Omega Centauri globular cluster in (f), exhibit features similar to those found in ghosting artifacts. The faint resolved stars in the periphery of the LMC in (g), and the artificial earth-orbiting satellite track in (h), have features found in scattered light artifacts. There is a barely visible ghost artifact in columns 4 & 5 of the middle two rows of CCDs in (i). |  |
---|---|---
(a) | (b) | (c)
Figure 7: Selected examples of false negatives found by the trained model in the test set described in 3.3. Faint ghosts/scattered light artifacts are visible in the upper left corner of (a), rightmost column CCD in the 5th row from the top of (b), and rightmost column CCDs in the 8th and 9th rows from the top of (c).  |
---|---
(a) | (b)
|
(c) | (d)
|
(e) | (f)
Figure 8: The images above are examples of DES Year 5 images predicted by the
CNN described in this paper to exhibit ghosts/scattered light artifacts, but
which were not identified by the ray-tracing algorithm as such. Figures (a) to
(d) show examples that have actual artifacts, representing true positives.
Figures (e) and (f) are examples of the $\sim$23% described in the text that
either do not exhibit artifacts or have negligible levels, representing false
positives.

##  4 Applying the Trained Model on DES Data and Comparing with the
Traditional Method

The CNN trained according to the details described in Section 3.2 was used to
perform inference on the DES Year-5 data set consisting of 23,755 full focal
plane DECam images with exposure numbers ranging from 666747 to 724364, which
were prepared using the procedure described in Section 3.2. This set also
included the Year-5 images that were used in the training+validation and
testing stages. For each image, the model was used to predict whether it
contained ghosts/scattered light or whether it was free from such artifacts.
The model identified 3,285 images as positives, containing ghosts/scattered
light artifacts. Several examples of these images are shown in Figure 8. Only
716 images in this set of positives were false positives, exhibiting nearly
imperceptible or no sign of ghosts/scattered light artifacts. The precision
achieved was therefore $p=\nicefrac{{2569}}{{3285}}=0.782$.

For comparison, the ray-tracing program described in Section 2 classified 259
DES Year-5 images as containing artifacts. Out of these, 241 were in common
with the set of positives identified by the ML model, and all of the images in
this overlap region were true positives. The remaining 18 that were positively
classified only by the ray-tracing program were all true positives except for
8. The precision achieved by the ray tracing model was therefore
$p=\frac{{241+10}}{259}=0.969$.

The difference in precision from the two methods may be due to the more
limited range of image types dealt with by the ray-tracing program, and the
issue raised in Section 3.3 about the training and validation set being based
on the images identified by that program.

##  5 Computer Resource Utilization

The conventional ray tracing algorithm takes on the order of a few ms per
image for actual ray tracing. Additional time is spent querying the bright
star catalog around each exposure as a pre-processing step. This algorithm was
run on a yearly basis as input to the DES data processing.

For the CNN-based approach, training the model over 30 epochs using the
procedure described in Section 3.2.1 on a laptop with an Intel Xeon E-2176M
CPU, 32GB RAM, and a mid-range 4GB Nvidia Quadro P2000 Mobile GPU took 8.8 min
(18 s/epoch) to complete. Utilizing the 16GB Nvidia P100 GPUs available in the
Google Cloud Colaboratory Jupyter notebook environment [19], reduces the
training time by a factor of $4\times$ (4.4 s/epoch).

The process of performing inference with the CNN on the 23,755 image DES
Year-5 data set described in Section 4 took 50 s (2 ms/image) on the Quadro-
equipped laptop described above. Such short inference times are indeed
promising for real-time artifact identification on future large-scale cosmic
surveys, especially since the network model has not even been optimized for
speed yet. Furthermore, there now exist practical high-level synthesis tools
that can implement these network models on FPGA hardware for critical real-
time applications [20].

##  6 Conclusion

We have successfully applied a machine learning based method to identify DES
images containing ghosts/scattered light artifacts. This method positively
identified $\sim$97% of all images that had been previously identified as
containing artifacts by a traditional ray-tracing method. Overall, it also
identified $\sim$10$\times$ more images with actual artifacts, with a
precision of $\sim$78%. This serves as a proof-of-principle demonstrating the
effectiveness of using modern ML methods in identifying ghosts/scattered light
in optical telescope images from a cosmic survey. It lays the foundation for
possible future refinements. The scope of this work was limited to detecting
the presence of these artifacts in an image without identifying their location
within the image. In future work, we will take advantage of recent
developments in object detection and semantic segmentation to expand the
capability of our method to include the identification of the individual
pixels associated with each artifact [21]. Such enhancements, coupled with the
results presented in this work, will benefit future cosmic surveys like the
LSST, which will be faced with the challenge of even larger data sets.

##  7 Acknowledgements

This collaborative work was carried out as part of an Illinois Mathematics and
Science Academy (IMSA) Student Inquiry and Research (SIR) project. We wish to
thank Dr. Don Dosch, Dr. David Devol, and Dr. Eric Smith of IMSA for
overseeing the SIR program and making this collaboration possible. We also
wish to thank the staffs of Fermilab’s experimental astrophysics group and
IMSA’s SIR office for their support.

Funding for the DES Projects has been provided by the U.S. Department of
Energy, the U.S. National Science Foundation, the Ministry of Science and
Education of Spain, the Science and Technology Facilities Council of the
United Kingdom, the Higher Education Funding Council for England, the National
Center for Supercomputing Applications at the University of Illinois at
Urbana-Champaign, the Kavli Institute of Cosmological Physics at the
University of Chicago, the Center for Cosmology and Astro-Particle Physics at
the Ohio State University, the Mitchell Institute for Fundamental Physics and
Astronomy at Texas A&M University, Financiadora de Estudos e Projetos,
Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro,
Conselho Nacional de Desenvolvimento Científico e Tecnológico and the
Ministério da Ciência, Tecnologia e Inovação, the Deutsche
Forschungsgemeinschaft and the Collaborating Institutions in the Dark Energy
Survey.

The Collaborating Institutions are Argonne National Laboratory, the University
of California at Santa Cruz, the University of Cambridge, Centro de
Investigaciones Energéticas, Medioambientales y Tecnológicas-Madrid, the
University of Chicago, University College London, the DES-Brazil Consortium,
the University of Edinburgh, the Eidgenössische Technische Hochschule (ETH)
Zürich, Fermi National Accelerator Laboratory, the University of Illinois at
Urbana-Champaign, the Institut de Ciències de l’Espai (IEEC/CSIC), the
Institut de Física d’Altes Energies, Lawrence Berkeley National Laboratory,
the Ludwig-Maximilians Universität München and the associated Excellence
Cluster Universe, the University of Michigan, the National Optical Astronomy
Observatory, the University of Nottingham, The Ohio State University, the
University of Pennsylvania, the University of Portsmouth, SLAC National
Accelerator Laboratory, Stanford University, the University of Sussex, Texas
A&M University, and the OzDES Membership Consortium.

Based in part on observations at Cerro Tololo Inter-American Observatory,
National Optical Astronomy Observatory, which is operated by the Association
of Universities for Research in Astronomy (AURA) under a cooperative agreement
with the National Science Foundation.

The DES data management system is supported by the National Science Foundation
under Grant Numbers AST-1138766 and AST-1536171. The DES participants from
Spanish institutions are partially supported by MINECO under grants
AYA2015-71825, ESP2015-66861, FPA2015-68048, SEV-2016-0588, SEV-2016-0597, and
MDM-2015-0509, some of which include ERDF funds from the European Union. IFAE
is partially funded by the CERCA program of the Generalitat de Catalunya.
Research leading to these results has received funding from the European
Research Council under the European Union’s Seventh Framework Program
(FP7/2007-2013) including ERC grant agreements 240672, 291329, and 306478. We
acknowledge support from the Brazilian Instituto Nacional de Ciência e
Tecnologia (INCT) e-Universe (CNPq grant 465376/2014-2).

This manuscript has been authored by Fermi Research Alliance, LLC under
Contract No. DE-AC02-07CH11359 with the U.S. Department of Energy, Office of
Science, Office of High Energy Physics.

##  8 Contributions

The author list is ordered alphabetically. C. Chang was responsible for the
initial idea of applying ML techniques to artifact detection and served as
primary mentor to D.M. Wang in the SIR project. A. Drlica-Wagner identified
optical ghosts/scattered light detection as an important problem that could
benefit from an alternative approach. He also ran the ray-tracing algorithm,
provided access to labeled images containing ghosts/scattered light, and
advised on their classification and causes. S. Kent developed the DECam ray-
tracing algorithm and provided expertise on the origins of ghosts and
scattered light in the DECam system. B. Nord provided initial training on ML
algorithms and advised on algorithm design. He also served as the primary
liason between the astrophysics group at Fermilab and IMSA. D.M. Wang was
responsible for extending the sample ML models provided by B. Nord to develop
the models used in this work. She also performed the training and validation
of the model, including selecting its set of hyperparameters. M.H.L.S. Wang
prepared the samples used for training and comparisons, based on the data A.
Drlica-Wagner provided access to. He also advised on the preprocessing of the
data and prepared the initial version of this document, including the model
architecture diagram.

## References

  * [1] DES Collaboration, The Dark Energy Survey (2005).  arXiv:astro-ph/0510346.
  * [2] DES Collaboration, The Dark Energy Survey: more than dark energy – an overview, MNRAS 460 (2) (2016) 1270–1299.  doi:10.1093/mnras/stw641.
  * [3] B. Flaugher, et al., The Dark Energy Camera, Astron. J. 150 (2015) 150.  arXiv:1504.02900, doi:10.1088/0004-6256/150/5/150.
  * [4] S. M. Kent, Ghost Images in DECam, FERMILAB-SLIDES-20-114-SCD (2013).  doi:10.2172/1690257.
  * [5] D. Tanoglidis, et al., Shadows in the Dark: Low-Surface-Brightness Galaxies Discovered in the Dark Energy Survey (2020).  arXiv:2006.04294.
  * [6] v. Z. Ivezić, et al., LSST: from Science Drivers to Reference Design and Anticipated Data Products, Astrophys. J. 873 (2) (2019) 111.  arXiv:0805.2366, doi:10.3847/1538-4357/ab042c.
  * [7] A. L. Samuel, Some studies in machine learning using the game of checkers, IBM Journal of Research and Development 3 (3) (1959) 210–229.  doi:10.1147/rd.33.0210.
  * [8] D. H. Hubel, T. N. Wiesel, Receptive fields of single neurones in the cat’s striate cortex, The Journal of Physiology 148 (3) (1959) 574–591.  doi:10.1113/jphysiol.1959.sp006308.
  * [9] Y. Lecun, L. Bottou, Y. Bengio, P. Haffner, Gradient-based learning applied to document recognition, Proceedings of the IEEE 86 (11) (1998) 2278–2324.  doi:10.1109/5.726791.
  * [10] G. E. Hinton, S. Osindero, Y.-W. Teh, A fast learning algorithm for deep belief nets, Neural Computation 18 (7) (2006) 1527–1554, pMID: 16764513.  doi:10.1162/neco.2006.18.7.1527.
  * [11] J. W. DeRose, W. R. Morningstar, Automated image artifact identification in dark energy survey ccd exposures, CS229 Final Project Report, Stanford University (December 2015).
URL http://cs229.stanford.edu/proj2015/149_report.pdf

  * [12] K. Zhang, J. S. Bloom, deepCR: Cosmic ray rejection with deep learning, The Astrophysical Journal 889 (1) (2020) 24.  doi:10.3847/1538-4357/ab3fa6.
URL https://doi.org/10.3847%2F1538-4357%2Fab3fa6

  * [13] M. Abadi, et al., TensorFlow: Large-scale machine learning on heterogeneous systems, software available from tensorflow.org (2015).
URL https://www.tensorflow.org/

  * [14] F. Chollet, et al., Keras, https://keras.io (2015).
  * [15] A. Krizhevsky, I. Sutskever, G. E. Hinton, Imagenet classification with deep convolutional neural networks, in: F. Pereira, C. J. C. Burges, L. Bottou, K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems 25, Curran Associates, Inc., 2012, pp. 1097–1105.
  * [16] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, R. Salakhutdinov, Dropout: A simple way to prevent neural networks from overfitting, Journal of Machine Learning Research 15 (2014) 1929–1958.
URL http://jmlr.org/papers/v15/srivastava14a.html

  * [17] E. Bertin, Displaying Digital Deep Sky Images, in: P. Ballester, D. Egret, N. P. F. Lorente (Eds.), Astronomical Data Analysis Software and Systems XXI, Vol. 461 of Astronomical Society of the Pacific Conference Series, 2012, p. 263.
  * [18] D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, in: 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
URL http://arxiv.org/abs/1412.6980

  * [19] Google LLC, Colaboratory: Frequently asked questions, https://research.google.com/colaboratory/faq.html (2021).
  * [20] J. Duarte, et al., Fast inference of deep neural networks in FPGAs for particle physics, JINST 13 (07) (2018) P07027.  arXiv:1804.06913, doi:10.1088/1748-0221/13/07/P07027.
  * [21] K. He, G. Gkioxari, P. Dollár, R. Girshick, Mask r-cnn (2018).  arXiv:1703.06870.