Confluent Drawings
This program is an implementation of the paper "Towards Unambiguous Edge Bundling: Investigating Confluent Drawings for
Network Visualization" by Bach et al.
Idea
Especially with dense graphs it can be difficult to see which nodes are connected to another, because there are simply too many edges. To increase the perceivability of the graph, its edges can be bundled. Confluent Drawings are a graph representation where edges are bundled, if they have target and source nodes in common. To accomplish this, the powergraph is computed where nodes are put together in one group depending on their target nodes. For each group an additional node is created. It is connected with the nodes of its group and the group's target nodes or sub-group nodes. This leads to a so called routing graph, where the group nodes are the routing nodes. For each edge of the original graph, the source and target nodes are connected by finding the shortest path in the routing graph. The new edges are then drawn as b-splines which use the routing nodes as control points. This results in a Confluent Drawing. However, it is possible that there are certain artifacts which lead to crossing edges in the Confluent Drawing. They can be avoided by splitting routing nodes, which have more than one incoming and more than one outgoing edge. Routing the paths over those splitted nodes leads to a Confluent Drawing without crossing artifacts.
Program
In the program, a graph can be chosen from a list. The graph, as well as the routing graph, the Confluent Drawing and the Confluent Drawing without crossing artifacts are then displayed. In the top left corners the number of nodes and edges can be seen. Each of the graphs can be zoomed and the nodes can be dragged around. Also the whole graphs can be dragged inside their frames by clicking and dragging it anywhere in the frame. Routing nodes are displayed in black. Edges in the routing graph are never routed through a normal graph node. On mouseover, the labels of the nodes are shown. A node has the same colour in all of the graphs to make it easier to spot the node and its position when observing the different graphs.
Implementation
The program is written in JavaScript and uses the D3 library and WebCoLa library for the graph layout and powergraph group computation.
Links
References
Paper
Bach, B., Riche, N. H., Hurter, C., Marriott, K., & Dwyer, T. (2017). Towards unambiguous
edge bundling: Investigating confluent drawings for network visualization. IEEE transactions on
visualization and computer graphics, 23(1), 541-550.
Graphs
T. Dwyer, N. H. Riche, K. Marriott, and C. Mears. Edge compression techniques for visualization of dense directed graphs. IEEE Transactions on Visualization and Computer Graphics, 19(12):2596–2605, 2013.
D. Lusseau et al., "The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations." Behavioral Ecology and Sociobiology 54(4), 396-405 (2003).
W. de Nooy, A. Mrvar, and V. Batagelj, "Exploratory Social Network Analysis with Pajek." Cambridge University Press, Chapter 2. (2004)
D. E. Knuth, "The Stanford GraphBase: A Platform for Combinatorial Computing." Addison-Wesley, Reading, MA (1993).
Libraries