Information Technology Reference
In-Depth Information
combined DAGMap and node-link layout. We then provide details on how the
DAGMap is computed from the DAG. Returning to our case study, we explain how
the node-link and DAGMap views are linked through user interaction.
7.2
Related Work
7.2.1
Node Link Diagram
A node-link diagram is an intuitive representation of a hierarchical dataset. Each
element of the dataset is represented as a node, and relationships between elements
are represented as edges linking two nodes. Tree hierarchies have been widely
explored, and different types of layout algorithms have been proposed. Figure
7.2
shows different representations of the same hierarchy using several algorithms.
These algorithms can be extended to a directed acyclic graph. When drawing a
DAG, source nodes are often placed at the top and are said to have level 0. The level
of a node is then set to the length of the longest path connecting the node to a source
node. In this process, we make sure that all of the edges are directed downwards
(see Fig.
7.1
a).
Tree layout algorithms (see
di Battista, Eades, Tamassia, & Tollis
,
1998
)draw
internal nodes as well as leaf nodes, thus explicitly showing the relative positions
of the nodes in the tree. These properties also remain the same for the layout of the
DAGs (
Eades & Sugiyama
,
1990
).
The quality and readability of these node-link representations are usually
measured in terms of the ability of the representations to avoid edge crossings
(see
Gutwenger & Mutzel.
,
2004
, for instance). Node-link diagrams are useful for
representing DAGs but are less efficient when the representation involves semantic
information in terms of node sizes and colors. Indeed, even when drawing DAGs
with nodes of equal sizes, layers must be kept sufficiently apart to ensure that the
diagram is readable.
Fig. 7.2
Different layouts of the same hierarchy using different algorithms. (
a
) Dendogram.
(
b
)Walker(
Reingold & Tilford
,
1981
;
Wal ker
,
1990
). (
c
) Cone tree (
Carriere & Kazman
,
1995
)
Search WWH ::
Custom Search