Rigidity and Persistence of Directed Graphs




Hendrickx, Julien M
Anderson, Brian
Blondel, Vincent D

Journal Title

Journal ISSN

Volume Title


Institute of Electrical and Electronics Engineers (IEEE Inc)


Motivated by [1], [2] and [3], we consider here formations of autonomous agents in a 2-dimensional space. Each agent tries to maintain its distances toward a pre-specified group of other agents constant, and the problem is to determine if one can guarantee that the structure of the formation will persist, i.e., if the distance between any pair of agents will remain constant. A natural way to represent such a formation is to use a directed graph. We provide a theoretical framework for this problem, and give a formal definition of persistent graphs (a graph is persistent if almost all corresponding agents formations persist). Note that although persistence is related to rigidity (concerning which much is known [4]), these are two distinct notions. We then derive various properties of persistent graphs, and give a combinatorial criterion to decide persistence. We also define the notion of minimal persistence (persistence with least number of edges), and eventually, we apply these notion to the interesting special case of cycle-free graphs.



Keywords: Directed graphs; Persistence; Persistent graphs; Combinatorial mathematics; Intelligent agents; Optimization; Problem solving; Graph theory



Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference 2005


Conference paper

Book Title

Entity type

Access Statement

License Rights



Restricted until