  Classical results in sparse recovery guarantee the exact reconstruction of
$s$-sparse signals under assumptions on the dictionary that are either too
strong or NP-hard to check. Moreover, such results may be pessimistic in
practice since they are based on a worst-case analysis. In this paper, we
consider the sparse recovery of signals defined over a graph, for which the
dictionary takes the form of an incidence matrix. We derive necessary and
sufficient conditions for sparse recovery, which depend on properties of the
cycles of the graph that can be checked in polynomial time. We also derive
support-dependent conditions for sparse recovery that depend only on the
intersection of the cycles of the graph with the support of the signal.
Finally, we exploit sparsity properties on the measurements and the structure
of incidence matrices to propose a specialized sub-graph-based recovery
algorithm that outperforms the standard $\ell_1$-minimization approach.
