A User Study in Similarity Measures for Graph Drawing

Abstract

The need for a similarity measure for comparing two drawings of graphs arises in problems such as interactive graph drawing and the indexing or browsing of large sets of graphs. Many applications have been based on intuitive ideas of what makes two drawings look similar - for example, the idea that vertex positions should not change much. In this paper, we formally define several of these intuitive ideas of similarity and present the results of a user study designed to evaluate how well these measures reflect human perception of similarity.