Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data

Compound graphs, a frequently encountered type of data set, have a hierarchical tree structure with parent-child relations (‘inclusion’ relations) and non-hierarchical relations between leaf nodes (‘adjacency’ relations). Such datasets are common in software systems, social networks, and citation networks, amongst other scenarios. Visualizing these data sets is difficult because the addition of adjacency relations in any existing tree visualization method results in visual clutter. Moreover, using a generic visualization approach for these yields poor results too because of the difficulty of separating the inclusion and the adjacency relations. The existing methods for visualizing compound graphs and compound directed graphs (hereafter collectively referred to as compound (di)graphs) have numerous shortcomings, such as the inefficient usage of the available space (radial and balloon layout-based tree visualization techniques), the lack of flexibility (methods for drawing clustered graphs), inability to scale well for compound (di)graphs with large hierarchies (ArcTree-based visualization), unintuitive presentation (matrix view based methods), and excessive clutter because of several “extra routing nodes” introduced by binary splits (flow map layouts). Drawing inspiration from the management and routing of electrical and network cables, this paper presents hierarchical edge bundles for visualizing compound (di)graphs. It is a flexible and an intuitive technique that can be used in conjunction with existing tree visualization methods and reduces visual clutter when working with a high count of adjacency relations.

The key idea behind hierarchical edge bundling is to use, instead of straight lines between a pair of points which are connected, a method to interpolate between the points in the hierarchical structure of the compound (di)graphs, resulting in a visualization where all connection which share a similar path get bundled together. These points, known as the control points, together make up the control polygon, and are spread from the starting point to the ending point through their least common ancestor (LCA). Piece-wise cubic B-splines are used to visualize the curves, and they are chosen over Bézier curves (because they do not have sufficient local control) and Beta-splines (because they yield inferior bundling behavior). For straightening a spline curve, either the control polygon (by straightening each of its control points) or each spline point can be straightened. Since the difference in the outputs of these two methods is inconspicuous, the former is chosen because of the relatively low computation cost. In order to prevent connections between sibling leaf nodes curving towards their shared parent node, the LCA is removed from the original control polygon of the spline curve. However, this can be problematic in scenarios where the original control polygon contains only 3 control points, and therefore, the LCA is only permitted to be removed if there are more than 3 control points in the original control polygon. For rendering issues where long curves tend to obscure shorter curves since the latter only occupy a small area on the screen, the shorter curves can be drawn atop the long curves to avoid this. Moreover, alpha blending is used to easily distinguish “individual curves or subbundles within a bundle”, and RGB interpolated color gradient is used to indicate the direction of connections. This method was used to visualize the hierarchically organized software system of a Philips medical scanner with 3 hierarchy levels, 284 nodes, and 1,011 adjacency relations at a real-time speed ($>=10$ frames per second). Qualitative results included in the paper show the difficulty of discerning connectivity information in non-bundled visualizations, which are much easier to perceive in the bundled visualization. Informal user studies conducted with researchers and graduate students from the academia with relevant background and with industry representatives from 2 companies showed that users concur upon the superiority of bundled visualization techniques for gaining quick insights in the adjacency relations, where the bundles allowed interpretation of implicit relations between the items at higher hierarchical levels while providing lowe-level relation information simultaneously. Moreover, the thickness of bundles indicated the hierarchical nature of the relations, with thick bundles at higher levels fanning out to thinner ones for lower level relations. Radial layout was preferred over the balloon layout, with the users considering the rooted and the slide-and-dice treemap layouts as “less pleasing”. Finally, the interface also provided an option to control the bundling strength to enhance bundle-based interaction.

This paper introduces hierarchical edge bundles for visualizing adjacent relations in compound (di)graphs in real-time that results in improved interpretability of adjacency relations. This method, along with the radial layout, are quite popular in software system visualizations, and are collectively known as hierarchical circular bundle views. The paper is written with great clarity of detail, and the accompanying visualizations make all the design choices and the consequences easy to follow. As admitted in the paper, the method results in bundle overlap in scenarios with “a large number of collinear nodes”, compromising the readability of the visualizations. Another potential shortcoming is that with the radial layout, the current setup allows for implicit relations between parent nodes, and there is no way to explicitly model relations between parent nodes.