In the present study, an incremental variational inequality is described for frictional contact problems with material non linear behavior assumed to be elasto-plastic for the contacting bodies. On the contacting boundaries, the constraint conditions include noninterpenetration along the normal direction of the contact boundary and Coulomb friction law in the sliding direction. After numerical discretization using the finite element method, an effective linear complementary formulation is then established with two unknown variables and two complementary variables for each contact nodal pair. The proposed developments permit a reduced number of unknown variables which are chosen as the gap function for the normal direction and the norm of the incremental sliding displacements for the tangential direction; and the complementary variables are taken as the normal contact forces and slack variables in the tangential directions. The resulting linear complementary equations are then solved employing an explicit Conjugate Gradient Based Projection (CGBP) method in conjunction with a generalized Newton-Raphson iteration procedure to account.for the material nonlinear behavior. The methodology is valid for three-dimensional frictional contact representations; however, for purposes of illustration of the proposed approaches, attention is confined to applications involving two-dimensional static elasto-plastic problems under small deformation. Numerical examples are presented which clearly show that the developments satisfy the problem physics and contact conditions with features to include high accuracy and reduced computational costs.