A Survey of Multiple Tree Visualisation
Author Contact Details
School of Computing
10 Colinton Road
Tel: +44 131 455 2749
School of Computing
10 Colinton Road
Tel: +44 131 455 2772
This paper summarises the state-of-the-art in multiple tree visualisations. It discusses the
spectrum of current representation techniques used on single trees, pairs of trees and finally
multiple trees, in order to identify which representations are best suited to particular tasks and
to find gaps in the representation space where opportunities for future multiple tree
visualisation research may exist. The application areas from where multiple tree data are
derived are enumerated, and the distinct structures that multiple trees make in combination
with each other and the effect on subsequent approaches to their visualisation are discussed,
along with the basic high-level goals of existing multiple tree visualisations.
Multiple trees, layout techniques, survey
Tree visualisation has been one of the staples of Information Visualisation (IV) since its
inception, inspiring myriad variations in terms of layout styles and interaction techniques. The
bulk of this research has been performed on single tree instances, yet as more data is produced
that requires users to navigate through multiple tree classifications or to understand the
complex interaction of several tree structures, an increasing number of situations call for the
analysis and comparison of multiple tree structures - tasks to which IV techniques can also be
There have been attempts to categorise tree visualisation literature by criteria such as layout
style, interaction technique and data type in previous survey papers. Again, however, most of
them concern themselves with only the visualisation of single trees. Noik1 provides an early
survey and classification system of graph presentation techniques, including trees, primarily
focused on classifying by focusing and filtering attributes, and is too early for multiple tree
visualisations to have registered in the literature. Later, Herman et al.2 surveyed the graph
visualisation literature from an information visualisation perspective, grouping techniques by
interaction and layout style rather than through the more formal algorithmic perspective
favoured in traditional graph drawing domains. Their examples cover mostly restricted graphs
including trees along with directed acyclic graphs (DAGs) and other graphs derived from
general graphs. As with Noik, the survey does not include any examples of multiple tree
visualisations due to the survey now being several years old. More recently, PhD and
Masters’ theses regarding tree visualisation such as Nguyen3 and Nussbaumer4 include
background chapters summarising the state-of-the-art at the time, but again cover only single
Graham’s thesis5 includes a background chapter on multiple tree visualisation as it existed in
2001 but, as much of the work on the topic has occurred since then, recent work has not yet
been summarised or explored comprehensively. As such, this paper aims to act as a survey
paper for the field, collecting and summarising the current state-of-the-art in multiple tree
visualisation. We begin by describing the areas where multiple tree data is to be found and the
different types of structure formed by overlapping trees. Then we give a brief summary of
single tree visualisation before moving on to two-tree and multiple tree visualisations in
greater detail, discussing the techniques used to display and interact with these structures and
their associated advantages and disadvantages. From the review of such work we summarise
the basic tasks that multiple tree visualisations are attempting to allow users to perform.
The primary sources of data, and therefore application areas, for multiple tree visualisations
are bioinformatics, faceted classifications, schema/ontology mapping and software
development. These are fields with a common thread of re-classification or re-categorisation
which produce in some form or other multiple tree data sets which users are interested in
analysing for finding patterns, editing relationships or using as mechanisms for querying data.
In bioinformatics, analyses of species relationships produce multiple conflicting phylogenies
and taxonomies over the same or overlapping groups of species; each instance being a model
of evolutionary or morphological similarity between those species. Constantly, new
classifications are produced over previously classified data due to the discovery of new
species and the development of new analytic techniques. Currently, reconciling such
structures relies on producing consensus trees6 which accents shared structure but omits
unique details of individual tree structures in the process, even though practitioners regard
each conflicting classification as legitimate in its own right.
Hierarchically-faceted classifications7 occur when items can be filtered by multiple
hierarchically-organised attributes, with the most common example being internet shopping
sites where products are classified by price, type, maker etc. We must be careful to
distinguish between flat facets – those facets that group a set of objects according to one level
of categorisation e.g. manufacturer (Dell, HP, Viglen etc) – and hierarchical facets which
have multiple levels of categorisation – an ‘operating systems’ facet can have Windows, Mac
OS and Linux at the top-level, and in turn Windows can have sub-categorisations of Vista,
XP, 98, 95 etc. It is the hierarchical facets that are of interest to us, as a collection of such
facets can be understood as a collection of multiple, overlapping trees.
Hierarchical facets are similar to biological taxonomies in that multiple hierarchies are
constructed over a set of objects, though there are two distinct differences. Firstly, each
faceted classification will include all the objects in a set, even if some objects end up being
assigned to an ‘unknown’ or ‘other’ group within a classification, whereas biological
taxonomies may only roughly overlap on the object set rather than match completely.
Secondly the problem for users with biological classifications is trying to reconcile these
different views of the data, whereas with faceted classifications the ability to filter through
multiple trees, as seen for example in Sifer8, is an aid to the end user, designed to free users
from just the one way of browsing or interrogating data. We can say such classifications are
complementary rather than conflicting in purpose.
Research into ontologies and semantic web issues has looked at the problem of schema or
ontology mapping9, where the challenge is to find the best match between the various parts of
related schemas or ontologies. XML schemas are hierarchical, and while ontologies are more
complex they do contain major tree-based structures such as concept and relation hierarchies.
As such, they can often have mapping issues that fit into the domain of multiple trees as seen
in Aumueller et al10. Mapping can be automated to various extents by name and structure
analysis and also by applying further ontologies that form a semantic bridge between different
schemas, but an associated visualisation as in Altova’s MapForce product11 and Wang et al.’s
SCSI application12supplies a mechanism for a human expert to validate relationships and,
more importantly, to resolve instances that are not amenable to automatic methods.
Lastly, software development versioning systems such as CVS produce snapshots of classes
and packages which are organised hierarchically, and software developers may wish to
compare these snapshots to track package growth and discover where development effort was
concentrated at any particular time. Since computer scientists like to solve their own problems
first there have been many attempts to visualise software evolution, an early example being
Eick et al.’s SeeSoft system13. These tools in turn are advances on visual diff tools that
analyse source files or directories to discover differences. For directories and hierarchically-
structured files such as XML, the problem again becomes one of mapping between multiple
trees. Software visualisation undoubtedly covers a much wider area than simply revisions of
package/class-hierarchies, but of those that do examine this aspect, Gîrba et al.’s work14
attempts to explicitly show the evolution of hierarchical structures alongside other attributes
in code repositories, and Wu et al.15 display CVS package hierarchies as adjacent entities for
The semantics of a data set make a difference to the choice of multiple tree visualisations to
use, and probably the most basic dichotomy in tree data semantics is in the difference
between internal and leaf nodes. In a biological taxonomy, every node is simply a container
for the nodes below it and leaf nodes are nothing special in this respect, they are merely the
same type of node except they have zero child nodes. In contrast, class hierarchies in software
visualisation have the actual classes (compiled code) as leaves and the internal nodes are
arbitrary categorisations of those classes, thus there is a semantic difference in this case
between leaf and internal nodes.
Together with basic research into new Information Visualization techniques, investigations
into handling data from these domains accounts for the vast majority of literature in multiple
Multiple Tree Structures
The logical structures formed by merging multiple trees dwell in the messy domain between
single tree structures and general graphs; the exact type of structure formed depends on the
trees’ node overlap characteristics and structural similarity. The starting point is to define
what a tree itself is, with one formal definition being that it is an undirected graph structure
with one path and one path only between any pair of nodes in the graph. It must thus be
acyclic as the presence of cycles would produce multiple possible paths between some nodes
in an undirected graph. The more common, colloquial definition is to think of a tree as a
rooted structure, starting at a root node which may have zero or more children nodes linked to
it. In turn each of these nodes can link to other child nodes, so that each node has one parent
node only (except the root, which has no parent) and zero or more children nodes.
Information visualisation literature tends to freely swap the terms ‘tree’ and ‘hierarchy’ even
though hierarchies are not always trees, though others are tighter by referring to a
‘hierarchical tree’. The essential difference is the presence of multiple inheritance as found in
pedigrees16 or class hierarchies17 - an entity can have one or more parents in a hierarchy, but
only one in the strict definition of a tree.
There are four basic structures that can be constructed if we consider direct node overlap
only, shown in Figure 1; where these structures fit in a subsumption hierarchy of restricted
graph structures is outlined in McGuffin & Schraefel18.
The simplest case is that where no node overlap occurs between a set of trees. The resulting
structure is a forest, a collection of disjoint trees as shown in Figure 1a, though as discussed
later other relationships may yet exist between the trees.
Shared internal nodes in a multitree
have the same child nodes across
c) d) Orange Root
Shared internal nodes in a directed
acyclic graph can have different
children for each tree.
Figure 1. Structures that multiple trees can make through node overlap – a) Forest, b) Multitree,
c) DAMG and d) Polyarchy
Trees that only share leaf nodes form Multitrees as envisaged by Furnas & Zacks19 and also
demonstrated in Wittenburg et al.20; related phylogenies fall into this category as do faceted
classifications, where the same group of objects are categorised under different
classifications21. Multitrees also capture situations where trees reuse fragments of other
classifications instead of building new structures where a previously-defined structure already
resides, shown in Figure 1b. The prime example of this type of structure are family trees as
visualised by McGuffin & Balakrishnan22; one person’s descendants may overlap with
another, but the structure of the parts that do overlap will be the same.
Tree collections whose shared interior nodes are subject to restructuring can be divided into
two categories depending on whether there is a global parent-node orientation across the
trees. If there is a global orientation then the multiple trees form a DAG, or a multi-DAG as
seen in Figure 1c if multiple edges are kept distinct, such as those produced by Graham’s
multiple taxonomies5. For example, a biological taxonomy may reuse internal nodes such as
kingdoms and genera from another taxonomy but then construct its own paths between them
by defining other internal nodes; however a global parent-child orientation is preserved, as a
genus will always be lower down than a kingdom in any taxonomic tree, never the other way
If there is no global orientation shared between the structures, then the combined trees form a
polyarchy structure (Figure 1d) as identified by Robertson et al.23 and used by Conklin et al.’s
drill-down data browser24. Here the distinction between leaf nodes and internal nodes across
trees breaks down; nodes which form parent-child relationships in one tree may end up
forming the inverted relationship in another tree, or be siblings in yet another tree or unrelated
altogether; leaf nodes in one tree may well be internal nodes in another and vice versa.
For many scenarios, simple node overlapping does not adequately describe the mapping
between the trees. In these cases, the mapping is described through inter-tree edges that relate
the trees to each other. These relations can either be one-to-one or one-to-many as shown in
Figure 2, and can also have data such as typing or weighting associated with those edges. For
example, in biological taxonomy there can be explicit relations defined between nodes in
different classification trees, as detailed in Graham & Kennedy25, which are deduced by field
experts. These links can indicate a spectrum of different relations based on set notation such
as includes, congruence, dissimilarity etc and one node may be the source or target of several
links involving one or more other trees. What appears to be a collection of disparate trees
from the perspective of node sharing, now reveals a complex tree-based graph structure.
Figure 2. Inter-tree links defined between non-overlapping nodes.
Ontology and schema matching visualisations, such as Dadzie & Burger’s mouse ontology
viewer26, display similarly complex relationships. These relationships can be generated by
various means such as comparing element names, structural similarities or analysing semantic
similarities as seen in Cruz et al.27 – in a simple example a single full name element in one
schema matches to a combination of first and last name elements in another. Similar
relationships can also occur in software versioning, where renaming or refactoring may give
the same class or method different names between different releases, or cause classes to be
split or joined together between different releases. Tu & Godfrey28 describe matching such
files by a joint comparison of software metrics and name string matching between files.
The most noticeable variable in multiple tree visualisations is the representation used to show
and allow interaction with multiple tree structures. The representations can be based on
layouts used for individual trees or on layouts designed for restricted graphs, such as DAGs,
or adapted from those used to display more general graph structures. Some of the options
often used for single trees, such as node-link representations are applicable to more complex
graph structures such as multiple trees, and the widespread use of the small multiple29
technique means that single tree representations often feature prominently in multiple tree
visualisations. Therefore we begin our representation section with a quick discussion of single
tree representation styles, which is by no means exhaustive in its coverage of the literature.
For a fuller review of single tree visualisations we recommend the theses referenced in the
introduction such as Nguyen3 and Nussbaumer4.
Single tree visualisations have a long history before the coining of the term ‘Information
Visualization’, a classic reference being Reingold & Tilford’s30 work, itself only one of many
pre-1990 algorithms listed in Beebe’s exhaustive bibliography31 for tree drawing. However,
these approaches tended to focus exclusively on layout algorithms; what Information
Visualisation introduced was the notion of being able to interact with the generated tree
Single tree layout divides into a number of categories, based on the graphical method used to
indicate a parent-child relationship, five of which are shown in Figure 3. The first and most
widespread is the node-link layout30, 32, with parent-child relations represented as lines (links)
drawn between the visual objects that represent the nodes in the tree. Secondly, nested or
enclosure layouts33, 34 indicate the same relationship by placing child node representations
within the boundaries of their parent node. Thirdly, there is the adjacency layout or icicle
plot35 style where child nodes are drawn as abutting their parent node. This method, more
than the node-link approach, requires the definition of a parent-child orientation to
differentiate parent-child relations from sibling relationships and to indicate the direction of a
relationship. Usually this orientation is either top-down as in Graham & Kennedy’s taxonomy
browser25 or centre-out as in Stasko et al36. All three of these layout styles have been extended
from their original 2D projection to 3D variants with various degrees of success: node-link37,
nested38, and adjacency39.
a) A b) A c) A
B C D B C
E D E F
D E F
d) A e) ABCDE F
Figure 3. Basic types of tree representation - a) node-link, b) nested, c) adjacency, d) indented list
& e) matrix representations
A fourth representation style is indentation, where nodes are listed linearly in order of depth-
based traversal and then indented by an amount proportional to their depth in the tree. Often,
stylised links are drawn to make parent-child relationships clearer but this is not always the
case. This is the most common form of tree display used in contemporary GUIs, seen in
locations such as the folders view of Microsoft Windows Explorer. In empirical evaluation by
Cockburn & Mackenzie40 this layout has shown to be the objectively preferred choice when
compared to other styles of tree visualisation, though Kobsa41 suggested that much of this
performance advantage is explained by familiarity due to the ubiquitous presence of
Finally, individual trees can also be displayed via a matrix representation but this tends to be
less common than the previous styles for good reason. Firstly, this is because of the difficulty
in following edge paths in matrices, as recognised by Shen & Ma42. In Figure 3a,c&d it is
clear that D is a ‘grandchild’ of A, and whilst slightly trickier in the case of the nested
representation in Figure 3b (Lü & Fogarty43 discuss how variation in nested representations
can greatly affect this property), in the matrix representation the A-B and B-D edges need to
be discerned independently and then combined, making the relationship much more difficult
to deduce. A second issue is that essentially a single tree is not complicated enough in
structure to warrant a matrix representation. One of the main reasons cited for using matrices
to visualise graph types is that they eliminate edge crossings that occur in other graph
representations, but a single tree can always be drawn with no edge-crossings in the other
representations and so this reason no longer applies. Further to this point, a tree with N nodes
has N-1 edges, and thus when displayed as a matrix will only fill the square root of the total
N2 possible entries, making it highly space-inefficient.
All the layout styles have associated advantages and disadvantages and the choice of
representation is depending on the tasks that are to be performed with the structures and the
semantics of the data concerned. Generally node-link representations are more understandable
to the lay-person and communicate structure readily, but use up screen space rapidly. Nested
representations allow more nodes to be displayed at once but structure is more difficult to
perceive due to lacking a global child-parent orientation, plus they emphasise leaf nodes at the
expense of internal nodes. The adjacency and indented list methods strive for a halfway house
between these two styles, utilising a higher proportion of screen-space than a node-link
display, yet making structure relatively simple to follow. Finally, the matrix reduces the tree
essentially to a look-up table. These basic layout styles are the foundation for all tree
visualisations that display internal tree structure, and the styles themselves can be combined
within a visualisation of a single tree as demonstrated by Zhao et al.44, where portions of the
tree are drawn as either nested or node-link representations dependent on screen space and
user interaction. Further, Nguyen and Huang’s EncCon technique45 combines the enclosure
and node-link approaches across an entire tree; the tree nodes being positioned using an
optimised nested layout algorithm and then connected with links.
Multiple Tree Models x Multiple Tree Representations
A logical starting point to categorise multiple tree visualisations is to distinguish whether
‘multiplicity’ is based on the number of trees displayed, or the number of trees modelled in
the structure, or both.. Table 1 shows a brief tabular summary of this categorisation and the
four basic cases it produces - with the simplest case of a single tree model represented as a
single tree visualisation being covered in the previous section.
The second case covers the scenario of one tree model visualised many times; for instance
Wilson & Bergeron’s dynamic hierarchy visualization46 can display multiple, differing
representations of the same hierarchy, but does not display multiple structures. A similar
caveat applies to Urbanek’s KLIMT system47, Schedl et al.’s48 stacked radial tree
visualisation and Teoh’s more recent work49 on multiple views for trees. Kules et al.50
explore the situation of simultaneously using two different, linked representation styles of the
same tree - one nested and one node-link representation.
Of more interest to us are the approaches that deal with multiple instances of trees in the data
we wish to visualise, and these can be divided into visualisations that are shown as a single
tree or show multiple trees. The former case tends to be visualisations built for hierarchical
facet exploration, such as MoireTrees51 and Facet Folders52, that try and give a fluid single
tree view over a multi-hierarchical structure for ease of navigation. The latter case is that of
visualisations which display multiple representations of multiple trees. Here there may not be
a universal coverage of leaves by each hierarchy – some may have more leaves than others
and in the case of polyarchy structures the notion of what leaves are may change between
This difference between single and multiple tree representations for multiple tree models is
not as clear-cut as a simple dichotomy would suggest, especially in the case of visualisation
interfaces for faceted hierarchy exploration. While for some instances it is fairly clear how
many tree representations are being shown, for instance the Mambo music browser53 only
displays one hierarchical facet at a time, and others such as FacetMap54, FacetLens55 and Yee
et al.’s image browsing system56 simultaneously display at least parts of a hierarchy per facet
type, yet others such as MoireTrees and Facet Folders merge portions of multiple hierarchical
facets into one hierarchy representation. The essential difference is that while the same
multiple hierarchy models can operate behind all these various interfaces, the latter have
deliberately chosen to project this model onto a single hierarchical view.
Table 1. Number of trees compared with number of individual representations
Number of Tree Representations
1 Tree Multiple Trees
Traditional single tree visualisations Multiple/multiform views of a single tree
(e.g. Cone Trees37, TreeMaps33) structure (e.g. Wilson & Bergeron46,
Original TreeMap - (screenshot courtesy of Teoh’s Multiple Views of a tree data set
Human-Computer Interaction Laboratory,
University of Maryland, College Park)
Single hierarchical view of navigation Full multiple tree visualisation (e.g.
through faceted hierarchies (e.g. Graham & Kennedy57, Munzner et al58,
Number of Trees in Structure
MoireTrees visualisation Graham & Kennedy’s multiple taxonomy
The first stage in visualising multiple trees is to visualise two trees, approaches to which can
be seen in Figure 4 and can be categorised as:
a) Linking two spatially separate tree representations.
b) Shared colouring between two spatially separate tree representations.
c) Animation between trees (temporally separate).
d) Matrix comparison of two trees.
e) Spatial agglomeration of two tree structures.
a) b) c) d) e)
Figure 4. Methods of comparing nodes in two trees, a) edge drawing, b) colouring, c) animation,
d) matrix representation & e) agglomeration – shown using indented list representations as the
basis for individual trees.
Edge Drawing - The first and most widespread technique in the literature is to display both
trees as separate structures with lines drawn between them to indicate relationships between
nodes they connect27, 59-62 as in Figure 4a). This allows exact and individual relationships to be
traced between different trees. The drawback with this approach is if there are many lines
displayed at once then individual edges become impossible to distinguish from the mass of
drawn lines, a common problem in the perception of graph drawings as recognised by
Purchase63, of which this is the specialised case of drawing bipartite graphs64, plus the added
constraint that both parts of such a graph are grouped into tree structures. In response to this,
Robertson et al.65 describe a collection of methods to alleviate traceability difficulties, Holten
& van Wijk66 use a bundling technique to visually group related links drawn between two
hierarchies, and Buchin et al.67 explore formal algorithms for reducing the number of edge
crossings between two binary trees. Further, many such visualisations such as Craig &
Kennedy61 only show selected subsets of links between trees to reduce the tangled appearance
of a fully-populated display.
Colouring - A closely related technique is to show matching nodes between trees through the
use of shared colouring as in Figure 4b), used by Parr et al.’s DoubleTree system68and
TreeJuxtaposer58 , Zoomology69 and EVAT70 applications developed for the InfoVis 2003
contest71 amongst others. This technique gives a more general overview of the amount of
overlap between trees. In essence, a coloured node is signalling that it has a match somewhere
in the other tree, whereas a drawn link signals exactly which node it matches in the opposite
tree. Further interaction, such as individual node brushing, is necessary to then locate exact
matches of nodes between trees. The vast majority of the numerous commercial or freeware
applications for comparing file directories and XML files such as Microsoft’s WinDiff72 use
colouring with a linearly indented list representation as it is the simplest effect to implement
with standard GUI toolkits. Some merge the approach with edge drawing, such as Kompare73
and Altova’s DiffDog74 that use both lines and colouring to indicate similarities between two
A further difference between the colouring and edge drawing approaches is that the edge
drawing approaches tend to display their trees in representation styles such as a horizontal
node-link layout75, a horizontal space-filling adjacency layout61, 76, or indented lists62 that have
a non-radial orientation. This enables edges to be drawn, such that, while they may
unavoidably cross each other, they do not cross any of the nodes in the trees. The shared
colouring approaches do not have to contend with this issue and can therefore use a more
varied array of representations, including nested layouts such as Treemaps20 and hyperbolic
Animation - Animation such as found in Robertson et al23 is used to display change between
representations of different trees, in effect distinguishing the trees temporally rather than
spatially. Animation is also used for showing changes in values associated with tree nodes as
in Ghoniem & Fekete78 or the small-scale addition and deletion of nodes seen in Wittenburg
& Sigman79. In practice, animation is best used either for showing gradual transitions that
represent evolving change in the structure of a tree, or in showing switches between
hierarchies where only a few nodes stay constant, rather than radical reorganisation where a
user can easily lose track of the overall change. In both cases animation is effective when only
a few nodes are either moved or preserved with consideration to the entire node set.
Matrix - The fourth method for visually comparing two trees is to arrange the trees along the
horizontal and vertical axes of a matrix as shown in Figure 4d), with the matrix now showing
relationships or shared leaves between the two trees - this differs from a single tree matrix
representation which has the same tree arrayed along both axes. A choice can be made as to
whether only leaf nodes are involved in the comparison, in which case an adjacency style or
node-link representation along the axes is used, or whether direct internal node comparisons
are also to be made in which case using the indented list representation of a tree along the
axes gives space for appropriate columns and rows as in Figure 4d). This choice as
previously stated boils down to data semantics – whether an internal node is simply the sum
of its leaf nodes or has unique properties in itself.
This method removes the problem of interpreting impenetrable masses of drawn edges but
suffers from the same under-utilisation of screen space as a single tree in the same style. This
is especially true if the mapping between tree nodes is strictly one-to-one – in which case the
number of unused entries in the matrix is proportional to the square of the number of utilised
spaces - thus the effect is exacerbated with larger trees. As such, it tends to be used by
techniques wanting to show one-to-many relationships between nodes in related trees.et al
The most common occurrence of this representation is in bioinformatics, where it is known as
a cluster heatmap80, a particular use being to plot the distribution of microarray data sets as
seen in Eisen’s TreeView software81. Further, if we stretch our definition of two trees to
include two subtrees of the same larger tree, then into this category fall source code and
general graph analysers such as van Ham’s call matrix visualisation82. Here, as with other
general clustered graph visualisations, the hierarchies are used as aids to access a general
graph structure that resides at the bottom level of the trees, rather than being the focus of
Agglomeration - This final approach fuses together two tree structures into one structural
visual representation. Furnas & Zacks’ Multitrees19 allows two tree structures to be fused
together in one node-link representation, in this instance the context is that of a family tree,
with one tree showing ancestors and the other descendants. Using their own definition of
Multitrees, it follows that the structures between these trees are always shared exactly, so a
node in one tree always has the same set of edges in the other
Edge Drawing Colouring
Figure 5. Screenshots of visualisations that show comparisons of two trees. Linking – Craig
and Kennedy’s61 Concept Relationship Editor, Colouring – DiffDaff83 file utility comparing
two XML files, Animation – Ghoniem & Fekete’s78 animated treemaps, Matrix – van Ham’s
code matrix82 , Agglomeration - Tu & Shen’s Union Tree84.
For more involved structures where parentage of nodes may change between trees, Tu &
Shen84 propose a structure known as a union tree in which nodes that have different parents
between the two trees are cloned to appear under both parents simultaneously in a merged
structure. This removes cycles from the merged structure, retaining a strict tree structure for
subsequent visualisation while preserving the edge sets found in both component trees. This is
a common technique when dealing with DAG structures that are to be visualised using tree
layouts – spanning trees can perform the same function but by removing edges rather than
cloning nodes. Tu & Shen then visualise the union tree with a TreeMap layout and use
shading effects within the node representations to indicate changes in node attributes and
presence between the two trees.
Hong et al.’s Zoomology browser69 features a similar technique to visualise two trees in one
merged adjacency representation. The representation is visualised from the perspective of one
of the two trees, with areas marked in white indicating nodes ‘missing’ from the current tree
but present in the other, and, for the reverse condition, white borders used to mark nodes
occurring only in the current tree. Lee et al.85 also merge two similar trees into one structure
and display the result as a node-link visualisation. They then use colour and transparency cues
to indicate the calculated degree or certainty of structural overlap between the two
hierarchies. Isenberg & Carpendale86 combine elements of multiform view techniques with
aspects of agglomeration on a table-top display, letting users interact with and compare a pair
of trees through direct visual overlay (i.e. no computational analysis on the merged structure
is performed), and allowing two different representation styles to be used – selection of which
is based on user preference for the task at hand.
Summary - Thus we can see that even for two trees there is a range of possible representation
styles that can be utilised to show those trees’ inter-relationships. Figure 5 shows a sampling
of screenshots for systems that use each of these representation styles, showing the variety of
visual forms that the representations of a pair of trees can take. Some lend themselves better
to certain structures – the edge drawing and matrix representations can easily show related
tree structures which have one-to-many relationships beyond simple node overlapping, while
such relationships would remain ambiguous with the colour-coding approach. Similarly for
overlapping MultiTree structures the agglomeration approach means simply redrawing
structure on top of existing displayed structure.
If set relations rather than individual node matching between trees are of more importance
then the colouring approach lends itself well to displaying such data. Of the six published
entries for the InfoVis 2003 contest71 for pairwise comparison of trees, all used a colouring-
based linking and brushing approach for at least part of their solution (entries could include
multiple visualisations). Animation between trees was not used in any of the approaches, the
technique being reserved for illuminating focus+context transitions internal to trees.
Agglomeration was used in an overview panel presented in Hong et al’s Zoomology
Multiple tree (>2) visualisations for the most part extend the two-tree approach to a larger
collection of tree structures. Here the pressure builds on available screen space and decisions
are needed about whether to show relationships from just one tree to the other trees or to show
all relationships between the entire set of trees. Furthermore, other options such as 3D
representations for navigating collections of trees may be considered, and when the number of
trees becomes too large to display usefully, scatterplot-like representations of tree distances
emerge, with trees reduced to individual points
Edge Drawing–This approach, when extended to more than two instances, involves the
display of multiple individual representations on-screen, a technique termed as small
multiples by Tufte29. Available screen space is sub-divided into areas in which the individual
trees are drawn - an extension of the technique for two trees seen in Figure 4a-b). Then, to
draw edges between these multiple tree representations is probably best described as what
Parallel Coordinates87 would resemble if the axes were hierarchical in nature, especially as
these visualisations generally do not attempt to draw a many-to-many mapping between all
the trees but either a one-to-many mapping or a sequential mapping as seen in Parallel
Coordinates. The reasons for not showing a many-to-many mapping in this representation
style are that it would firstly produce so many edges intersecting each other and the trees
themselves as to be unreadable; secondly, many data sets are specifically visualised in this
manner because they have a temporal ordering such that comparison of a particular tree is
usually only meaningful to the directly preceding or succeeding trees.
We are not aware of any current general purpose Parallel Coordinates systems that use
hierarchical axes; perhaps the nearest example in appearance is Wernert et al.’s Tree3D88
system, based on previous work by Stewart et al.89 into visualising multiple phylogenetic
trees. This approach lines up multiple phylogenies in a parallel formation and then traces lines
between matching nodes in immediately neighbouring phylogenies. Dwyer & Schreiber’s90
later phylogenies visualisation can also be viewed in this style, and includes edge crossing
minimisation algorithms to improve readability.
Similarly, Telea & Auber’s visualisation of source code evolution91 uses small multiple
representations of code package structures and edges between these representations to
indicate the introduction and movement of source code tree changes. Colour is also utilised to
pick out particular package grouping or subsets of interest.
Also, Tominski et al.92 developed a radial-based layout, VisAxes, for multi-dimensional
information. Here, as in Parallel Coordinates, dimensions map one-to-one to a set of axes; a
dimension/axis of particular interest is placed at the centre of the display around which the
other axes are arranged. Similarly to Parallel Coordinates, objects are then visualised as poly-
lines that plot between the axes set at the appropriate intersections for each axis – though here
each poly-line starbursts from the central axis to the others rather than the sequential
intersecting that the Parallel Coordinates layout provides. This technique is mentioned
because they discuss the possibility of hierarchical axes and if enough such axes were used
their approach would come under the umbrella of multiple tree visualisations that use edge
drawing to show correlations.
Colouring - It is noticeable that once more than two trees arrive on the scene the dominant
approach for showing relationships between individual trees in small multiples is through
colour or another highlighting technique. In fact, the majority of the examples referenced in
the previous edge drawing section also use colouring in tandem with edge drawing to mark
particular subsets. The reasons for this are two-fold.
Firstly, there is the previously described problem of edge crossings and the resulting lack of
readability, though alleviated to an extent through edge crossing minimization algorithms.
Secondly, edges themselves require space to draw and to visually reroute themselves between
trees, but with space at a premium with multiple representations to draw there is pressure to
use the more space-efficient tree representations as seen in Figure 3b-d) and to use what space
there is for tree structure. Examples that use colouring to show correlations include Munzner
et al.’s TreeJuxtaposer58, which can draw multiple linked trees, based on dendrograms – a
node-link style of layout used for phylogenies. However, internal nodes are not labelled and
the allocation for individual nodes can become so compressed that the drawn intra-tree edges
may use all the space available for drawing, hence moving towards the adjacency style of
representation. Graham & Kennedy25 use multiple adjacency-layout representations, as do Chi
et al.93 and Spenke & Beilken94, whilst both Wittenberg et al.20 and Kutz95 use multiple nested
layouts to represent their trees. Morse et al.96 use multiple indented lists to compare and
contrast multiple taxonomic trees. Daida et al.97 uses small multiples of individual radial
node-link representations to visualise processes in genetic programming but does not allow
direct interaction with the nodes in a tree.
However, even with more efficient single tree visualisations, the ‘small multiple’ approach
does not scale well due to each tree receiving a correspondingly smaller area of screen space
as the size of the set grows. There has been research on displaying larger data sets via small
multiple representations, but this focuses on larger and larger individual trees98 rather than a
greater number of trees – so far the largest number of trees displayed with this method is
approximately 50, for a set of binary trees as seen in Chevenet et al.’s TreeDyn system99, or
14 if we impose the condition that the tree elements are interactive as in Graham et al100.
Animation has further drawbacks when applied to multiple trees rather than just a pair of
trees. Here, the number and complexity of trees which can be animated through is not
constrained by screen space but by human perceptual abilities; animation can only show at
any given moment a change between two trees, tracking a change between multiple trees
relies on a user being able to remember the animation’s past states. Card et al.’s TimeTree
visualisation101 combines a tree visualisation with temporal data, where changes in a tree
structure between different time points are reconciled through animation. Herman et al.’s102
Latour tree drawing system also displays multiple trees through animation, and describes the
input data as one initial tree plus a group of ‘difference trees’ that detail sets of incremental
changes to the initial tree structure. This would seem to implicitly recognise that animation is
best suited to showing structural evolution rather than complete reorganisations.
Wettel and Lanza103use a ‘flick-book’-style visualisation by simply switching between a view
of one tree to another – however they preserve the positioning of nodes between views by
allocating layout space according to a union of the tree set. Thus a space is allocated in each
individual tree view for every node that ever exists throughout the whole set of trees. If a
particular tree does not include a node at a particular position then the space is left blank in
the associated view.
Matrix-based visualisation of multiple trees is complicated by the fact that a matrix has only
2 axes to which an individual tree can be mapped. Multiple trees could be accommodated by
extending the multiple scatterplot technique seen in Becker & Cleveland104 – a visualisation
device that allows N-dimensional data to be rendered as an NxN matrix of scatterplots,
showing every pair-wise combination of variables – to use trees as the basis of comparison
rather than dimensions. This would in effect form a matrix of matrices, each of which shows
the correlation of two trees against each other, though we are unaware of any current
visualisations that do this. In this manner a matrix representation for multiple trees becomes a
small multiple display itself, except that each individual representation shows the mapping
between two trees rather than just one tree in isolation.
Conversely, the union tree (as defined by Tu and Shen84) could be used as a hieraxis for both
axes of one matrix, and edges plotted for multiple trees within this single matrix. However,
trees that differed significantly in their structures and node overlap would also produce larger
and larger union trees and thus correspondingly larger matrices. Further, techniques would
then be needed to display and differentiate multi-edges that occupied the same point in the
matrix. Abello and van Ham’s MatrixZoom system105 can display matrices containing multi-
edges but, rather than distinguish them individually, use colour saturation to indicate the
number of edges occupying a particular point in the matrix. The multi-edges in their system
are formed by viewing a graph at multiple, hierarchical levels of detail and aggregating edges
at each level.
One interesting take on the approach is touched on in Wong et al.’s106 work, where sketching
operations on a matrix representation are used to generate graphs. Their discussion includes
an example of how to generate multiple trees through drawing the appropriate matrix
representation, though the resulting structure is shown through a traditional node-link graph
representation. One limitation is that the same relationship cannot be replicated across trees as
their application does not allow the creation of multi-edges.
Agglomeration of multiple trees means in practice that a node can have multiple parents to
display in the same representation, possibly a different parent node per tree. Again the options
can include replicating nodes with more than one parent link across the trees to keep the
structure as tree-like as possible and amenable to standard tree-drawing techniques. If though
we wish to represent the multiple tree structure as the truer cycle-containing graph structure,
which nested, indented and adjacency layouts cannot display, then agglomerative
representations of multiple trees are generally displayed using node-link representations, such
as in Florentz and Muecke’s GLAD system107. Some do try a different tack though, Mank’s
CristalView108 uses force-directed placement of overlapping TreeMaps to communicate
shared nodes across multiple hierarchies. Burch and Diehl109 also break the node-link
domination to a degree by displaying a TreeMap of a reference taxonomy on top of which are
overlaid multiple node-link trees. The nodes in each individual tree are instances of object
classes in the reference taxonomy and are thus placed on top of the TreeMap at corresponding
positions, with the edges between contorting to connect the appropriate points.
Care must be taken when displaying multiple tree structures using general node-link graph
drawing techniques; to begin with multi-edges resulting from consistent edges across different
trees need to be distinguished by some method, but most general graph-drawing toolkits do
not provide support for this. A general graph layout method also usually results in no global
orientation for child-parent links even if one exists in the overall structure. Techniques
specifically developed for drawing DAGs can re-impose a global orientation for parent-child
links, though the restrictions on node placement involves a trade-off on edge crossings as seen
in Graham & Kennedy57, D’Ambros et al.110 and Melançon & Herman111. The main
advantage with agglomeration displays is that screen space is effectively re-used across tree
representations. There is no technical upper limit to how many trees can be displayed through
agglomeration, though eventually known perceptual obstacles found in graph drawing caused
by edge-crossing and occlusion of nodes and edges will lead to difficulty in interpreting the
3D Representations - A popular compromise that fuses elements of the previous approaches
is to use a 3D representation of multiple trees. These generally take the form of multiple,
distinct tree representations drawn in parallel planes to each other. Relationships between the
trees are shown again either by drawing edges between trees as in Dadzie & Burger26, Dwyer
& Schreiber90 and Wernert et al.88, or by using colouring as in Chi et al93. The 3D approach
means the group of trees can be rotated so that they resemble a small multiple display of
multiple trees (one tree per section of screen space), or turned ninety degrees so the trees give
the impression of overlaying one another. This feature does have the drawback of not
guaranteeing equivalent nodes in different trees will overlay each other and can lead to a
display with a high degree of occlusion. Reiss’ early work on software visualisation112 used
3D to show a merged structure of three different hierarchies, where looking at any of the
xy/xz/yz planes head-on would reveal one individual hierarchy.
Edge drawing Colouring
Figure 6. Screenshots of systems representing the different representation styles for multiple
trees. Edge drawing – Telea & Auber’s91 CodeFlow application, Colouring – Munzner et
al.’s TreeJuxtaposer58, Animation – Wettel & Lanza’s103 CodeCity representation, 3D –
Dadzie & Berger’s26 mouse anatomy ontology viewer, Agglomeration – Graham &
Kennedy’s57 DAG viewer and Atomic - Hillis et al.’s TreeSet visualization113 (screenshot
from the TreeSet module running under the Mesquite software system114)
Atomic Representations - Finally, when the number of trees grows extremely large, the
finite screen space cannot show all the trees at any sensible level of detail, so techniques have
been developed that visualise the trees as atomic items, from which examples can be viewed
in detail. Amenta & Klingner115 & Hillis et al.113 take this approach by visualising a set of
phylogenies in a scatterplot, where distances between points relate to the degree of similarity
between the associated trees. Meyer116 proposes a similar scheme, whereby the trees form
nodes in a hierarchical graph, connected by edges according to their similarity. Parts of the
graph and, from there, individual trees or a consensus tree of a tree group can then be
interrogated to display further details and to reveal related phylogenies. Both these
applications state that consensus trees lose data from the individual trees that compose them,
and so the ability to see the individual phylogenies is crucial.
Summary - Again, as with the two tree scenario, the type of overall structure the multiple
trees form will have a strong bearing on the visualisation techniques that will be required to
effectively visualise the data. An unrelated forest of trees will obviously be easily, and
perhaps only, represented as separate visual entities, whilst visually overlaying trees - an
agglomeration layout - might benefit those that share many multitree-like sub-structures
between themselves. Trees that construct their own structure over shared nodes, forming
polyarchies or DAGs, are more problematic as the differing tree structures produce significant
extra edge-crossings in the agglomeration style views. Finally, trees that are related through
non-overlapping node relationships will favour a representation that does not emphasise node-
sharing but instead has the ability to show one-to-many relationships between trees. This will
favour the edge drawing and matrix representations over the agglomeration based techniques.
Figure 6 gives a selection of visualisations for the various multiple tree visualisations, with
the omission of the as-yet unimplemented matrix representation.
Table 2 describes a matrix of representations by possible features to highlight the strengths of
each representation, including the ability to show node mappings between trees, and the
ability to show types of structural changes – specifically the addition, deletion and
reorganising of nodes between trees. For instance, finding one-to-many relationships is easier
in the edge drawing representation than in the colouring metaphor, while showing new and
deleted nodes is easier in the colouring approach than with the edge drawing representations.
Situations are also marked where there are, to our knowledge, no current representations –
such as many in the matrix category.
In summary, representations for multiple trees are based on the representations described for
two trees, but the drawbacks and advantages of each become more exaggerated as more trees
are considered, until atomic representations of trees become the only viable option and more
detailed views are only considered upon reducing the tree set size or zooming in on a
particular tree instance. Matrix representations appear to be under-exploited even though they
are gathering more attention for general graph display due to their removal of edge-crossing
difficulties found in general node-link representations. For multiple tree structures that
include cycles that hamper the application of certain representations or feature relations that
induce edge-crossings in node-link diagrams, perhaps this is one potential avenue of future
exploration. To balance against this, matrices have well-known drawbacks in path navigation
that are also their main weakness in general graph drawing and will require mechanisms for
dealing with multi-edges which occur frequently in multiple tree sets.
Table 2. Strengths and weaknesses for representations of multiple trees. Those categories where capabilities for a task in a given representation have been proven are shaded.
The 3D category is omitted as much of what 3D visualisations are capable of depends on the individual representations used for the trees.
Representation 1:1 Node Matching M:N Node Matching Extends To N Trees Structural Changes Attribute Changes
Small Multiples Yes, edges link between Multiple edges emanating Poorly. Could be extended in a Yes, for subtrees as edges plot No, edge drawing relates only
– Edge Drawing nodes in different trees. or arriving at a particular hierarchical parallel coordinate style relatively to each other. Addition to structural changes and
node. but edge and tree crossings become and deletion more problematic as consistencies between trees
an issue. Screen space also reduces in edges cannot be drawn to or from a
proportion to the number of trees. non-existent node.
Small Multiples Colouring is a set-based Indistinguishable from the Yes, selections in 1 tree can be New and deleted nodes generally Yes, if colour coding can be
- Coloured action, so it takes further 1:1 state. marked by colour in N other trees, coloured as a specific user function. assigned to specific attributes
interaction techniques to though again screen space reduces in Distribution of blocks of colour can and traits, differences between
discern specific 1:1 proportion to the number of trees. show dispersal of sub-tree across trees can then be seen.
relationships in a selection. wider structure.
Animation Can be done by preserving Unknown. Would require Pairwise in sequence comparison. Yes, but difficult to track multiple Dependent on method used to
node position between animation of node Cognitive effort required to remember changes, best used when changes communicate attribute values.
frames or animating aggregation/splitting. previous animation states. are gradual or only a few nodes are Change in e.g. colour space
between successive preserved between trees. and even size is generally less
positions. noticeable than change in
Agglomeration Yes, achieved by spatially Can be done by drawing Yes, matching parts of tree structure Yes, changes in parents or children Only if attribute changes can
overlapping nodes from non-hierarchical edges in are reinforced in the representation between trees will be shown by be aggregated and summarised
different trees addition to hierarchical and extra edges used to show new extra edges in representation. within one node representation
relationships structure or restructuring. Multi-edge representations critical – this is usually precluded by
for showing constancies. space constraints.
Matrix Yes, 1 point per row or Yes, fill in multiple points Possible by building a multiple Yes, matrices show edges between No, the matrix relates only
column between two trees per row or column. scatterplot-style matrix or using a trees, a change in structure between relationships between the
on the axes. union tree of all trees as the axes. any two particular trees would trees; though it is conceivable
manifest itself as a divergence from those relationships could be
a diagonal plot of edges in the couched in terms of attribute
matrix. value changes.
Atomic No, tree viewed as an No, tree viewed as an Yes, into the hundreds or thousands, Yes for global change, if distance Possible, if distance metric
atomic object. atomic object. trees that occupy ‘interesting’ metric used in the layout of tree used to layout tree ‘points’
positions in the space can then be ‘points’ is indicative of a global relates in some way to node
rendered individually. degree of difference as in Hillis et attribute values
The literature reveals three main high-level tasks that multiple tree visualisations attempt to
tackle in order to allow users to use, create and understand multi-hierarchical data.
1. Filtering of data through multiple hierarchical categories – faceted hierarchy browsing or
2. Mapping of relationships between multiple hierarchies – such as allowing users to edit
machine-produced mappings between ontologies or taxonomic data.
3. Exploration of differences between multiple hierarchies, structurally or in terms of node
Many of the visualisations that fall under the umbrella of data filtering do not wish to
compare multiple hierarchies but instead aim to offer a straightforward way of navigating
through the structure formed by multiple hierarchies to reach the data sitting at the leaves. As
such they tend not to offer complex or multiple views of the dataset, but a current view of
where navigation has led to and indications of where immediate navigation forward or
backward could lead to. Representations of this task are either a single hierarchy composed of
the current and possible further filtering categories or a set of extremely flat hierarchy
representations; often only one or two levels of a hierarchy are displayed even if deeper sub-
categories exist. et al
The second high-level task, mapping relationships between multiple hierarchies, is in all cases
done on a pair wise basis. Apart from Wong et al’s106 matrix-based sketcher this task is
always carried out by representing the hierarchies in question as two individual
representations, mostly in the indented list style (and never as a nested representation),
between which relationships are shown by lines or arcs acting as links. This method is
preferred in fields such as ontology alignment and taxonomic concept mapping as it can show
more complex relationships than simple 1:1 relationships between nodes in different trees –
and it is these one-to-many or many-to-many relationships that tend to need expert
intervention to specify accurately when the simpler relationships have mostly been resolved
algorithmically. Commercial products such as MapForce11 and research prototypes such as
SchemaMapper65 all adhere to this template of representation and interaction.
The final high-level task, comparing multiple hierarchies to find changes in structure or node
properties, is the task that has produced the most varied collection of representations as
researchers strive to project the richness and complexity of the inter-relationships between
multiple trees, while at the same time attempting to keep the basic representations intelligible,
and can be divided into a number of different tasks – comparing node attributes, finding
structural reorganisations or locating node deletion and addition
Finding differences in node attributes inevitably involves either a small multiple display or
animation approach as the differences between successive trees need to be shown in their own
area either spatially or temporally. Out of these, the edge drawing approach is usually
disregarded as attributes are usually encoded using colour or size as in Treemaps, and edge
drawing is almost universally reserved for showing structure reorganisation.
Finding changes in structure depends on the type and detail of change we wish to see. The
overlap of common structure can be seen by colouring in small multiples. If we are interested
in finding re-classification of existing structure, the most prominent style appears to be some
form of agglomeration representation or edge drawing approach, as divergent edges between
trees can quickly be seen in the display of the merged structure – though as stated before too
many changes can lead to problems with edge-crossings in node-link displays. Addition and
deletion of nodes can be seen in general in coloured representations if a function has been
implemented to encode such nodes with specific colours, such as found in TreeJuxtaposer.
Edge drawing techniques have difficulty here as if a node is freshly minted or now removed,
there is nothing to either draw a connecting edge from or to. (The same problem occurs in
parallel coordinates when a null value occurs for an item in a particular value.)
Unlike for single trees, there are limited user studies in comparing multiple tree
representations, and those that have occurred have been small in scale. Lee et al85 compared a
node-link agglomerated display of two trees against Microsoft’s WinDiff72 tool and found
preference amongst software engineers for their CandidTree interface. Graham & Kennedy117
found that taxonomists preferred a small multiple representation of a tree set linked by
colouring to an agglomerated graph representation, and still preferred the small multiple
approach to a DAG representation that preserved child-parent orientation. However these
were both studies for specific fields and these preferences may be ingrained to a particular
mindset or tasks. Multiple tree research still lacks an equivalent study to Barlow &
Neville’s118, Kobsa’s41 or Andrews & Kasanicka’s119 evaluations across a gamut of single tree
visualisation types. Parunak120 argued that people were best prepared to think of multiple
classifications as individual, intersecting entities rather than a merged whole, and this might
give a hint as to why the small multiple approaches appear to be the dominant metaphor in
multiple tree visualisation.
This review of current work demonstrates that multiple tree visualisation is still an open
research topic. Even for single trees, research is still being published on different, novel ways
of displaying and interacting with trees and hierarchies, with techniques designed to
accommodate certain user groups and tasks. Visualising multiple hierarchies adds an extra
level of complexity, as representations of multiple trees cover a wider breadth of display
possibilities than representations for single instances or even pairs of trees. Layouts for
general and layered graph drawing enter into consideration as well as interaction techniques
such as linking and brushing for discovering correlations between trees.
The complexity of the overall structure varies depending on the inter-relationships between
the individual hierarchies, on a spectrum of no overlap whatsoever to directed acyclic graphs,
onto polyarchies, and then through to structures that have extra non-trivial relationships
between nodes – this can and does affect the particular choice of layout and techniques used
in a multiple tree visualisation.
Consideration of tasks also narrows the possible range of representations; human-assisted
mapping between trees is done exclusively on a pair-wise fashion between individual tree
representations. Navigation of multiple trees involves displaying as little of the complexity of
the structure as possible and keeping the navigation choices down to the next one or two
immediately accessible levels in each hierarchy. For more involved tasks, such as discovering
differences in structure between trees, increasingly detailed and varied visualisations have
been considered. In these circumstances, research so far has shown that developers and users
prefer when possible to reduce visual complexity by keeping the individual tree structures
visually separate, even if the underlying data model is a fusion of many trees. The layout
design space has not been fully explored by existing visualisations; matrix-style layouts are
noticeable by their absence in the literature.
No conclusive user studies have yet been performed comparing the various types of possible
multiple tree visualisation. Those small studies that have occurred were based on small user
samples, self-assessment as in the InfoVis 2003 competition, or a particular type of data.
The situation is exacerbated by the fact that as stated multiple trees can form different classes
of structure. Whilst single tree comparative evaluation can rely on a tree being a tree, multiple
tree evaluation will have to accommodate numerous types of structures from multitrees to
polyarchies and consider whether systems under comparison are being compared like with
like. It would, for instance, not make sense to ask a visualisation designed to show multitrees
to handle structures with more complex relationships and then judge its performance against
another system based on that capability. As such, any experiments to show which
representation or systems are best for particular tasks will have to be doubly careful about
choosing a data set.
The authors would like to thank EPSRC for providing the funding (Grant no. EP/D052629/1)
through which this paper was produced, and the expert reviewers for providing essential
feedback on previous drafts of this article. Also thanks to those researchers who were kind
enough to grant permission to use screenshots of their visualisations in this paper.
1 Noik EG. A Space of Presentation Emphasis Techniques for Visualizing Graphs. Graphics
Interface 1994 (Banff, Alberta, Canada), Morgan-Kaufmann Publishers; 225-234.
2 Herman I, Melançon G, and Marshall MS. Graph Visualisation and Navigation in Information
Visualisation: a Survey. IEEE Transactions on Visualization and Computer Graphics 2000; 6(1):
3 Nguyen QV, Space Efficient Visualisation of Large Hierarchies. PhD Thesis, Faculty of
Information Technology, University of Technology, Sydney, Australia, 2005; 171+xix pp.
4 Nussbaumer A, Hierarchy Browsers. Master's Thesis, Institute for Information Systems and
Computer Media (IICM), Graz University of Technology, Graz, Austria, 2005; 109 pp.
5 Graham M, Visualising Multiple Overlapping Classification Hierarchies. PhD Thesis, School of
Computing, Napier University, Edinburgh, UK, 2001; 182 pp.
6 Steel M, Dress AWM, and Böcker S. Simple but Fundamental Limitations on Supertree and
Consensus Tree Methods. Systematic Biology 2000; 49(2): 363-368.
7 Priss U. Facet-like Structures in Computer Science. Axiomathes 2008; 18(2): 243-255.
8 Sifer M. Filter co-ordinations for exploring multi-dimensional data. Journal of Visual Languages
and Computing 2006; 17(2): 107-125.
9 Shvaiko P and Euzenat J. Ontology Matching [Website]. (Accessed 16 December, 2008).
10 Aumueller D, Do H-H, Massmann S, and Rahm E. Schema and Ontology Matching with
COMA++. ACM SIGMOD 2005 (Baltimore, Maryland, USA), ACM Press; 906-908.
11 Altova GmbH. MapForce (Version 2008 rel. 2 sp. 2) [Computer Software]. Retrieved 16
December, 2008. Available from http://www.altova.com/downloadtrialmapforce3.html
12 Wang G, Rifaieh R, Goguen J, Zavesov V, Rajasekar A, and Miller M. Towards User Centric
Schema Mapping Platform. International Workshop on Semantic Data and Service Integration
2007 (Vienna, Austria).
13 Eick SG, Steffen JL, and Sumner EE, Jr. Seesoft - A Tool For Visualizing Line Oriented Software
Statistics. IEEE Transactions on Software Engineering 1992; 18(11): 957-968.
14 Gîrba T, Lanza M, and Ducasse S. Characterizing the Evolution of Class Hierarchies. 9th
European Conference on Software Maintenance and Reengineering - CSMR 2005 (Manchester,
UK), IEEE Computer Society Press; 2-11.
15 Wu X, Storey M-A, Murray A, and Lintern R. Visualization to Support Version Control Software:
Suggested Requirements. VisSoft 2003 (Amsterdam, Netherlands); 80-86.
16 Fuchsberger C, Falchi M, Forer L, and Pramstaller PP. PedVizApi: a Java API for the interactive,
visual analysis of extended pedigrees. Bioinformatics 2008; 24(2): 279-281.
17 Storey M-A, Musen M, Silva J, Best C, Ernst N, Fergerson R, and Noy N. Jambalaya: Interactive
visualization to enhance ontology authoring and knowledge acquisition in Protégé. Workshop on
Interactive Tools for Knowledge Capture (K-CAP) 2001 (Victoria, British Columbia, Canada).
18 McGuffin M and Schraefel MC. A Comparison of Hyperstructures: Zzstructures, mSpaces, and
Polyarchies. ACM Hypertext 2004 (Santa Cruz, California, USA), ACM Press; 153-162.
19 Furnas GW and Zacks J. Multitrees: Enriching and Reusing Hierarchical Structure. ACM CHI
1994 (Boston, Massachusetts, USA), ACM Press; 330-336.
20 Wittenburg K, Das D, Hill W, and Stead L. Group Asynchronous Browsing on the World Wide
Web. Fourth International World Wide Web Conference 1995 (Boston, Massachusetts, USA); 51-
21 Sifer M. Exploring Web Site Log Data with a Multi-Classification Interface. IEEE Conference on
Information Visualisation 2003 (London, UK), IEEE Computer Society Press; 94-101.
22 McGuffin M and Balakrishnan R. Interactive Visualization of Genealogical Graphs. IEEE InfoVis
2005 (Minneapolis, Minnesota, USA), IEEE Computer Society Press; 17-24.
23 Robertson G, Cameron K, Czerwinski M, and Robbins D. Animated visualization of multiple
intersecting hierarchies. Information Visualization 2002; 1(1): 50-65.
24 Conklin N, Prabhakar S, and North C. Multiple Foci Drill-Down through Tuple and Attribute
Polyarchies in Tabular Data. IEEE InfoVis 2002 (Boston, Massachussets, USA), IEEE Computer
Society Press; 131-134.
25 Graham M and Kennedy J. Extending taxonomic visualisation to incorporate synonymy and
structural markers. Information Visualization 2005; 4(3): 206-223.
26 Dadzie A-S and Burger A. Providing visualisation support for the analysis of anatomy ontology
data. BMC Bioinformatics 2005; 6(74): n/a.
27 Cruz IF, Sunna W, Makar N, and Bathala S. A visual tool for ontology alignment to enable
geospatial interoperability. Journal of Visual Languages and Computing 2007; 18(3): 230-254.
28 Tu Q and Godfrey MW. An Integrated Approach for Studying Architectural Evolution. 10th
International Workshop on Program Comprehension (IWPC) 2002 (Paris, France), IEEE
Computer Society Press; 127-136.
29 Tufte ER, The Visual Display of Quantitative Information. Graphics Press: Cheshire, Connecticut,
30 Reingold EM and Tilford JS. Tidier drawing of trees. IEEE Transactions on Software Engineering
1981; 7(2): 223-228.
31 Beebe NHF. A Bibliography of Tree Drawing Algorithms. Bibliography, Department of
Mathematics, University of Utah, Salt Lake City, 2006; 22pp. Available from
32 Moen S. Drawing Dynamic Trees. IEEE Software 1990; 7(4): 21-28.
33 Johnson B and Shneiderman B. Treemaps: A Space-Filling approach to the visualization of
hierarchical information structures. IEEE Visualization 1991 (San Diego, California, USA), IEEE
Computer Society Press; 284-291.
34 Wang W, Wang H, Dai G, and Wang H. Visualization of Large Hierarchical Data by Circle
Packing. ACM CHI 2006 (Montréal, Québec, Canada), ACM Press; 517-520.
35 Kruskal JB and Landwehr JM. Icicle Plots: Better Displays for Hierarchical Clustering. The
American Statistician 1983; 37(2): 162-168.
36 Stasko J, Catrambone R, Guzdial M, and McDonald K. An evaluation of space-filling information
visualizations for depicting hierarchical structures. International Journal of Human-Computer
Studies 2000; 53(5): 663-694.
37 Robertson GG, Mackinlay JD, and Card SK. Cone Trees: Animated 3D Visualizations of
Hierarchical Information. ACM CHI: Human Factors in Computing Systems 1991 (New Orleans,
Louisiana, USA), ACM Press; 189-194.
38 Bladh T, Carr DA, and Scholl J. Extending Tree-Maps to Three Dimensions: A Comparative
Study. 6th Asia-Pacific Conference on Computer-Human Interaction 2004 (Rotorua, New
Zealand), 3101, Springer-Verlag; 50-59.
39 van Ham F and van Wijk JJ. Beamtrees: Compact Visualization of Large Hierarchies. IEEE
InfoVis 2002 (Boston, Massachussets, USA), IEEE Computer Society Press; 93-100.
40 Cockburn A and McKenzie B. An Evaluation of Cone Trees. BCS HCI 2000 (Sunderland, UK),
41 Kobsa A. User Experiments with Tree Visualization Systems. IEEE InfoVis 2004 (Austin, Texas,
USA), IEEE Computer Society Press; 9-16.
42 Shen Z and Ma K-L. Path Visualization for Adjacency Matrices. Eurographics/ IEEE-VGTC
Symposium on Visualization 2007 (Norrköping, Sweden), Eurographics; 83-90.
43 Lü H and Fogarty J. Cascaded Treemaps: Examining the Visibility and Stability of Structure in
Treemaps. Graphics Interface 2008 (Windsor, Ontario, Canada), 322, Canadian Information
Processing Society; 259-266.
44 Zhao S, McGuffin MJ, and Chignell MH. Elastic Hierarchies: Combining Treemaps and Node-
Link Diagrams. IEEE InfoVis 2005 (Minneapolis, Minnesota, USA), IEEE Computer Society
45 Nguyen QV and Huang ML. EncCon: an approach to constructing interactive visualization of large
hierarchical data. Information Visualization 2005; 4(1): 1-21.
46 Wilson RM and Bergeron RD. Dynamic Hierarchy Specification and Visualization. IEEE InfoVis
1999 (San Francisco, California, USA), IEEE Computer Society Press; 65-72.
47 Urbanek S. Different ways to see a tree - KLIMT. 15th Conference on Computational Statistics,
COMPSTAT 2002 (Berlin, Germany), Physica-Verlag; 303-308.
48 Schedl M, Knees P, Widmer G, Seyerlehner K, and Pohle T. Browsing the Web Using Stacked
Three-Dimensional Sunbursts to Visualize Term Co-Occurrences and Multimedia Content. IEEE
Visualization 2007 (Sacramento, California, USA), Poster Compendium, IEEE Computer Society
49 Teoh ST. A Study on Multiple Views for Tree Visualization. Visualization and Data Analysis
2007 (San Jose, California, USA), 6495, SPIE Press; 99-110.
50 Kules B, Shneiderman B, and Plaisant C. Data Exploration with Paired Hierarchical
Visualizations: Initial Designs of PairTrees. National Conf. on Digital Government Research 2003
(Boston, Massachusetts, USA), 130 - ACM International Conference Proceeding Series, Digital
Government Research Center
51 Mohammadi-Aragh MJ and Jankun-Kelly TJ. MoireTrees: Visualization and Interaction for Multi-
Hierarchical data. Eurographics / IEEE VGTC Symposium on Visualization 2005 (Leeds, UK),
52 Weiland M and Dachselt R. Facet Folders: Flexible Filter Hierarchies with Faceted Metadata.
ACM CHI 2008 (Florence, Italy), ACM Press; 3735-3740.
53 Dachselt R and Frisch M. Mambo: A Facet-based Zoomable Music Browser. 6th international
conference on Mobile and Ubiquitous Multimedia 2007 (Oulu, Finland), ACM Press; 110-117.
54 Smith G, Czerwinski M, Meyers B, Robbins D, Robertson G, and Tan DS. FacetMap: A Scalable
Search and Browse Visualization. IEEE Transactions on Visualization and Computer Graphics
2006; 12(5): 797-804.
55 Lee B, Smith G, Robertson GG, Czerwinski M, and Tan DS. FacetLens: Exposing Trends and
Relationships to Support Sensemaking within Faceted Datasets. ACM CHI 2009 (Boston,
Massachusetts, USA), ACM Press; 1293-1302.
56 Yee K-P, Swearingen K, Li K, and Hearst M. Faceted Metadata for Image Search and Browsing.
ACM CHI 2003 (Fort Lauderdale, Florida, USA), ACM Press; 401-408.
57 Graham M and Kennedy J. Exploring Multiple Trees through DAG Representations. IEEE
Transactions on Visualization and Computer Graphics 2007; 13(6): 1294-1301.
58 Munzner T, Guimbretière F, Tasiran S, Zhang L, and Zhou Y. TreeJuxtaposer: Scalable Tree
Comparison using Focus+Context with Guaranteed Visibility. ACM Transactions on Graphics
2003; 22(3): 453-462.
59 Sheth N, Börner K, Baumgartner J, Mane K, and Wernert E. Treemap, Radial tree, and 3D Tree
Visualizations. IEEE InfoVis Poster Compendium 2003 (Seattle, Washington, USA), IEEE
Computer Society Press; 128-129.
60 Wan Zainon WN and Calder P. Visualising Phylogenetic Trees. Seventh Australasian User
Interface Conference 2006 (Hobart, Australia), 50, Australian Computer Society; 145-152.
61 Craig P and Kennedy J. Concept Relationship Editor: A visual interface to support the assertion of
synonymy relationships between taxonomic classifications. Visualization and Data Analysis 2008
(San Jose, California, USA), 6809, SPIE Press; 12.
62 Chiticariu L, Hernández MA, Kolaitis PG, and Popa L. Semi-Automatic Schema Integration in
Clio. VLDB 2007 (Austria, Vienna), ACM Press; 1326-1329.
63 Purchase H. Which Aesthetic Has the Greatest Effect on Human Understanding? Graph Drawing
1997 (Rome, Italy), LNCS 1353, Springer-Verlag; 248-261.
64 Eades P and Wormald NC. Edge crossings in drawings of bipartite graphs. Algorithmica 1994;
65 Robertson GG, Czerwinski MP, and Churchill JE. Visualization of Mappings Between Schemas.
ACM CHI 2005 (Portland, Oregon, USA), ACM Press; 431-439.
66 Holten D and Van Wijk JJ. Visual Comparison of Hierarchically Organized Data. Computer
Graphics Forum 2008; 27(3): 759-766.
67 Buchin K, Buchin M, Byrka J, Nöllenburg M, Okamoto Y, Silveira R, and Wolff A. Drawing
(Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability. Graph
Drawing 2008 (Heraklion, Crete, Greece), LNCS 5417, Springer-Verlag; 324-335.
68 Parr CS, Lee B, Campbell D, and Bederson BB. Visualizations for taxonomic and phylogenetic
trees. Bioinformatics 2004; 20(17): 2997-3004.
69 Hong JY, D'Andries J, Richman M, and Westfall M. Zoomology: Comparing Two Large
Hierarchical Trees. IEEE InfoVis Poster Compendium 2003 (Seattle, Washington, USA), IEEE
Computer Society Press; 120-121.
70 Auber D, Delest M, Domenger JP, Ferraro P, and Strandh R. EVAT: Environment for
Vizualisation and Analysis of Trees. IEEE InfoVis Poster Compendium 2003 (Seattle, Washington,
USA), IEEE Computer Society Press; 124-125.
71 Information Visualization Benchmarks Repository. InfoVis 2003 Contest - Visualization and
PairWise Comparison of Trees [Webpage]. (Accessed 20 July, 2009).
72 Microsoft Corp. WinDiff (Version 5.1) [Computer Software]. Retrieved 15 December, 2008.
Available from http://support.microsoft.com/kb/159214
73 Snyder J, Dobbe W, Keel J, Bruggeman O, and Firebaugh J. Kompare (Version 3.5) [Computer
Software]. Retrieved 15 December, 2008. Available from http://www.kde.org/download/
74 Altova GmbH. DiffDog (Version 2008 rel. 2 sp. 2) [Computer Software]. Retrieved 15 December,
2008. Available from http://www.altova.com/download/diffdog/diff_merge_tool.html
75 David J, Guillet F, Gras R, and Briand H. An interactive, asymmetric and extensional method for
matching conceptual hierarchies. EMOI-INTEROP - Open Interop Workshop on Enterprise
Modelling and Ontologies for Interoperability 2006 (Luxembourg), 200, CEUR-WS.org.
76 Bossung S, Stoeckle H, Grundy J, Amor R, and Hosking J. Automated Data Mapping
Specification via Schema Heuristics and User Interaction. 19th IEEE International Conference on
Automated Software Engineering (ASE) 2004 (Linz, Austria), IEEE Computer Society Press; 208-
77 Raghavan A, Schema Mapper: A Visualization Tool for Incremental Semi-automatic Mapping-
based Integration of Heterogeneous Collections into Archaeological Digital Libraries: The
ETANA-DL Case Study. Master's Thesis, Dept of Computer Science, Virginia Polytechnic Institute
and State University, Blacksburg, Virginia, USA, 2005; 66+vii pp.
78 Ghoniem M and Fekete J-D. Animating Treemaps. 18th HCIL Symposium - Workshop on Treemap
Implementations and Applications 2001 (University of Maryland, College Park, Maryland, USA).
79 Wittenburg K and Sigman E. Visual Focusing and Transition Techniques in a Treeviewer for Web
Information Access. Visual Languages 1997 (Capri, Italy), IEEE Computer Society Press; 20-27.
80 Wilkinson L and Friendly M. The History of the Cluster Heat Map. The American Statistician
2009; 63(2): 179-184.
81 Eisen M. TreeView (Version 1.60) [Computer Software]. Available from
82 van Ham F. Using Multilevel Call Matrices in Large Software Projects. IEEE InfoVis 2003
(Seattle, Washington, USA), IEEE Computer Society Press; 227-232.
83 Cyberpromote. DiffDaff (Version 1.0) [Computer Software]. Retrieved 3 April, 2009. Available
84 Tu Y and Shen H-W. Visualizing Changes of Hierarchical Data using Treemaps. IEEE
Transactions on Visualization and Computer Graphics 2007; 13(6): 1286-1293.
85 Lee B, Robertson GG, Czerwinski M, and Parr CS. CandidTree: visualizing structural uncertainty
in similar hierarchies. Information Visualization 2007; 6(3): 233-246.
86 Isenberg P and Carpendale S. Interactive Tree Comparison for Co-located Collaborative
Information Visualization. IEEE Transactions on Visualization and Computer Graphics 2007;
87 Inselberg A and Dimsdale B. Parallel Coordinates: A Tool for Visualizing Multidimensional
Geometry. IEEE Visualization 1990 (San Francisco, California, USA), IEEE Computer Society
88 Wernert EA, Berry DK, Huffman JN, and Stewart CA. Tree3D - A System for Temporal and
Comparative Analysis of Phylogenetic Trees. IEEE InfoVis Poster Compendium 2003 (Seattle,
Washington, USA), IEEE Computer Society Press; 114-115.
89 Stewart CA, Hart D, Berry DK, Olsen GJ, Wernert EA, and Fischer W. Parallel implementation
and performance of fastDNAml - a program for maximum likelihood phylogenetic inference.
ACM/IEEE Conference on Supercomputing 2001 (Denver, Colorado, USA), ACM/IEEE
Computer Society; 20-20.
90 Dwyer T and Schreiber F. Optimal Leaf Ordering for Two and a Half Dimensional Phylogenetic
Tree Visualisation. Australasian Symposium on Information Visualisation 2004 (Dunedin, New
Zealand), 35, Australian Computer Society; 109-115.
91 Telea A and Auber D. Code Flows: Visualizing Structural Evolution of Source Code. Computer
Graphics Forum 2008; 27(3): 831-838.
92 Tominski C, Abello J, and Schumann H. Axes-Based Visualizations with Radial Layouts. 19th
ACM Symposium on Applied Computing 2004 (Nicosia, Cyprus), ACM Press; 1242-1247.
93 Chi EH, Pitkow J, Mackinlay J, Pirolli P, Gossweiler R, and Card SK. Visualizing the Evolution of
Web Ecologies. ACM CHI 1998 (Los Angeles, California, USA), ACM Press; 400-407.
94 Spenke M and Beilken C. Visualisation of trees as highly compressed tables with InfoZoom. IEEE
InfoVis 2003 (Seattle, Washington, USA), IEEE Computer Society Press; 122-123.
95 Kutz DO. Examining the Evolution and Distribution of Patent Classifications. IEEE Conference on
Information Visualisation 2004 (London, UK), IEEE Computer Society Press; 983-988.
96 Morse DR, Ytow N, and Roberts DM. Comparison of multiple taxonomic hierarchies using
TaxoNote. IEEE InfoVis Poster Compendium 2003 (Seattle, Washington, USA), IEEE Computer
Society Press; 126-127.
97 Daida JM, Hilss AM, Ward DJ, and Long SL. Visualizing Tree Structures in Genetic
Programming. Genetic Programming and Evolvable Machines 2005; 6(1): 79-110.
98 Slack J, Hildebrand K, and Munzner T. PRISAD: A Partitioned Rendering Infrastructure for
Scalable Accordion Drawing. Information Visualization 2006; 5(2): 137-151.
99 Chevenet F, Brun C, Bañuls A-L, Jacq B, and Christen R. TreeDyn: towards dynamic graphics and
annotations for analyses of trees. BMC Bioinformatics 2006; 7: 439.
100 Graham M, Kennedy J, and Downey L. Visual Comparison and Exploration of Natural History
Collections. ACM AVI 2006 (Venice, Italy), ACM Press; 310-313.
101 Card SK, Suh B, Pendleton BA, Heer J, and Bodnar JW. TimeTree: Exploring Time Changing
Hierarchies. IEEE VAST 2006 (Baltimore, Maryland, USA), IEEE Computer Society Press; 3-10.
102 Herman I, Melançon G, de Ruiter MM, and Delest M. Latour - a tree visualisation system. Graph
Drawing 1999 (Stirin Castle, Prague, Czech Republic), LNCS 1731, Springer-Verlag; 392-399.
103 Wettel R and Lanza M. Visual Exploration of Large-Scale System Evolution. 15th Working
Conference on Reverse Engineering (WCRE) 2008 (Antwerp, Belgium), IEEE Computer Society
104 Becker RA and Cleveland WS. Brushing Scatterplots. Technometrics 1987; 29(2): 127-142.
105 Abello J and van Ham F. Matrix Zoom: A Visual Interface to Semi-external Graphs. IEEE InfoVis
2004 (Austin, Texas, USA), IEEE Computer Society Press; 183-190.
106 Wong PC, Foote H, Mackey P, Perrine K, and Chin Jr. G. Generating Graphs for Visual Analytics
through Interactive Sketching. IEEE Transactions on Visualization and Computer Graphics 2006;
107 Florentz B and Muecke T. Unification and Evaluation of Graph Drawing Algorithms for Different
Application Domains. International Conference on Information Visualization 2006 (London, UK),
IEEE Computer Society Press; 475-482.
108 Mank FWM, CristalView - The visualization of a Cristal. Master's Thesis, Mathematics and
Computer Science, Technische Universiteit Eindhoven, Eindhoven, Netherlands, 2005; 115+v pp.
109 Burch M and Diehl S. Trees in a Treemap: Visualizing Multiple Hierarchies. Visualization and
Data Analysis 2006 (San Jose, California, USA), 6060, SPIE Press; 224-235.
110 D'Ambros M and Lanza M. Software Bugs and Evolution: A Visual Approach to Uncover Their
Relationship. 10th European Conference on Software Maintenance and Reengineering - CSMR
2006 2006 (Bari, Italy), IEEE Computer Society Press; 227-236.
111 Melançon G and Herman I. DAG Drawing from an Information Visualization Perspective.
Eurographics/IEEE TCVG Symposium on Visualization (VisSym) 2000 (Amsterdam, The
Netherlands), Springer-Verlag; 3-12.
112 Reiss SP. An Engine for the 3D Visualization of Program Information. Journal of Visual
Languages and Computing 1995; 6(3): 299-323.
113 Hillis DM, Heath TA, and St. John K. Analysis and Visualization of Tree Space. Systematic
Biology 2005; 54(3): 471-482.
114 Maddison WP and Maddison DR. Mesquite: a modular system for evolutionary analysis (Version
1.06) [Computer Software]. Retrieved 2nd April, 2009. Available from http://mesquiteproject.org
115 Amenta N and Klingner J. Case Study: Visualizing Sets of Evolutionary Trees. IEEE InfoVis 2002
(Boston, Massachusetts, USA), IEEE Computer Society Press; 71-74.
116 Meyer J. A Framework For Large-Scale Interactive Visualization Of Phylogenetic Trees. IASTED
International Conference on Visualization, Imaging and Image Analysis 2006 (Palma de Mallorca,
Spain), ACTA Press; 122-129.
117 Graham M, Kennedy JB, and Hand C. A Comparison of Set-Based and Graph-Based
Visualisations of Overlapping Classification Hierarchies. ACM AVI 2000 (Palermo, Italy), ACM
118 Barlow T and Neville P. A Comparison of 2-D Visualisations of Hierarchies. IEEE InfoVis 2001
(San Diego, California, USA), IEEE Computer Society Press; 131-138.
119 Andrews K and Kasanicka J. A Comparative Study of Four Hierarchy Browsers using the
Hierarchical Visualisation Testing Environment (HVTE). IEEE IV Conference 2007 (Zurich,
Switzerland), IEEE Computer Society Press; 81-86.
120 Parunak HVD. Don't Link Me In: Set Based Hypermedia for Taxonomic Reasoning. ACM
Hypertext 1991 (San Antonio, Texas, USA), ACM Press; 233-242.