In this paper a new graph based approach referred to as Fisher Locality Preserving Projections (FLPP) is proposed for efficient palmprint recognition. The technique employs two graphs with the first being used to characterize the within-class compactness and the second being dedicated to the augmentation of the between-class separability. In addition, a Passband Discrete Cosine Transform (PBDCT) is used for dimensionality reduction and feature extraction. This process makes the palmprint features more robust against inherent degradations of palmprint images. By applying an FLPP, only the most discriminant and stable palmprint features are retained. Since the palmprint features are derived from the principal lines, wrinkles and texture along the palm area one should carefully consider this fact when performing the feature extraction process in order to enhance recognition accuracy. To address this problem, an improved region of interest (ROI) extraction algorithm is introduced. This algorithm allows the efficient extraction of the whole palm area ignoring all the undesirable parts, such as the fingers and background. The experimental results demonstrate the effectiveness of the proposed method even for highly degraded palmprint images. An Equal Error Rate (EER) of 0.48% has been obtained on a database of 4000 palmprint images.