# Rigidity and Persistence of Directed Graphs

## Date

2005

## Authors

Hendrickx, Julien M

Anderson, Brian

Blondel, Vincent D

## Journal Title

## Journal ISSN

## Volume Title

## Publisher

Institute of Electrical and Electronics Engineers (IEEE Inc)

## Abstract

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.

## Description

## Keywords

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

## Citation

## Collections

## Source

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

## Type

Conference paper

## Book Title

## Entity type

## Access Statement

## License Rights

## DOI

10.1109/CDC.2005.1582484