Maximum Rigid Components as Means for Direction-Based Localization in Sensor Networks
Bastian Katz1
, Marco Gaertler1
and Dorothea Wagner1 
| (1) |
Faculty of Informatics, Universität Karlsruhe (TH), Germany |
Abstract
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

-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.
This work was partially supported by the German Research Foundation (DFG) within the Research Training Group GRK 1194 ”Self-organizing
Sensor-Actuator Networks”, and under grant WA 654/14-3 and by EU under grant DELIS (contract no. 001907).
References secured to subscribers.