Recent developments in graph matching

Graphs are a powerful and versatile tool useful in various subfields 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 are reviewed. Also theoretical work showing various relations between different similarity measures is discussed. Other topics to be addressed include graph clustering and efficient indexing of large databases of graphs.