Graphs give a universal and flexible framework to describe the structure and relationship between objects. They are useful in many different application domains like pattern recognition, computer vision and image analysis. In the image analysis context, images can be repre- sented as graphs such that the nodes describe the features and the edges describe their relations. In this paper we, firstly, review the graph-based representations commonly used in the literature. Secondly, we discuss, empirically, the choice of a graph-based representation on three different image databases and show that the representation has a real impact on the method performances and experimental results in the literature on graph performance evaluation for similarity measures should be considered carefully.