TR-2009-05

Rigid and Globally Rigid Graphs with Pinned Vertices

Tibor Jordán



Abstract

We consider rigid and globally rigid bar-and-joint frameworks (resp. graphs) in which some joints (resp. vertices) are pinned down and hence their positions are fixed. We give an overview of some old and new results of this branch of combinatorial rigidity with an emphasis on the related optimization problems.
 
In one of these problems the goal is to find a set P of vertices of minimum total cost for which the positions of all vertices become uniquely determined when P is pinned down. For this problem, which is motivated by the localization problem in wireless sensor networks, we give a constant factor approximation algorithm.


Bibtex entry:

@techreport{egres-09-05,
AUTHOR = {Jord{\'a}n, Tibor},
TITLE = {Rigid and Globally Rigid Graphs with Pinned Vertices},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2009},
NUMBER = {TR-2009-05}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!