The application of some recently proposed algebraic multilevel methods for the solution of two-dimensional finite element problems on nonuniform meshes is studied. The locally refined meshes are created by the newest vertex mesh refinement method. After the introduction of this refinement technique it is shown that, by combining levels of refinement, a preconditioner of optimal order can be constructed for the case of local refinement along a line. Its relative condition number is accurately estimated. Numerical tests demonstrating the performance of the proposed preconditioners will be reported in a forthcoming paper.