The mutual-visibility problem in a graph asks for the cardinality of a largest set of vertices so that for any two vertices there is a shortest -path whose internal vertices are all not in . Variations of this problem are known, based on the extension of the visibility property of vertices that are in and/or outside . It is known that solving the mutual-visibility problem in all its variations is NP-complete, whereas it has been shown that there are exact formulas for special graph classes like paths, cycles, blocks, cographs, and for the Cartesian product of some simple graphs like paths, cliques and cycles. In this paper, we study the (variations of) mutual-visibility problem in the context of distance-hereditary graphs. In particular, we introduce the direct canonical decomposition of a graph as a tool for defining useful structural properties of the graphs studied. Then, we show that such properties allow us to devise a linear-time algorithm for solving all the variants of the mutual-visibility problem for distance-hereditary graphs. In turn, this allowed us to show that a recently posed conjecture about the total mutual-visibility number of distance-hereditary graphs holds.

Robots with very weak capabilities placed on the vertices of a graph are required to move toward a common vertex from where they do not move anymore. The task is known as the Gathering problem and it has been extensively studied in the last decade with respect to both general graphs and specific topologies. Most of the challenges faced are due to possible isometries observable from the placement of the robots with respect to the underlying topology. Rings, Grids, and Complete graphs are just a few examples of very regular topologies where the placement of the robots and suitable movements are crucial for succeeding in Gathering. Here we are interested in understanding what can be done in Butterfly graphs where really many isometries are present and most importantly unavoidable by any movement. We propose a Gathering algorithm for the so-called leader configurations, i.e., those where the initial placement of the robots admits the detection (and election) of one robot as the leader. We introduce a non-trivial technique to elect the leader which is of its own interest. We also prove that the proposed Gathering algorithm is asymptotically optimal in terms of synchronous rounds required.

Let G be a graph and X⊆V(G). Then X is a mutual-visibility set if each pair of vertices from X is connected by a geodesic with no internal vertex in X. The mutual-visibility number μ(G) of G is the cardinality of a largest mutual-visibility set. In this paper, the mutual-visibility number of strong product graphs is investigated. As a tool for this, total mutual-visibility sets are introduced. Along the way, basic properties of such sets are presented. The (total) mutual-visibility number of strong products is bounded from below in two ways, and determined exactly for strong grids of arbitrary dimension. Strong prisms are studied separately and a couple of tight bounds for their mutual-visibility number are given.

In the theoretical studies on distributed algorithms for swarm robotics, the complexity and capabilities of the robots are usually reduced to their minimum. Recently, the Moblot model has been introduced in order to deal with robots considered silent, anonymous, and oblivious but capable to aggregate into more complex structures, called molecules. We study the case where robots move along a graph based on a square lattice and we formally define the Molecular Pattern Formation (MPF) problem, where a specific configuration of robots assembled into molecules must be reached. As a preliminary general result, we provide a necessary condition for its solvability. Then, we actually show that dealing with molecules can resolve in some cases the symmetry breaking issue on grids where otherwise robots cannot. Finally, we introduce an interesting case study, representative of the MPF problem, in which the molecules can be formed by the set of the seven tetrominoes (aka Tetris blocks). We provide a complete characterization of this specific problem, providing a distributed algorithm able to form a molecular pattern whenever the necessary condition for the solvability of MPF is verified.

The concept of mutual-visibility in graphs has been recently introduced. If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u, v-path P such that V(P) ∩ X ⊆ {u, v}. If every two vertices from X are X-visible, then X is a mutual-visibility set. The mutual-visibility number of G is the cardinality of a largest mutual-visibility set of G. It is known that computing the mutual-visibility number of a graph is NP-complete, whereas it has been shown that there are exact formulas for special graph classes like paths, cycles, blocks, cographs, and grids. In this paper, we study the mutual-visibility in distance-hereditary graphs and show that the mutual-visibility number can be computed in linear time for this class.

The Mutual Visibility is a well-known problem in the context of mobile robots. For a set of n robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robots are collinear. For robots moving on graphs, we consider the Geodesic Mutual Visibility (GMV) problem. Robots move along the edges of the graph, without collisions, so as to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means that there is a shortest path (i.e., a “geodesic”) between each pair of robots along which no other robots reside. We study this problem in the context of trees and (finite or infinite) square grids, for robots operating under the standard Look-Compute-Move model. In both scenarios, we provide resolution algorithms along with formal correctness proofs, highlighting the most relevant peculiarities arising within the different contexts, while optimizing the time complexity.

If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u,v-path P such that V(P)∩X⊆{u,v}. If each two vertices from X are X-visible, then X is a mutual-visibility set. The mutual-visibility number of G is the cardinality of a largest mutual-visibility set of G and has been already investigated. In this paper a variety of mutual-visibility problems is introduced based on which natural pairs of vertices are required to be X-visible. This yields the total, the dual, and the outer mutual-visibility numbers. We first show that these graph invariants are related to each other and to the classical mutual-visibility number, and then we prove that the three newly introduced mutual-visibility problems are computationally difficult. According to this result, we compute or bound their values for several graphs classes that include for instance grid graphs and tori. We conclude the study by presenting some inter-comparison between the values of such parameters, which is based on the computations we made for some specific families.

The study of mobile entities, called robots, that have to accomplish global tasks on the basis of local information has attracted many researchers. A well-known scenario is that in which robots operate in Look-Compute-Move (LCM) computational cycles. In each cycle, a robot takes a snapshot of the environment (Look phase), then executes a distributed algorithm on the basis of the obtained snapshot (Compute phase), and finally moves toward a desired destination, if any (Move phase). LCM cycles might be subject to different temporal constraints dictated by the considered schedule. The classic models for the activation and synchronization of mobile robots are the fully-synchronous, semi-synchronous, and asynchronous models. The three models have been shown to constitute a hierarchy, that is fully-synchronous robots can accomplish more tasks than semi-synchronous robots that in turn can accomplish more tasks than asynchronous robots. The computational power of robots based on the different models has been extensively investigated, revealing a big gap between asynchronous robots and the other models. For many problems it is still not known whether the synchronization is crucial for designing resolution algorithms or not. In order to better understand the asynchronous case, here we propose further models referred to as semi-asynchronous, showing that for robots moving on graphs, semi-synchronous robots can accomplish more tasks than semi-asynchronous robots that in turn can accomplish more tasks than asynchronous robots. Whether the same strict hierarchy also holds for robots moving on the Euclidean plane remains open, however our investigation reveals interesting consequences that may help in better characterizing the computational power of robots with respect to the different synchronization models.

We present results on the design of a visual interaction environment for geographic information systems. In our model a database is a spatially related collection of regions with features, hierarchically organized as a nested partition. We envision an exploration of the database where, starting from an abstract view, more detailed information on subregions and/or features is successively disclosed on demand and visualized in a fish-eye view fashion. The interaction process is a sequence of views on the database, displayed by maps preserving topological properties. Efficient navigation requires the adoption of topological invariants for representing such partitions. Since each interaction step modifies only a portion of the current invariant, the definition of our interaction primitives is based on an efficient incremental approach (the current topological invariant is updated by exploiting knowledge coming from previous steps, instead of recomputing always everything from scratch).

In this paper, we provide low-congested interval routing schemes (IRS) for some common interconnection networks such as butterflies, wrapped butterflies, and cube-connected cycles. In particular, by exploiting their hypercubelike structure, we show that 1-IRS and 2-IRS are already sufficient to get schemes with a congestion which is at most c times the optimal one, for low constant values of c. All such schemes have also a small dilation proportional to the diameter. Moreover, a new lower bound on the congestion achievable by schemes for butterfly networks is provided, which improves upon the best previously known one [25]. © 2000 John Wiley & Sons, Inc.