On the faithfulness of graph visualizations

Readability criteria have been commonly used to measure the quality of graph visualizations. In this paper we argue that readability criteria, while necessary, are not sufficient. We propose a new kind of criterion, generically termed faithfulness, for evaluating graph layout methods. We propose a general model for quantifying faithfulness, and contrast it with the well established readability criteria. We use examples of multidimensional scaling, edge bundling and several other visualization metaphors (including matrix-based and map-based visualizations) to illustrate faithfulness.