  A new framework is proposed to study rank-structured matrices arising from
discretizations of 2D and 3D elliptic operators. In particular, we introduce
the notion of a graph-induced rank structure (GIRS) which aims to capture the
fine low rank structures which appear in sparse matrices and their inverses in
terms of the adjacency graph $\mathbb{G}$. We show that the GIRS property is
invariant under inversion, and hence any effective representation of the
inverse of GIRS matrices would lead to effective solvers. Starting with the
observation that sequentially semi-separable (SSS) matrices form a good
candidate for representing GIRS matrices on the line graph, we propose two
extensions of SSS matrices to arbitrary graphs: Dewilde-van der Veen (DV)
representations and $\mathbb{G}$-semi-separable ($\mathbb{G}$-SS)
representations. It is shown that both these representations come naturally
equipped with fast solvers where the solve complexity is commensurate to fast
sparse Gaussian elimination on the graph $\mathbb{G}$, and $\mathbb{G}$-SS
representations have a linear time multiplication algorithm. We show the
construction of these representations to be highly nontrivial by determining
the minimal $\mathbb{G}$-SS representation for the cycle graph $\mathbb{G}$. To
obtain a minimal representation, we solve an exotic variant of a low-rank
completion problem.
