Mutual visibility in graphs

Let G = (V, E) be a graph and P subset of V a set of points. Two points are mutually visible if there is a shortest path between them without further points. Pis 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. (C) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper studies mutual visibility in undirected graphs and introduces the Mutual-Visibility problem. It is shown that the Mutual-Visibility problem is NP-complete, but checking whether a given set of points is a mutual-visibility set is solvable in polynomial time. Special classes of graphs, like block graphs, trees, grids, tori, complete bipartite graphs, and cographs, are studied in terms of mutual-visibility sets and numbers.