Abstract
Graphs are a powerful and versatile tool useful in various sub-fields of science and engineering. In many applications, for example, in pattern recognition and computer vision, it is required to measure the similarity of objects. When graphs are used for the representation of structured objects, then the problem of measuring object similarity turns into the problem of computing the similarity of graphs, which is also known as graph matching. In this paper, similarity measures on graphs and related algorithms will be reviewed. In addition, theoretical work showing various relations between different similarity measures will be discussed. Other topics to be addressed include graph clustering and efficient indexing of large databases of graphs.