# Mutual Visibility in Graphs

Gabriele Di Stefano

( Department of Information Engineering, Computer Science and Mathematics
University of L’Aquila – Italy
<EMAIL_ADDRESS>)

###### Abstract

Let $G=(V,E)$ be a graph and $P\subseteq V$ a set of _points_. Two points are
_mutually visible_ if there is a shortest path between them without further
points. $P$ is a _mutual-visibility set_ if its points are pairwise mutually
visible. The _mutual-visibility number_ of $G$ is the size of any largest
mutual-visibility set. In this paper we start the study about this new
invariant and the mutual-visibility sets in undirected graphs. We introduce
the Mutual-Visibility problem which asks to find a mutual-visibility set with
a size larger than a given number. We show that this problem is NP-complete,
whereas, to check whether a given set of points is a mutual-visibility set is
solvable in polynomial time. Then we study mutual-visibility sets and mutual-
visibility numbers on special classes of graphs, such as block graphs, trees,
grids, tori, complete bipartite graphs, cographs. We also provide some
relations of the mutual-visibility number of a graph with other invariants.

##  1 Introduction

Given a set of points in Euclidean space, they are mutually visible if and
only if no three of them are collinear. Then two points $p$ and $q$ are
mutually visible when no further point is on the line segment $pq$. A line
segment in Euclidean space represents the shortest path between two points,
but in more general topologies, this type of path (called geodesic) may not be
unique. Then, in general, two points are mutually visible when there exists at
least a shortest path between them without further points.

In this paper, we investigate the mutual visibility of a set of points in
topologies represented by graphs (e.g., see Figure 6b). In particular, a
fundamental problem is finding the maximum number of points in mutual
visibility that a given graph can have. To this aim, consider the following
new invariant: the _mutual-visibility number_ of a graph is the size of any
largest _mutual-visibility set_ , that is, a subset of the vertices (_points_)
that are in mutual visibility. To study this invariant from a computational
point of view, we introduce the Mutual-Visibility problem: find a mutual-
visibility set with a size larger than a given number. We prove that this
problem is NP-complete, whereas, to check whether the points of a given set
are in mutual visibility is a problem solvable in polynomial time. Then, given
this situation, our work proceeds by investigating the mutual-visibility
number for special classes of graphs, showing how the Mutual-Visibility
problem can be solved in polynomial time. We also provide some relations of
the mutual-visibility number of a graph with other invariants.

While these new concepts are interesting in themselves, their study is
motivated by the fundamental role that mutual visibility plays in problems
arising in the context of mobile entities, as shown below. Furthermore, points
of a graph in mutual visibility may represent entities on some nodes of a
computer/social network that want to communicate in a efficient and
“confidential” way, that is, in such a way that the exchanged messages do not
pass through other entities.

#### Related works

Questions about sets of points and their mutual visibility in Euclidean plane
have been investigated since the end of XIX century. Perhaps, the most famous
problem was posed by Sylvester [17], who conjectured that it is not possible
to arrange a finite set of points “so that a right line through every two of
them shall pass through a third, unless they all lie in the same right line”.
A correct proof was given by Gallai [16] some 40 years later, with a theorem
now known as Sylvester–Gallai theorem. In [10], Chapter III, it is shown how
to place a set of points with integer positive coordinates $(i,j)$, $j\leq i$,
in such a way that each point is in mutual visibility with the origin $(0,0)$,
by also maximizing the number of points with the same abscissa. This
disposition shows interesting relations with the Farey series and the Euler’s
totient function $\phi$: the number of points with abscissa $n$ is exactly
$\phi(n)$.

More recently, mutual visibility has been studied in the context of mobile
entities modeled as points in the Euclidean plane, whose visibility can be
obstructed by the presence of other mobile entities. The problem investigated
in [7] is perhaps the most basic: starting from arbitrary distinct positions
in the plane, within finite time the mobile entities must reach a
configuration in which they are in distinct locations and they can all see
each other. Since then, many papers have addressed the same subject (e.g., see
[3, 5, 12, 15]) and similar visibility problems were considered in different
contexts where the entities are “fat robots” modeled as disks in the plane
(e.g., see [13]) or are points on a grid based terrain and their movements are
restricted only along grid lines (e.g., see [1]).

Visibility problems were also studied on graphs. Wu and Rosenfeld [14]
considered the mutual visibility in pebbled graphs. They assumed that the
visibility may be obstructed by “pebbles” placed on some vertices of the
graph. Two unpebbled vertices $u,v$ of a pebbled graph $G$ are mutually
visible if and only if there exists a shortest path $p$ in $G$ between $u$ and
$v$ such that no vertex of $p$ is pebbled. In [18] they consider edge
pebblings and vertex pebblings, by showing that the visibility relations
defined by edge and vertex pebblings are incomparable. Again in the context of
mobile entities, in [2] it is studied the Complete Visitability problem of
repositioning a given number of robots on the vertices of a graph so that each
robot has a path to all others without visiting an intermediate vertex
occupied by any other robot. Here, the required paths are not shortest paths
and the studied graphs are restricted to the infinite squared grid and the
infinite hexagonal grid, both embedded in the Euclidean plane.

#### Contribution

In Section 2, formal definitons of mutual-visibility set and mutual-visibility
number are provided along with basic notations and some preliminary results.
Algorithmic results about the Mutual-Visibility problem are shown in Section
3. In Section 4 we study the mutual-visibility sets and mutual-visibility
numbers for special classes of graphs. Concluding remarks and notes about
further studies on the subject are provided in Section 5.

##  2 Notation and preliminaries

In this work we consider finite, simple, loopless, undirected and unweighted
graphs $(V,E)$ with vertex set $V$ and edge set $E$. We use standard
terminologies from [6, 9], some of which are briefly reviewed here.

#### Basic notation.

Let $G=(V,E)$ be a graph. A subgraph of $G$ is a graph having all its vertices
and edges in $G$. Given a subset $S$ of $V$, the induced subgraph $G[S]$ of
$G$ is the maximal subgraph of $G$ with vertex set $S$. The subgraph of $G$
induced by $V\setminus S$ is denoted by $G-S$, and $G-x$ stands for
$G-\\{x\\}$. If $v$ is a vertex of $G$, by $N_{G}(v)$ we denote the neighbors
of $v$, that is, the set of vertices that are adjacent to $v$, and by
$N_{G}[v]$ we denote the closed neighbors of $v$, that is
$N_{G}(v)\cup\\{v\\}$. The number of edges incident to a vertex $v$ of a graph
$G$ is the _degree_ of that vertex and is denoted $deg_{G}(v)$. Then
$deg_{G}(v)=|N_{G}(v)|$ and the maximum degree is denoted $\Delta(G)$. If
$|N_{G}(v)|=1$, $v$ is called _pendant_ vertex. Two vertices $u,v$ are _true
twins_ if $uv\in E$ and $N_{G}[u]=N_{G}[v]$ and are _false twins_ if
$uv\not\in E$ and $N_{G}(u)=N_{G}(v)$. The operation of extending a graph by
adding a new vertex which has a twin in the obtained graph, is called
_splitting_ [4].

A sequence of pairwise distinct vertices $(x_{0},x_{1},\ldots,x_{n})$ is a
path in $G$ if $x_{i}x_{i+1}\in E$ for $0\leq i<n$, and is an induced path if
$G[\\{x_{0},\ldots,x_{n}\\}]$ has $n$ edges. The _length_ of an induced path
is the number of its edges. A cycle in $G$ is a path $(x_{0},\ldots,x_{n-1})$,
$n\geq 3$, where also $x_{0}x_{n-1}\in E$. A _$(x,y)$ -path_ is a path from
$x$ to $y$. A graph $G$ is connected if for each pair of vertices $x$ and $y$
of $G$ there is a $(x,y)$-path in $G$. In a connected graph $G$, the length of
a shortest $(x,y)$-path is called distance and is denoted by $d_{G}(x,y)$. A
_connected component_ of $G$ is a maximal connected subgraph of $G$. A vertex
$x$ is an _articulation vertex_ if $G-x$ has more connected components than
$G$. A graph $G=(V,E)$ is _biconnected_ if $G-x$ is connected, for each $x\in
V$.

A subgraph $H$ of $G$ is said to be _convex_ if all shortest paths in $G$
between vertices of $H$ actually belong to $H$. The _convex hull_ of a subset
$V^{\prime}$ of vertices – denoted _$h(V^{\prime})$_ – is defined as the
smallest convex subgraph containing $V^{\prime}$.

#### Operations on graphs

If $G$ is a graph, $\overline{G}$ denotes its _complement_ , that is the graph
on the same vertices such that two distinct vertices of $\overline{G}$ are
adjacent if and only if they are not adjacent in $G$. Given two graphs
$G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$, such that $V_{1}\cap
V_{2}=\emptyset$, the _disjoint union_ $G_{1}\cup G_{2}$ denotes the graph
$(V_{1}\cup V_{2},E_{1}\cup E_{2})$; the _join_ $G_{1}+G_{2}$ denotes the
graph consisting in $G_{1}\cup G_{2}$ and all edges joining $V_{1}$ with
$V_{2}$, that is $(V_{1}\cup V_{2},E_{1}\cup E_{2}\cup\\{xy~{}|~{}x\in
V_{1},y\in V_{2}\\})$. To define the _Cartesian product_ $G_{1}\times
G_{2}=(V,E)$, consider any two vertices $u=(u_{1},u_{2})$ and
$v=(v_{1},v_{2})$ in $V=V_{1}\times V_{2}$. Then $uv\in E$ whenever either
$u_{1}=v_{1}$ and $u_{2}v_{2}\in E_{2}$ or $u_{2}=v_{2}$ and $u_{1}v_{1}\in
E_{1}$. We call $G_{1}$ and $G_{2}$ _isomorphic_ , and write $G_{1}\sim G_{2}$
if there exists a bijection $\varphi:V_{1}\rightarrow V_{2}$ with $xy\in
E_{1}\iff\varphi(x)\varphi(y)\in E_{2}$ for all $x,y\in V_{1}$.

#### Special graphs

In this paper we use some special graphs. $K_{n}$ denotes the _complete graph_
(or _clique_) with $n$ vertices and $n(n-1)/2$ edges. The _clique number_
$\omega(G)$ of a graph $G$ is the number of vertices in a maximum clique in
$G$. $P_{n}$ denotes the _path graph_ with $n$ vertices and $n-1$ edges.
$C_{n}$ denotes the _cycle graph_ with $n$ vertices and $n$ edges. Finally,
$K_{m,n}=\overline{K_{m}}+\overline{K_{n}}$ denotes the _complete bipartite
graph_. A _tree_ is a connected graph without cycles and its pendant vertices
are called _leaves_. The tree $K_{1,n}$ is called _star_ and can be obtained
by adding $n$ pendant vertices to a single vertex, called the _center_ of the
star. The graph $C_{3}$ is also called _triangle_. A _grid graph_
$\Gamma_{m,n}=P_{m}\times P_{n}$ is the Cartesian product of two paths $P_{m}$
and $P_{n}$. For $m\geq 3$ and $n\geq 3$ a graph $T_{m,n}=C_{m}\times C_{n}$
obtained by the Cartesian product of two cycle graphs is called _torus_. A
connected graph obtained from $K_{1}$ by a sequence of splittings is called
_cograph_.

$(u_{0},v_{0})$
---
$(u_{2},v_{0})$
---
$(u_{4},v_{0})$
---
$(u_{6},v_{0})$
---

Figure 1:  A grid graph $\Gamma_{2,7}$ with $\mu(\Gamma_{2,7})=4$ and an
induced subgraph $H$ of $\Gamma_{2,7}$ that is a tree with five leaves. For
each graph, vertices in red are points of a maximum mutual-visibility set,
then $\mu(H)=5>\mu(\Gamma_{2,7})$.

#### Preliminaries

Let $G=(V,E)$ be a graph and $P\subseteq V$ a set of _points_. Two points are
_mutually visible_ if there is a shortest path between them with no further
point. $P$ is a _mutual-visibility set_ if its points are pairwise mutually
visible. The _mutual-visibility number_ of $G$ is the size of any largest
mutual-visibility set of $G$ and it is denoted $\mu(G)$. By $M(G)$ we denote
the set containing all the largest mutual-visibility sets of $G$. Formally:

$M(G)=\\{P~{}|~{}P\subseteq V\mbox{ is a mutual-visibility set and
}|P|=\mu(G)\\}$

Notice that given a graph $G$ and a set of points $P$, the mutual visibility
relation between two points in $P$ is reflexive, symmetric, but not
transitive. Then it is different from the visibility relations studied in
[18], that are all transitive.

Let $H=(V_{H},E_{H})$ be an induced subgraph of a graph $G$. If $P$ is a
mutual-visibility set in $G$ then $P\cap V_{H}$ is not necessarily a mutual-
visibility set of $H$. For example, consider a cycle graph $C_{n}$, $n\geq 4$:
it is easy to find a maximum mutual-visibility set $P$ of size three. Now
consider an induced subgraph $C_{n}-v$, where $v\not\in P$: it is a path
graph. All the points in $P$ are in $C_{n}-v$, but they are not mutually
visible, since one of them is between the other two. However, the following
lemma holds for convex subgraphs of a given graph.

###### Lemma 2.1

Let $H=(V_{H},E_{H})$ be a convex subgraph of $G=(V,E)$. Let $P\subseteq V$ be
a mutual-visibility set of $G$. Then $P\cap V_{H}$ is a mutual-visibility set
of $H$.

Proof. Let $u,v$ be two not necessarily distinct vertices of $G$ in
$P^{\prime}=P\cap V_{H}$, then, by definition of convex subgraph, all the
shortest paths between $u$ and $v$ in $G$ are in $H$ and one of them is
without points in $P$ and then in $P^{\prime}$. Hence $u,v$ are mutually
visible in $H$. By the generality of $u,v$, $P^{\prime}$ is a mutual-
visibility set of $H$. $\Box$

Given a graph $G$ and a positive integer $k$, the property $\mu(G)\leq k$ is
not a hereditary property for induced subgraphs, i.e., it is possible for an
induced subgraph $H$ of $G$ that $\mu(H)>k\geq\mu(G)$. Consider the grid graph
$\Gamma_{2,7}\sim P_{2}\times P_{7}$ in Figure 1, where $P_{2}=(u_{0},u_{1})$
and $P_{7}=(v_{0},v_{1},\ldots,v_{6})$. Then, as we will prove in Section 4.3,
$\mu(G)=4$. The induced subgraph $H$ obtained by removing vertices
$(u_{0},v_{0}),(u_{2},v_{0}),(u_{4},v_{0})$, and $(u_{6},v_{0})$ from $G$ is a
tree with five leaves, then, as shown in Figure 1 and proved in Section 4.2,
$\mu(H)=5$. So $\mu(H)>4=\mu(G)$.

However, if we consider convex subgraphs of $G$ the property holds, as stated
by the following lemma.

###### Lemma 2.2

Let $H$ be a convex subgraph of a graph $G$. Then $\mu(H)\leq\mu(G)$.

Proof. Any mutual-visibility set $P$ of $H$ is also a mutual-visibility set of
$G$, since all the shortest paths between points in $P$ are both in $G$ and in
$H$. Then the statement follows. $\Box$ The next lemma sets an upper bound to
the mutual-visibility number of a graph based on the mutual-visibility numbers
of certain convex subgraphs.

###### Lemma 2.3

Let $G=(V,E)$ be a graph and let $V_{1},V_{2},\ldots V_{k}$ be subsets of $V$
such that $\bigcup_{i=1}^{k}V_{i}=V$. Then
$\mu(G)\leq\sum_{i=1}^{k}\mu(h(V_{i}))$.

Proof. Assume $\mu(G)>\sum_{i=1}^{k}\mu(h(V_{i}))$ and let $P\subseteq V$ be a
mutual-visibility set such that $|P|=\mu(G)$. Since $\bigcup_{i=1}^{k}V_{i}=V$
any point of $P$ is in at least one convex hull $h(V_{i})$. Let $P_{i}$ be the
set of vertices that are in $P$ and in $h(V_{i})$, for each $i=1,2,\ldots,k$.
Then $\sum_{i=1}^{k}|P_{i}|\geq|P|=\mu(G)>\sum_{i=1}^{k}\mu(h(V_{i}))$. Hence
there exists at least a set $P_{j}$ such that $|P_{j}|>\mu(h(V_{j}))$, for
some $j$ in $\\{1,2,\ldots,k\\}$. This is a contradiction since, by Lemma 2.1,
$P_{j}$ is a mutual-visibility set of $h(V_{j})$ and its size cannot be larger
than $\mu(h(V_{j}))$. $\Box$

It is worth to notice that for each graph $G$ there exists a mutual-visibility
set $P$ such that $|P|=\mu(G)$ and no articulation vertex is in $P$, as shown
below.

###### Lemma 2.4

Let $G=(V,E)$ be a graph and let $X$ be the set of its articulation vertices.
There exists a maximum mutual-visibility set $P\in M(G)$ such that $X\cap
P=\emptyset$.

Proof. Let $P$ be any mutual-visibility set in $M(G)$ and suppose, by
contradiction, that there exists a point $x_{P}\in X\cap P$. Let
$(V_{1},E_{1}),(V_{2},E_{2}),\ldots(V_{k},E_{k}),k\geq 2$ be the new connected
components of $G-x_{P}$, created by removing $x_{P}$. Note that
$P\setminus\\{x_{p}\\}\subseteq\bigcup_{\ell=1}^{k}V_{\ell}$. However, there
is only one index $i\in\\{1,\ldots,k\\}$ such that $P\cap
V_{i}\not=\emptyset$, otherwise there would be two points $u,v$ belonging to
two different connected components in $G-x_{P}$ that are in mutual visibility
in $G$. This is impossible since any shortest $(u,v)$-path passes through
$x_{P}$. Then $P^{\prime}=(P\setminus\\{x_{P}\\})\cup\\{x^{\prime}\\}$, where
$x^{\prime}\in V_{j},j\not=i$, is such that $P^{\prime}\in M(G)$. $\Box$

Before calculating mutual-visibility numbers and maximum mutual-visibility
sets for some graph classes, let us show a first result that compares the
mutual-visibility number of a graph $G$ with two well studied invariants of
$G$.

###### Lemma 2.5

Given a graph $G$ with clique number $\omega(G)$ and maximum degree
$\Delta(G)$ then $\mu(G)\geq\omega(G)$ and $\mu(G)\geq\Delta(G)$.

Proof. All vertices of a largest clique $K$ of $G$ form a mutual-visibility
set. Then $\omega(G)=|K|=\mu(K)$, and, by Lemma 2.2, $\mu(K)\leq\mu(G)$
because $K$ is a convex subset of $G$. Hence, $\omega(G)\leq\mu(G)$.

Let $v$ be a vertex of $G$ with degree $\Delta(G)$, then consider the set
$P=N_{G}(v)$. For any two vertices $x,y\in N_{G}(v)$ they are adjacent or at
distance two in the path $(x,v,y)$. Then, since $v$ is not in $P$, in both
cases they are in mutual visibility and then $P$ is a mutual-visibility set.
$\Box$

Where Lemma 2.3 provides an upper bound to the mutual-visibility number of a
graph, Lemma 2.5 provides two lower bounds to this value. The following lemma
gives a first taste of the mutual-visibility number in two basic graph
classes, that will be useful to derive further results.

###### Lemma 2.6

The mutual-visibility number of a path graph $P_{n}$, $n\geq 2$, is
$\mu(P_{n})=2$ and the mutual-visibility number of a cycle graph $C_{n}$,
$n\geq 3$, is $\mu(C_{n})=3$.

Proof. $\mu(P_{n})$ cannot be larger than two since, as already noted, a point
of any mutual-visibility set with three or more points would be on the unique
shortest path between two other points. Moreover, since $n\geq 2$ there is an
edge $e$ in $P_{n}$ and the two endpoints of $e$ are mutually visible, so
$\mu(P_{n})=2$.

Regarding the cycle graph $C_{n}=(x_{0},x_{1}\ldots,x_{n-1})$, $\mu(C_{n})\geq
3$ since it is always possible to choice $x_{0}$,
$x_{\lceil\frac{n}{2}\rceil-1}$ and $x_{\lceil\frac{n}{2}\rceil}$ as three
points in mutual visibility. Any largest mutual-visibility set cannot have
four or more points as, otherwise, there exist four points $x_{i_{1}}$,
$x_{i_{2}}$, $x_{i_{3}}$ and $x_{i_{4}}$, with $i_{1}<i_{2}<i_{3}<i_{4}$, such
that the two $(x_{i_{1}},x_{i_{3}}$)-paths contain $x_{i_{2}}$ and
$x_{i_{4}}$, respectively, and then $x_{i_{1}}$ and $x_{i_{3}}$ are not in
mutual visibility. $\Box$

##  3 Computational complexity

To study the computational complexity of finding a maximum mutual-visibility
set in a graph, we introduce the following decision problem.

###### Definition 3.1

Mutual-Visibility problem:
Instance: A graph $G=(V,E)$, a positive integer $K\leq|V|$.
Question: Is there a mutual-visibility set $P$ of $G$ such that $|P|\geq K$?

The problem is hard to solve as shown by the next theorem.

$u_{i}$
---
$\bar{u_{i}}$
---
$u_{i}$
---
$\bar{u_{i}}$
---
$s_{i}$
---
$t_{i}$
---
$s_{i}$
---
$t_{i}$
---
$u_{1}$
---
$\bar{u_{1}}$
---
$u_{2}$
---
$\bar{u_{2}}$
---
$u_{p}$
---
$\bar{u_{p}}$
---
$v_{1}$
---
$v_{2}$
---
$v_{q}$
---
$w$
---
$y$
---
$z$
---
$y^{\prime}$
---
$z^{\prime}$
---

Figure 2: The graph used in Theorem 3.1. Red vertices are points. Most visible
vertices and edges represent the main part of the graphs. The rest is added to
ensure the mutual visibility among points. Top left: The true-setting gadget
used to represent a variable $x_{i}$ with two maximum mutual-visibility sets
representing the two possible truth assignments: $x_{i}$ is false if and only
if $u_{i}$ is a point.

###### Theorem 3.1

Mutual-Visibility is NP-complete.

Proof. Given a set of points $P\subseteq V$ of $G$, we can test in polynomial
time whether $P$ is a mutual-visibility set or not (see also Algorithm MV).
Consequently, the problem is in NP.

We will now prove that the 3SAT problem, shown as NP-complete in [11],
polynomially reduces to Mutual-Visibility.

> A 3SAT instance $\Phi$ is defined as a set
> $X=\\{x_{1},x_{2},\ldots,x_{p}\\}$ of $p$ boolean variables and a set $C$ of
> $q$ clauses, each defined as a set of three literals: every variable $x_{i}$
> corresponds to two literals $x_{i}$ (the positive form) and $\bar{x_{i}}$
> (the negative form). To simplify the notations we will denote by
> $\\{\ell_{1},\ell_{2},\ell_{3}\\}$ the clause with literals
> $\ell_{i},i=1,2,3$, without distinction between the orders in which they are
> listed. A truth assignment assigns a Boolean value ($True$ or $False$) to
> each variable, corresponding to a truth assignment of opposite values for
> the two literals $x_{i}$ and $\bar{x_{i}}$: $\bar{x_{i}}$ is $True$ if and
> only if $x_{i}$ is $False$. For a literal $\ell\in\\{x_{i},\bar{x_{i}}\\}$
> we denote by $\bar{\ell}$ its negation: $\bar{\ell}=\bar{x_{i}}$ if
> $\ell=x_{i}$ and $\bar{\ell}=x_{i}$ if $\ell=\bar{x_{i}}$. A clause is
> satisfied if at least one of its literals is satisfied. The 3SAT problem
> asks whether there is a truth assignment satisfying all clauses.

In what follows, we assume there are at least three clauses such that their
(pairwise) intersection is empty. Any instance $\Phi$ that does not satisfy
this constraint can be transformed into an instance $\Phi^{\prime}$ with such
three clauses by adding five new variables $a,b,c,d,e$ and the required three
clauses $\\{a,\bar{a},b\\}$, $\\{\bar{b},c,\bar{c}\\}$, $\\{d,\bar{d},e\\}$
that are always satisfied for each truth assignment. Then the 3SAT instance
$\Phi$ has a Yes answer if and only if $\Phi^{\prime}$ has a Yes answer.

We transform 3SAT to Mutual-Visibility. Let $X=\\{x_{1},x_{2},\ldots,x_{p}\\}$
and $C=\\{c_{1},c_{2},\ldots,c_{q}\\}$ be any instance of 3SAT. We must
construct a graph $G=(V,E)$ and a positive integer $K\leq|V|$ such that $G$
has a mutual-visibility set of size $K$ or more if and only if $C$ is
satisfiable.

For each variable $x_{i}\in X$, there is a true-setting convex subgraph of $G$
$T_{i}=(V_{i},E_{i})$, with $V_{i}=\\{u_{i},\bar{u_{i}},s_{i},t_{i}\\}$ and
$E_{i}=\\{u_{i}\bar{u_{i}},\bar{u_{i}}s_{i},\bar{u_{i}}s_{i},s_{i}t_{i}\\}$.
See the top left part of Figure 2 for a drawing of $T_{i}$ and the two
possible maximum mutual-visibility sets. Note that each of the two maximum
mutual-visibility sets of $T_{i}$ contain either $u_{i}$ or $\bar{u_{i}}$.

For each clause $c_{j}\in C$, there is a vertex $v_{j}$ and, for each literal
$x_{i}$ (or $\bar{x_{i}}$) in $c_{j}$ there is in an edge $v_{j}u_{i}$ (or an
edge $v_{j}\bar{u_{i}}$, respectively). Moreover, there is a vertex $w$ and
edges ${v_{j}}w$ for each $j=1,2,\ldots,q$.

There are four more vertices in $V$, that is $y,y^{\prime},z,z^{\prime}$. For
each $i\in\\{1,2,\ldots,p\\}$ there are edges ${u_{i}}y$, $\bar{u_{i}}y$,
${s_{i}}z$, ${t_{i}}z$, ${s_{i}}w$, ${t_{i}}w$. Finally, $E$ contains edges
$yz$, $yy^{\prime}$ and $zz^{\prime}$.

A representation of $G$ is given in Figure 2.

The construction of our instance of Mutual-Visibility is completed by setting
$K=3p+q+2$. It is easy to see how the construction can be accomplished in
polynomial time. All that remains to be shown is that $C$ is satisfiable if
and only if $G$ has a mutual-visibility set of size $K$ or more.

First, suppose that $t:X\rightarrow\\{True,False\\}$ is a satisfying truth
assignment for $C$. The corresponding set of points $P$ includes vertices
$u_{i}$ if $t(x_{i})$ is $False$, and $\bar{u_{i}}$ otherwise, for each
$i\in\\{1,2,\ldots,p\\}$. Moreover $y^{\prime}$, $z^{\prime}$, $v_{j}$,
$s_{i}$, $t_{i}$ are in $P$, for each possible value of $i$ and $j$. No
further vertex is in $P$. Then $|P|=3p+q+2=K$. It remains to show that $P$ is
a mutual-visibility set. Clearly, $y^{\prime}$ is in mutual visibility with
$z^{\prime}$. Let
$ST=\left\\{s_{i},t_{i}~{}|~{}i\in\\{1,2,\ldots,p\\}\right\\}$,
$U=\left\\{u_{i},\bar{u_{i}}~{}|~{}i\in\\{1,2,\ldots,p\\}\right\\}$,
$D=\left\\{v_{j}~{}|~{}j\in\\{1,2,\ldots,q\\}\right\\}$. Each vertex in $ST$
is in mutual visibility with all the points in its true-setting subgraph and
with all the other points in $P$ thanks to shortest paths passing through
vertices $w,y$, and $z$ that are not in $P$ (e.g., for $t_{i}\not\in T_{1}$,
the paths
$(t_{i},z,s_{1}),(t_{i},z,t_{1}),(t_{i},z,z^{\prime}),(t_{i},z,y,y^{\prime}),(t_{i},z,y,u_{1}),(t_{i},z,y,\bar{u_{1}}),(t_{i},w,v_{1})$).

All the points in $D$ are in mutual visibility through shortest paths of
length two via vertex $w$. More interesting is to show that each point $v\in
D$ is in mutual visibility with $y^{\prime}$ (and with $z^{\prime}$). Point
$v$ corresponds to a clause $c\in C$ and, since $C$ is satisfiable, there is a
vertex $u$ in $N_{G}(v)\cap U$ that is not in $P$ corresponding to a $True$
literal in $c$. Then the shortest paths $(v,u,y,y^{\prime})$ and
$(v,u,y,z,z^{\prime})$ show that $v$ is in mutual visibility with $y^{\prime}$
and $z^{\prime}$. Finally, each point in $U$ is in mutual visibility with all
the other points in $U$, because of shortest paths passing through $y$.
Regarding the mutual visibility of points in $U$ with points in $D$, let
$v_{j}$ be a point in $D$ corresponding to a clause $c_{j}$ and let $x_{i}$
(or $\bar{x_{i}})$ be a literal in $c_{j}$ corresponding to vertex $u_{i}$ (or
$\bar{u_{i}}$). If $t(x_{i})$ is True then either the point $\bar{u_{i}}$ is
connected to $v_{j}$ with the path $(\bar{u_{i}},u_{i},v_{j})$ or
$\bar{u_{i}}$ is adjacent to $v_{j}$. Otherwise, if $t(x_{i})$ is False then
either the point $\bar{u_{i}}$ is adjacent to $v_{j}$ or connected to $v_{j}$
via $(u_{i},\bar{u_{i}},v_{j})$. Similarly for all the literals in $c_{j}$. If
$x_{i}$ is not in $c_{j}$ then point $u_{i}$ (or $\bar{u_{i}}$) is in mutual
visibility with $v_{j}\in D$ thanks to a shortest path
$(u_{i},y,u^{\prime},v_{j})$ (or $(\bar{u_{i}},y,u^{\prime},v_{j})$), where
the vertex $u^{\prime}\in D$ is in correspondence with a $True$ literal in
$c_{j}$. This concludes the first part of the proof.

Conversely, let us suppose that there is a set $P\subseteq V$ of points such
that $|P|\geq K=3p+q+2$. In $C$ there are three clauses that do not share any
variable. Assume, without loss of generality, that these three clauses are,
$c_{1}$, $c_{2}$, $c_{3}$. Then the star subgraph $H$ of $G$ induced by
vertices $v_{1}$, $v_{2}$, $v_{3}$ and $w$ is a convex subgraph of $G$. Convex
subgraph of $G$ are $T_{i}$, the path graph
$H^{\prime}=(y^{\prime},y,z,z^{\prime})$ and each subgraph $L_{j}\sim K_{1}$
consisting in a single vertex $v_{j}$, $j=4,\ldots q$. The union of the
vertices of these convex subgraphs is $V$ then, by applying Lemmas 2.3, we
have:

$\mu(G)\leq\mu(H)+\mu(H^{\prime})+\sum_{i=1}^{p}\mu(T_{i})+\sum_{j=4}^{q}\mu(L_{j})=3+2+3p+(q-3)=3p+q+2$

The above inequality holds since it is not difficult to see that $\mu(H)=3$
(see also Corollary 4.3), $\mu(H^{\prime})=2$ by Lemma 2.6, and, by
enumeration, that $\mu(T_{i})=3$. The mutual-visibility number $\mu(G)$ is the
size of a largest mutual-visibility set in G, then $|P|=K=3p+q+2$. Since $y$
and $z$ are articulation vertices we can assume, by Lemma 2.4, they are not in
$P$.

Moreover, at least one vertex for each $T_{i}$ is not in $P$: call $Q$ the set
of such vertices. Then the points in $P$ are a subset of
$V^{\prime}=V\setminus(Q\cup\\{y,z\\})$. Since $|V|=4p+q+5$ and $|Q|\geq p$,
then $|V^{\prime}|\leq 3p+q+3$. Hence at most one vertex in $V^{\prime}$ is
not in $P$. Consequently, at least two vertices among $v_{1}$, $v_{2}$,
$v_{3}$ of $H$ are in $P$ (say $v_{1}$, $v_{2}$), and since $H$ is a convex
subgraph of $G$ then the only shortest path between $v_{1}$ and $v_{2}$ is
$(v_{1},w,v_{2})$. This implies that $w$ is not in $P$, otherwise $v_{1}$ and
$v_{2}$ are not in mutual visibility.

In conclusion, all the vertices in $D$ are in $P$, $y^{\prime}$ and
$z^{\prime}$ are in $P$ and three vertices for each $T_{i}$ are in $P$, and in
particular exactly one vertex among $u_{i}$ and $\bar{u_{i}}$ is in $P$. Now,
consider a point $v_{j}$ in $D$ and its corresponding clause $c_{j}$. Since
$v_{j}$ and $y^{\prime}$ are mutually visible, at least one vertex in
$N_{G}(v_{j})\cap U$ is not in $P$ an then, the corresponding literal is
$True$ and $c_{j}$ is satisfied. By the generality of $c_{j}$ all the clauses
are satisfied. $\Box$

Theorem 3.1 shows that Mutual-Visibility is hard, however the following
problem, which asks to test if a given set of points is a mutual-visibility
set, can be solved in polynomial time.

###### Definition 3.2

Mutual-Visibility Test:
Instance: A graph $G=(V,E)$ and $P\subseteq V$.
Question: Is $P$ a mutual-visibility set of $G$?

The solution is provided by means of Algorithm MV that in turn uses Procedure
BFS_MV as a sub-routine. Procedure BFS_MV and Algorithm MV are shown in
Figures 1 and 2, respectively.

Procedure: BFS_MV

Input : A connected graph $G=(V,E)$, a set of points $P$, $v\in V$, a boolean
$t$

Output : The distance vector of $v$ from any vertex $u$ in $P$ calculated in
$G$, if $t$ is True, otherwise calculated in $G-P\setminus\\{u,v\\}$.

1 $D[u]:=\infty~{}\forall u\in V$;

2 $DP[p]:=\infty~{}\forall p\in P$;

3 $D[v]:=0$;

4 if  _$v\in P$_ then $DP[v]:=0$;

5 Let $Q$ be a queue;

6 $Q.enqueue(v)$;

7 while  _$Q$ is not empty and $\exists p\in P,D[p]=\infty$ _ do

8 $u:=Q.dequeue()$;

9 for  _each $w$ in $N_{G}(u)$_ do

10 if  _$D[w]=\infty$_ then

11 $D[w]:=D[u]+1$;

12 if  _ $w\in P$_ then $DP[w]:=D[w]$;

13 if  _$t$ or $w\not\in P$_ then $Q.enqueue(w)$;

14

15

16

17

18return DP

Algorithm 1 Procedure BFS_MV

Algorithm: MV

Input : A graph $G=(V,E)$ and a set of points $P\subseteq V$

Output : True if $P$ is a mutual-visibility set, False otherwise

1 if  _points in $P$ are in different connected components of $G$_ then

2 return False

3Let $H$ be the connected component of $G$ with points;

4 for  _each $p\in P$_ do

5 if  _BFS_MV (H,P,p,False) $\not=$ BFS_MV (H,P,p,True)_ then

6 return False

7

return True

Algorithm 2 Algorithm MV

###### Theorem 3.2

Algorithm MV solves Mutual-Visibility Test in $O(|P|(|V|+|E|))$ time.

Proof. When $G$ is connected, Algorithm MV (see Figure 2) calculates the
distances between any pair of points $u,v\in P$ both in $G$ and in
$G-P\setminus\\{u,v\\}$, the graph obtained by removing all the points in $P$
except $u$ and $v$ (loop at Line 2). To this end, MV uses Procedure BFS_MV
(see. Figure 1). If the distances are equal (and Line 2 is reached) then there
exits a shortest $(u,v)$-path without points, that is $u$ and $v$ are in
mutual visibility. Otherwise, $P$ is not a mutual-visibility set (Line 2).

Procedure BFS_MV is a variant of the breadth-first search algorithm that
updates two distance vectors: the distance vector $D$, for the distances of
$v$ with each vertex in the graph, and the distance vector $DP$, for the
distances of $v$ with the points in $P$. These distance vectors are
initialized at Lines 1–1. To track all the visited vertices, a queue $Q$ is
initialized with the vertex $v$. Then, at Line 1, a loop starts, ending when
all the points are visited or there are no more vertices to visit. Within the
loop, the first vertex $u$ in $Q$ is dequeued at Line 1. For each non-visited
neighbor $w$ of $u$ its distance $D[w]$ from $v$ is correctly updated to
$D[u]+1$ (see Line 1). If $w$ is a point, this distance is recorded in $DP$.
Finally, at Line 1, $w$ is enqueued in $Q$ if it is not a point or the
distances must be calculated in $G$ (that is, if $t$ is True). Note that if
$t$ is False and $w$ is a point, $w$ is not enqueued in $Q$ because any
shortest path between $v$ and a point $p\in P$, $p\not=w$, useful to calculate
$d_{G}(v,p)$ and to test the mutual visibility of $v$ and $p$, cannot pass
through $w$. Procedure BFS_MV ends by returning the distance vector $DP$.

Algorithm MV first checks if the points in $P$ are in different connected
components of $G$ at Line 2. In this case $P$ is not a mutual-visibility set
and the algorithm correctly returns False. If all the points are in the same
connected component $H=(V_{H},E_{H})$ (and hence in $G$, if it is connected),
for each point $p$ in $P$ it calculates the distances of $p$ from each other
point $u\in P$, both in $H$ and in $H-P\setminus\\{p,u\\}$ (see Line 2). If at
least one of these distances is different in the two graphs, then Algorithm MV
correctly returns False, otherwise True.

Procedure BFS_MV works in $O(|V|+|E|)$ time, since every vertex and every edge
will be explored in the worst case. Algorithm MV calls Procedure BFS_MV at
most two times for each $p\in P$, then the overall time is $O(|P|(|V|+|E|))$.
$\Box$

##  4 Mutual-visibility set for special graph classes

In this section we study the mutual-visibility number for specific graph
classes and provide some results useful to calculate maximum mutual-visibility
sets in polynomial time in these graphs.

###  4.1 Graph characterization by mutual-visibility number

The following lemma characterizes some graph classes in terms of their mutual-
visibility number.

###### Lemma 4.1

Let $G=(V,E)$ be a graph such that $|V|=n$. Then

  1. 1.

$\mu(G)=1\iff G\sim\overline{K_{n}}$ (if $G$ is connected: $\mu(G)=1\iff G\sim
K_{1}$);

  2. 2.

$\mu(G)=2\iff$ $n>1$ and $G\sim P_{n}$ or $G$ is the disjoint union of at most
$n-1$ path graphs;

  3. 3.

$\mu(G)=|V|\iff G\sim K_{n}$;

  4. 4.

if $G$ is connected and $|V|>2$: $\mu(G)=|E|\iff G\sim K_{1,n-1}$ or $G$ is a
triangle

Proof.

  1. 1.

$(\Rightarrow)$ Since $\mu(G)=1$, $E$ must be empty otherwise there exist
$xy\in E$, and $x$ and $y$ are mutually visible, so $\mu(G)\geq 2$. Hence $G$
is a graph with $n$ vertices and no edges, that is $\overline{K_{n}}$
$(\Leftarrow)$ Since $E$ is empty there are no paths between vertices, then
any mutual-visibility set cannot have more than one point. Hence $\mu(G)=1$.

  2. 2.

$(\Rightarrow)$ Since $\mu(G)=2$, then $n>1$. Assume now by contradiction that
$G$ is not isomorphic to $P_{n}$ and $G$ is not the disjoint union of $n-1$
path graphs. Since at least one connected component of $G$ has at least two
vertices, $\Delta(G)$ cannot be zero. If $\Delta(G)=1$, $G$ would be the
disjoint union of $K_{1}$ and $P_{2}$ graphs, but this is not possible. For
the same reason, if $\Delta(G)=2$ at least one connected component must be a
cycle graph $C_{k}$, for a certain $k$, impossible since $\mu(C_{k})=3$ by
Lemma 2.6. Then $\Delta(G)\geq 3$, but by Lemma 2.5, also in this case
$\mu(G)\geq 3$.
$(\Leftarrow)$ If $n=2$ or all the connect component of $G$ have at most two
vertices, then $\mu(G)=2$. If $n>2$, $\mu(G)=2$ by Lemma 2.6 applied to a
connected component of $G$ with more than two vertices, that must exist since
the connected components are at most $n-1$.

  3. 3.

$(\Rightarrow)$ Since all vertices are in mutual visibility then $G$ is
connected. Moreover each $u,v\in V$ must be adjacent otherwise in any shortest
path connecting them there is at least one vertex, that is a point since the
mutual-visibility set is $V$.
$(\Leftarrow)$ Obvious since all pair of vertices are adjacent and then
mutually visible.

  4. 4.

$(\Rightarrow)$ Since $G$ is connected, $|E|\geq|V|-1$. Moreover
$|V|\geq\mu(G)=|E|$. Then $|E|\leq|V|\leq|E|+1$. If $|V|=|E|=\mu(G)$ then, by
point 3), $G$ is a clique graph and then a triangle (the only case where
$|E|=\frac{n(n-1)}{2}=n=|V|$). If $|V|=|E|+1$, $G$ is a tree with $|V|>2$
vertices and $\mu(G)=|V|-1$ points. Then only one vertex is not a point. It
can be a leaf only if $|V|=3$ (and then $G\sim K_{1,2}$) otherwise there is a
path with at least three points in mutual visibility, a contradiction by Lemma
2.6. For the same reason, when $G\not\sim K_{1,2}$, it is the only vertex that
is not a leaf. Then the graph $G$ is a star with $n$ vertices, that is $G\sim
K_{1,n-1}$.
$(\Leftarrow)$ Obvious if $G$ is a triangle, otherwise, by Lemma 2.5,
$\mu(G)\geq\Delta(G)=deg(v)=|V|-1=|E|$, where $v$ is the center of $G$.
However $\mu(G)$ cannot be larger than $|E|=|V|-1$ otherwise $v$ should be a
point, preventing the mutual visibility among the pendant vertices.

$\Box$

###  4.2 Block graphs and Trees

Figure 3: A block graph. Red vertices are points of the maximum mutual-
visibility set.

A _block graph_ is a graph in which every maximal biconnected subgraph (called
_block_) is a clique (see Figure 3). The next Theorem characterizes the
largest mutual-visibility sets (an then the mutual-visibility number) for
block graphs.

###### Theorem 4.2

Let $G=(V,E)$ be a connected block graph and $X$ the set of its articulation
vertices. $V\setminus X$ is a mutual-visibility set of $G$ and
$\mu(G)=|V\setminus X|$.

Proof. By Lemma 2.4 there exists a maximum mutual-visibility set $P\in M(G)$
without vertices in $X$. To show that $P$ includes all the vertices of $G$ in
$V\setminus X$, consider two of them $u,v$ and the shortest $(u,v)$-path (note
that in block graphs the shortest path between two vertices is unique). If $u$
and $v$ belong to the same block then they are adjacent since a block is a
clique by definition. Otherwise, the shortest $(u,v)$-path passes only through
articulation vertices of $G$, since they are induced paths. Then $u$ and $v$
are mutually visible. By the generality of $u$ and $v$ the lemma holds. $\Box$

An immediate consequence of Theorem 4.2 is the following corollary holding for
trees.

###### Corollary 4.3

Let $T=(V,E)$ be a tree and $L$ the set of its leaves. Then $L$ is a mutual-
visibility set and $\mu(T)=|L|$.

Proof. A tree is a block graph where the blocks are the edges ($K_{2}$
subgraphs) in $E$ and each vertex in $V$ that is not a leaf is an articulation
vertex. Then $L$ is a maximum mutual-visibility set by Theorem 4.2. $\Box$

Figure 1 shows the maximum mutual-visibility set $P$ of a tree. However, the
maximum mutual-visibility set of trees and block graphs is not unique. This is
the case when the removal of an articulation point creates a new component
that is a path $P_{n}$, $n\geq 2$. In that case, we can create several mutual-
visibility sets of maximum size by choosing single vertices of $P_{n}$ for
each of them.

###  4.3 Grids, Tori

Figure 4: On the left: mutual-visibility sets for grid graphs $\Gamma_{1,1}$,
$\Gamma_{1,2}$, $\Gamma_{2,2}$, and $\Gamma_{2,3}$. On the right: two non
isomorphic mutual-visibility sets for $\Gamma_{3,3}$. The size of each mutual-
visibility set determines the mutual-visibility number of the corresponding
graph.

a)  $u$
---
$v$
---
$z$
---
$y$
---
$x$
---
$w$
---
b)

Figure 5: a) The unique maximum mutual-visibility set for $\Gamma_{4,4}$. b) A
maximum mutual-visibility set for $\Gamma_{6,6}$. An extension of this set for
$\Gamma_{7,7}$, when $\Gamma_{6,6}$ is seen as one of its subgraphs, is
obtained by removing points $u$ and $v$ and by adding points $w$, $x$, $y$,
and $z$.

For grid graphs $\Gamma_{m,n}$, Figure 4 represents the mutual-visibility sets
of maximum size for small values of $m$ and $n$, and Theorem 4.4 gives the
values of $\mu(\Gamma_{m,n})$ for $m>3$ and $n>3$. These values are based on
maximum mutual-visibility sets shown in Figure 5. Furthermore, Table 1 shows
the values of $\mu(\Gamma_{m,n})$ for all the possible settings of $m$ and
$n$, $m\leq n$.

$m$ | $n$ | Graph $G$ | $\mu(G)$ | Reference
---|---|---|---|---
1 | 1 | $K_{1}$ | 1 | Lemma 4.1
1 | $n>1$ | $P_{n}$ | 2 | Lemma 2.6
2 | 2 | $C_{4}$ | 3 | Lemma 2.6
2 | $n>2$ | $\Gamma_{2,n}$ | 4 | Lemmas 2.3 and 2.6
3 | 3 | $\Gamma_{3,3}$ | 5 | Figure 4
3 | $n>3$ | $\Gamma_{3,n}$ | 6 | Lemmas 2.3 and 2.6
4 | 4 | $\Gamma_{4,4}$ | 8 | Figure 5
$m>3$ | $n>3$ | $\Gamma_{m,n}$ | $2m$ | Theorem 4.4
Table 1: Values of $\mu(G)$ when $G\sim\Gamma_{m,n}$, for all the possible
value of $m$ and $n$ such that $m\leq n$.

###### Theorem 4.4

Let $\Gamma_{m,n}=P_{m}\times P_{n}$ be a grid graph such that $m>3$ and $n>3$
then

$\mu(\Gamma_{m,n})=2\cdot\min(m,n).$

Proof. Let $P_{m}=(u_{0},u_{1},\ldots,u_{m-1})$ and
$P_{n}=(v_{0},v_{1},\ldots,v_{n-1})$. In each subgraph
$((u_{0},v_{i}),(u_{1},v_{i}),\ldots,(u_{m-1},v_{i}))$, representing the
$i$-row of $\Gamma_{m,n}$, there are at most two points as an immediate
consequence of Lemmas 2.3 and 2.6, since a row is a convex subgraph of
$\Gamma_{m,n}$ and is a path. The same holds for each subgraph
$((u_{j},v_{0}),(u_{j},v_{1}),\ldots,(u_{j},v_{n-1}))$, representing the
$j$-column of the grid. Then $\mu(\Gamma_{m,n})\leq 2\cdot\min(m,n)$. To show
that the equality holds, let $k=\min(m,n)$ and consider a subgraph
$\Gamma_{k,k}$ of $\Gamma_{m,n}$. If $k=4$, the unique maximum mutual-
visibility set of $\Gamma_{4,4}$ is given by:
$(u_{1},v_{0}),(u_{2},v_{0}),(u_{0},v_{1}),(u_{3},v_{1}),(u_{0},v_{2}),(u_{3},v_{2}),(u_{1},v_{3}),(u_{2},v_{3})$
and is represented in Figure 5a. Then $\mu(\Gamma_{k,k})=8$, and since there
are two points for each row and each column, then
$\mu(\Gamma_{m,n})=8=2\cdot\min(m,n)$.

For $k\geq 5$, consider again a grid subgraph $\Gamma_{k,k}$ of $\Gamma_{m,n}$
and the set of points:
$(u_{1},v_{0}),(u_{2},v_{0}),(u_{0},v_{1}),(u_{3},v_{1}),$
$(u_{j-2},v_{j}),(u_{j+2},v_{j})$, for each $j=2,\ldots,k-3$, and
$(u_{k-4},v_{k-2}),(u_{k-1},v_{k-2}),(u_{k-3},v_{k-1}),(u_{k-2},v_{k-1})$.
This set generalizes the solution given for $k=4$ and is represented in Figure
5b. Since there are two points for each row and each column and all the points
are in mutual visibility, then $\mu(\Gamma_{m,n})=2\cdot\min(m,n)$. $\Box$

a)  b)

c)  d)

Figure 6: a) A torus $C_{5}\times C_{5}$. Vertices in red form a maximum
mutual-visibility set. b) The same graph represented as a three-dimentional
torus. The dotted vertex corresponds to the dotted vertex in a). c) A solution
for a torus $T_{12,12}$ such that $\mu(T_{12,12})=3\cdot 12$. d) A solution
for a torus $T_{15,15}$ such that $\mu(T_{15,15})=3\cdot 15$.

For tori $T_{m,n}=C_{m}\times C_{n}$, notice that each copy of $C_{m}$ and
$C_{n}$ is a convex subgraph of $T_{m,n}$. Then, by Lemmas 2.3 and 2.6, we
derive:

###### Corollary 4.5

Let $T_{m,n}=C_{m}\times C_{n}$ be a torus such that $m\geq 3$ and $n\geq 3$
then

$\mu(T_{m,n})\leq 3\cdot\min(m,n).$

However, the problem of finding $m$ and $n$ such that the mutual-visibility
number of $T_{m,n}$ is equal to $3\cdot\min(m,n)$ is still open. In general,
solutions for tori are quite irregular, like that shown in Figure 6a for a
torus $T_{5,5}$, where the upper bound is not reached. It would be interesting
to find the values of $m$ such that $\mu(T_{m,m})$ reaches the upper bound of
Corollary 4.5. There are no mutual-visibility sets for tori $T_{m,m}$ such
that $\mu(T_{m,m})=3\cdot m$, for $m\leq 11$ (result obtained with a
backtracking algorithm that explored a space of $\binom{m}{3}^{m}$ possible
solutions using Algorithm MV as subprocedure). As shown in Figures 6c and 6d,
for $m=12$ and $m=15$ there are tori such that $\mu(T_{12,12})=3\cdot 12$ and
$\mu(T_{15,15})=3\cdot 15$. These solutions were found without the help of a
computer, but a scalable solution, such as the one provided in Theorem 4.4 and
shown in Figure 5 for grids, is not available. With respect to grids, the main
difficulty is due to the fact that, for $m^{\prime}>m$ and $n^{\prime}>n$,
$T_{m,n}$ is not a subgraph of $T_{m^{\prime},n^{\prime}}$, whereas
$\Gamma_{m,n}$ is a subgraph of $\Gamma_{m^{\prime},n^{\prime}}$.

###  4.4 Complete bipartite graphs, cographs and more general graphs

Let us start with a preliminary result about graphs such that almost all the
vertices can be part of a mutual-visibility set.

###### Lemma 4.6

Let $G=(V,E)$ be a graph. Then $\mu(G)\geq|V|-1$ if and only if there exists
$v\in V$ adjacent to each vertex $u\in G-v$ such that $deg_{G-v}(u)<|V|-2$.

Proof. $(\Rightarrow)$ If $\mu(G)=|V|$ then, by Lemma 4.1, $G$ is a clique
graph and then the statement is obviously true. If $\mu(G)=|V|-1$, then there
exists a unique vertex $v$ of $G$ such that $v\not\in P$, where $P\in M(G)$.
Let $u\in G-v$. If $deg_{G-v}(u)=|V|-2$, then $u$ is adjacent to any other
point in $P$, and then is in mutual visibility with it. If
$deg_{G-v}(u)<|V|-2$ then there exists at least a vertex $w\in P$ not adjacent
to $u$. Since $u$ and $w$ are mutually visible, there must exist the path
$(u,v,w)$, then $v$ is adjacent to $u$.

$(\Leftarrow)$ Let $P=V\setminus\\{v\\}$ be a set of points. Let us show that
it is a mutual-visibility set and then that $\mu(G)\geq|V|-1$. Let $u\in P$,
if $deg_{G-v}(u)=|V|-2$, then, as noted above, $u$ is adjacent to any other
vertex in $P$. Otherwise $deg_{G-v}(u)<|V|-2$ and $uv\in E$ by hypothesis. In
this case, let $Q=P\setminus N_{G-v}[u]$ be the set of points in $P$ not
adjacent to $u$. Then for each $w\in Q$, $deg_{G-v}(w)<|V|-2$. Hence $w$ is
adjacent to $v$ and then $u$ and $w$ are in mutual visibility through the
shortest path $(u,v,w)$. By the generality of $u$ and $w$, we have that $P$ is
a mutual-visibility set of $G$. $\Box$

For complete bipartite graphs $K_{m,n}$, Table 2 reports the values of
$\mu(K_{m,n})$ for small values of $m$ and $n$. Note that for
$K_{2,n}\sim\overline{K_{2}}+\overline{K_{n}}$ Lemma 4.6 applies if the vertex
$v$ is taken in the partition $\overline{K_{2}}$. A general result is the
following.

$m$ | $n$ | Graph $G$ | $\mu(G)$ | Reference
---|---|---|---|---
1 | 1 | $P_{2}$ | 2 | Lemma 2.6
1 | $n>1$ | $K_{1,n}$ | n | Corollary 4.3
2 | 2 | $C_{4}$ | 3 | Lemma 2.6
2 | $n>2$ | $K_{2,n}$ | n+1 | Lemma 4.6
$m\geq 3$ | $n\geq 3$ | $K_{m,n}$ | n+m-2 | Theorem 4.7
Table 2: Values of $\mu(G)$ for $G\sim K_{m,n}$ for all the possible value of
$m$ and $n$ such that $m\leq n$.

###### Theorem 4.7

Let $G$ be a complete bipartite graph $K_{m,n}$ such that $m\geq 3$ and $n\geq
3$. Then $\mu(G)=m+n-2$.

Proof. First we notice that $\mu(G)\leq m+n-2$ because $\mu(G)=m+n$ would
imply that $G$ is a clique graph and $\mu(G)=m+n-1$ is not possible because
Lemma 4.6 does not apply. To show that $\mu(G)=m+n-2$, it is sufficient to
find exactly two vertices that are not in the maximum mutual-visibility set
consisting of all other vertices. Since
$G\sim\overline{K_{m}}+\overline{K_{n}}$, we take a vertex $u$ from
$\overline{K_{m}}$ and a vertex $v$ from $\overline{K_{m}}$.

Each point $w$ in $\overline{K_{m}}-v$ is in mutual visibility with other
points in $\overline{K_{m}}-v$ because of vertex $u$. Furthermore, $w$ is
adjacent to points in $\overline{K_{n}}-u$. Symmetrically, points in
$\overline{K_{n}}-u$ are in mutual visibility because of vertex $v$ and are
adjacent to all other points. $\Box$

We can generalize the results of Lemma 4.6 and Theorem 4.7 to more general
graphs resulting from a join operation.

###### Corollary 4.8

Let $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$ be two graphs and
$J=G_{1}+G_{2}=(V,E)$ their join. Then one of the following three cases holds:

  1. 1.

$\mu(J)=|V|\iff G_{1}$ and $G_{2}$ are clique graphs

  2. 2.

$\mu(J)=|V|-1\iff\mu(J)\not=|V|$ and $\mu(G_{1})\geq|V_{1}|-1$ or
$\mu(G_{2})\geq|V_{2}|-1$

  3. 3.

$\mu(J)=|V|-2\iff\mu(G_{1})<|V_{1}|-1$ and $\mu(G_{2})<|V_{2}|-1$.

Proof.

  1. 1.

Obvious by Lemma 4.1.

  2. 2.

$(\Rightarrow)$ If $\mu(J)=|V|-1$ then there is a vertex $v$ that is not a
point. Without loss of generality, let $v\in V_{1}$. Then each pair $x,y$ of
non adjacent points in $G_{1}-v$ must be connected to $v$ to be in mutual
visibility. Hence, by Lemma 4.6, $\mu(G_{1})\geq|V|-1$.
$(\Leftarrow)$ Without loss of generality, assume $\mu(G_{1})\geq|V_{1}|-1$.
If $\mu(G_{1})=|V_{1}|-1$, let $v\in V_{1}$ be the only vertex of $G_{1}$ that
is not a point, otherwise, if $G_{1}$ is a clique graph, let $v$ be any point
of $V_{1}$. Given $\mu(G_{1})\geq|V|-1$, all the points in
$V_{1}\setminus\\{v\\}$ are in mutual visibility. Any pair of points in
$V_{2}$ are in mutual visibility since either adjacent or connected to $v$.
Since any point in $V_{2}$ is adjacent to any point in $V_{1}$, we conclude
that all the points are in mutual visibility and then $\mu(J)=|V|-1$

  3. 3.

Let $v_{1}\in V_{1}$ and $v_{2}\in V_{2}$, and let
$P=V\setminus\\{v_{1},v_{2}\\}$ be the set of points. Then $P$ is a mutual-
visibility set, since any point in $V_{1}\setminus\\{v_{1}\\}$
($V_{2}\setminus\\{v_{2}\\}$, resp.) is adjacent to any point in $V_{2}$
($V_{1}$, resp.) and it is in mutual visibility with any non adjacent point of
$V_{1}$ with a shortest path of length two passing through $v_{2}$ ($v_{1}$,
resp.).

$\Box$

Cographs are well studied in literature and were independently rediscovered
many times, since they represent the class of graphs that can be generated
from $K_{1}$ by complementation and disjoint union (see Theorem 11.3.3 in [6]
for equivalent definitions). As reported in Section 2, a connected cograph can
be obtained starting from $K_{1}$ by a sequence of splittings, that is by
adding a sequence of twin vertices. In [8] the notion of _twin-free subgraph_
was introduced.

###### Definition 4.1

_[8]_ Let $G=(V,E)$ be a graph. The _twin-free subgraph_ ${\mathit{tf}}(G)$ of
$G$ is the subgraph $G[V^{\prime}]$ induced by the largest set of vertices
$V^{\prime}\subseteq V$ such that $G[V^{\prime}]$ has no twins.

Since any induced subgraph of a connected cograph $G$ is a cograph, then
${\mathit{tf}}(G)\sim K_{1}$ and it can be obtained by the polynomial time
Pruning algorithm presented in the same paper. This algorithm removes any
vertex $v$ of $G$ that has a twin, and it applies the same procedure to $G-v$
until a graph without twin vertices is reached. Then it provides a sequence of
vertex removals that corresponds to a sequence of splitting operations to
rebuild the whole $G$ starting from $K_{1}$ and in such a way that $G$ results
the join of two of its subgraphs. Based on this observation we can provide the
following result.

###### Theorem 4.9

Let $G=(V,E)$ be a connected cograph. Then $\mu(G)$ is at least $|V|-2$ and a
maximum mutual-visibility set can be computed in polynomial time.

Proof. Let us show that the vertices of any connected cograph $G=(V,E)$ can be
partitioned into two subsets $V_{1}$ and $V_{2}$ such that
$G=G[V_{1}]+G[V_{2}]$.

Let $v_{1}$ be the only vertex of ${\mathit{tf}}(G)$ and let
$V_{1}=\\{v_{1}\\}$. Since $G$ is connected, the first splitting operation to
rebuild $G$ from $v_{1}$ produces a true twin $v_{2}$ of $v_{1}$ and the
resulting graph is a $K_{2}$. Let $V_{2}=\\{v_{2}\\}$. Now add any vertex
$v_{1}^{\prime}$ ($v_{2}^{\prime}$, resp.) produced by a splitting operation
on a vertex of $V_{1}$ ($V_{2}$, resp.) to $V_{1}$ ($V_{2}$, resp.).
Eventually, each vertex in $V_{1}$ is connected to all the vertices in $V_{2}$
and vice versa. Hence $G=G[V_{1}]+G[V_{2}]$. By applying Corollary 4.8,
$\mu(G)\geq|V|-2$. If all the splitting operations generate true twins, then
$G$ is a clique graph and $\mu(G)=|V|$. By Algorithm MV, we can test if
$V\setminus\\{v\\}$ is a mutual-visibility set of $G$ for some vertex $v\in
V$, and then $\mu(G)=|V|-1$. Otherwise, $\mu(G)=|V|-2$ and
$V\setminus\\{v_{1},v2\\}$ is a mutual-visibility set of $G$. $\Box$

##  5 Conclusions

This paper is a first study on the concepts of mutual-visibility set and
mutual-visibility number. It would be interesting to study the same concepts
for weighted graphs and directed graphs. The latter case is very different
from the studied one since, given a set of points $P$, the relation of
visibility between two points is not symmetric.

From a computational point of view, the Mutual-Visibility problem could be
analyzed with respect to approximability and parameterized complexity.

Given a graph, we have shown some relations between the mutual-visibility
number and both the clique number and the maximum degree of the graph. It
would be interesting to study relations with other invariants, such as the
treewidth or the clique-width of a graph.

Finally, different kinds of visibility can be investigated. For example, the
_single point visibility_ : find the vertex in the graph seen by the largest
set of points.

## Acknowledgments

Figure 3 was adapted from a drawing by David Eppstein, whose remarkable
contributions to Wikipedia have greatly facilitated the writing of this
article.

## References

  * [1] R. Adhikary, K. Bose, M. K. Kundu, and B. Sau.  Mutual visibility by asynchronous robots on infinite grid.  In Algorithms for Sensor Systems - ALGOSENSORS 2018, volume 11410 of Lecture Notes in Computer Science, pages 83–101. Springer, 2018\.
  * [2] A. Aljohani, P. Poudel, and G. Sharma.  Complete visitability for autonomous robots on graphs.  In IEEE International Parallel and Distributed Processing Symposium, IPDPS, pages 733–742. IEEE Computer Society, 2018.
  * [3] A. Aljohani and G. Sharma.  Complete visibility for mobile robots with lights tolerating faults.  Int. J. Netw. Comput., 8(1):32–52, 2018.
  * [4] H.-J. Bandelt and H. M. Mulder.  Distance-hereditary graphs.  J. Comb. Theory Ser. B, 41(2):182–208, 1986.
  * [5] S. Bhagat.  Optimum algorithm for the mutual visibility problem.  In WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, volume 12049 of Lecture Notes in Computer Science, pages 31–42. Springer, 2020.
  * [6] A. Brandstädt, V. B. Le, and J. P. Spinrad.  Graph Classes: A Survey.  Monographs on Discrete Mathematics and Applications. SIAM, 1999.
  * [7] G. A. Di Luna, P. Flocchini, S. G. Chaudhuri, F. Poloni, N. Santoro, and G. Viglietta.  Mutual visibility by luminous robots without collisions.  Inf. Comput., 254:392–418, 2017.
  * [8] G. Di Stefano.  Distance-hereditary comparability graphs.  Discrete Applied Mathematics, 160(18):2669–2680, 2012.
  * [9] F. Harary.  Graph Theory.  Addison-Wesley, 1969.
  * [10] G. H. Hardy and E. M. Wright.  An Introduction to the Theory of Numbers.  Oxford University Press, 2008.
  * [11] R. M. Karp.  Reducibility among combinatorial problems.  In R. E. Miller and J. W. Thatcher, editors, Proceedings of Complexity of Computer Computations, pages 85–103, 1972.
  * [12] P. Poudel, A. Aljohani, and G. Sharma.  Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement.  Theor. Comput. Sci., 850:116–134, 2021.
  * [13] P. Poudel, G. Sharma, and A. Aljohani.  Sublinear-time mutual visibility for fat oblivious robots.  In Proceedings of ICDCN 2019, pages 238–247. ACM, 2019.
  * [14] A. Rosenfeld and A. Y. Wu.  Geodesic convexity in discrete spaces.  Inf. Sci., 80(1-2):127–132, 1994.
  * [15] G. Sharma.  Mutual visibility for robots with lights tolerating light faults.  In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops, pages 829–836. IEEE Computer Society, 2018.
  * [16] R. Steinberg, R. C. Buck, T. Grünwald, and Steenrod.  Three point collinearity (solution to problem 4065).  American Mathematical Monthly, 51(3), 1944.
  * [17] J. J. Sylvester.  Mathematical question 11851.  The Educational Times, 46:156, 1893.
  * [18] A. Y. Wu and A. Rosenfeld.  Geodesic visibility in graphs.  Inf. Sci., 108(1-4):5–12, 1998.