This paper surveys some of the recent research on the applications of the algebraic and combinatorial properties of Gaussian elimination on sparse matrices. Keywords: sparse matrix, Gaussian elimination, graph theory, computational complexity, triangulation, optimal ordering, optimum ordering, grid graph, band matrix.