When is it easy to invert a sparse matrix?

One such case is if the sparse matrix is banded. For example, tridiagonal linear systems can be solved in linear time using Thomas' algorithm. For small bandwidths, you can find an algorithm of linear time cost. Note that as the bandwidth grows, the hidden coefficient grows too.

The literature on the topic is active and there are many characterizations as far as I see, some of which you have already found. Maybe you should add reference-request as a tag.

There are many ways to solve systems with sparse matrices, so there is no way to answer this definitively and exhaust all possibilities. I'll add Krylov methods as one answer though. Many Krylov methods achieve fast results under the right conditions.

The conditions for Krylov methods to perform well have been asked here before. Every Krylov solver is a little bit different, but I'll give GMRES as an example.

For GMRES if your input matrix has the following properties:

1. Normal (or approximately normal)
2. Eigenvalues not too close to 0
3. Eigenvalues clustering (easily identified "groups" of eigenvalues all close together)

then GMRES will likely converge very rapidly regardless of the right-hand-side vector. Note that the conditions (1) through (3) actually don't say anything about sparsity of the matrix at all, but usually since sparse matrix-vector product is cheap the GMRES algorithm can be well suited to the sparse case.