Confluent* Drawings by Hierarchical Clustering

Zheng JX, Pawar S, Goodman DFM
Graph Drawing and Network Visualization (2018)
doi: 10.1007/978-3-030-04414-5
26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, Proceedings


Recently an edge bundling technique known as confluent* drawing was applied to general graphs by Bach et al. (2017) by leveraging power graph decomposition (a form of edge compression that groups similar vertices together, merging edges shared among group members). We explore the technique further by demonstrating the equivalence between confluent drawing and the hierarchical edge bundling of Holten (2006), thereby opening the door for existing hierarchical clustering algorithms to be used instead of power graphs to produce confluent drawings for general graphs. We investigate various popular hierarchical clustering methods, and present a qualitative experimental comparison between them. We also introduce a new distance measure for agglomerative clustering that outperforms previous measures, and make recommendations for using the method in practice.