A long trip in the charming world of graphs for Pattern Recognition

•The paper is a historical survey of graph-based methodologies in Pattern Recognition.•The scientific evolution of graph based methods over their history is discussed.•The paper analyses the trend of reusing vector space methods for graphs.•Three distinctive periods are recognized wrt how the vector-graph gap is filled.•Reserve a ticket for a historical trip in this charming world and discover it soon!.

This paper is a historical overview of graph-based methodologies in Pattern Recognition in the last 40 years; history is interpreted with the aim of recognizing the rationale inspiring the papers published in these years, so as to roughly classify them. Despite the extent of scientific production in this field, it is possible to identify three historical periods, each having its own connotation common to most of the corresponding papers, which are called here as the pure, the impure and extreme periods.