Classifying and modeling texture images, especially those with significant rotation, illumination, scale, and view-point variations, is a hot topic in the computer vision field. Inspired by local graph structure (LGS), local ternary patterns (LTP), and their variants, this paper proposes a novel image feature descriptor for texture and material classification, which we call Petersen Graph Multi-Orientation based Multi-Scale Ternary Pattern (PGMO-MSTP). PGMO-MSTP is a histogram representation that efficiently encodes the joint information within an image across feature and scale spaces, exploiting the concepts of both LTP-like and LGS-like descriptors, in order to overcome the shortcomings of these approaches. We first designed two single-scale horizontal and vertical Petersen Graph-based Ternary Pattern descriptors ( PGTPh and PGTPv ). The essence of PGTPh and PGTPv is to encode each 5×5 image patch, extending the ideas of the LTP and LGS concepts, according to relationships between pixels sampled in a variety of spatial arrangements (i.e., up, down, left, and right) of Petersen graph-shaped oriented sampling structures. The histograms obtained from the single-scale descriptors PGTPh and PGTPv are then combined, in order to build the effective multi-scale PGMO-MSTP model. Extensive experiments are conducted on sixteen challenging texture data sets, demonstrating that PGMO-MSTP can outperform state-of-the-art handcrafted texture descriptors and deep learning-based feature extraction approaches. Moreover, a statistical comparison based on the Wilcoxon signed rank test demonstrates that PGMO-MSTP performed the best over all tested data sets.