Connectivity graphs as models of local interactions

In this paper, we study graphs that arise from certain sensory and communication limitations on the local interactions in multi-agent systems. In particular, we show that the set of graphs that can represent formations corresponds to a proper subset of all graphs and we denote such graphs as connectivity graphs. These graphs have a special structure that allows them to be composed from a small number of atomic generators using a certain kind of graph amalgamation. This structure moreover allows us to give connectivity graphs a topological characterization in terms of their simplicial complexes. Finally, we outline some applications of this topological characterization to the construction of decentralized algorithms.