The paper addresses the problem of robust sensor placement for large scale linear time-invariant systems. Two different concepts of robustness are analyzed: 1) the robustness with respect to one sensor failure, and 2) the robustness with respect to one link failure. We show that both aforementioned problems can be posed as certain set cover problems, a classical problem for which many solutions exist. In addition we formulate and partially solve the minimum robust sensor placement, a much harder problem. By relating robust sensor placement to spanning trees associated with the dynamical system structure, readily computable upper and lower bounds are provided on the size of such robust placement configurations. Finally, some illustrative examples are presented.