Maximum Rigid Components as Means for Direction-Based Localization in Sensor Networks

Many applications in sensor networks require positional
information of the sensors. Recovering node positions is closely
related to graph realization problems for geometric graphs.
Here, we address the case where nodes have angular information.
Whereas Bruck et al. proved that the corresponding realization
problem together with unit-disk-graph-constraints is NP-hard
[2], we focus on rigid components which allow both efficient
identification and fast, unique realizations.
Our technique allows to identify maximum rigid components in
graphs with partially known rigid components using a reduction
to maximum flow problems. This approach is analyzed for the
two-dimensional case, but can easily be extended to higher
dimensions.