- Drawing Directed Graphs Using Quadratic Programming
- Tim Dwyer, Yehuda Koren, and Kim Marriott
- IEEE Trans. Vis. Comput. Graph. 12(4) pp. 536-548, 2006.
PDF (2437K)
- Abstract
We describe a new method for visualization of directed graphs. The method
combines constraint programming techniques with a high performance
force-directed placement (FDP) algorithm. The resulting placements highlight
hierarchy in directed graphs while retaining useful properties of FDP; such as
emphasis of symmetries and preservation of proximity relations. Our algorithm
automatically identifies those parts of the digraph that contain hierarchical
information and draws them accordingly. Additionally, those parts that do not
contain hierarchy are drawn at the same quality expected from a
non-hierarchical, undirected layout algorithm. Our experiments show that this
new approach is better able to convey the structure of large digraphs than the
most widely used hierarchical graph-drawing method. An interesting application
of our algorithm is {\em directional multidimensional scaling (DMDS)}. DMDS
deals with low-dimensional embedding of multivariate data where we want to
emphasize the overall flow in the data (e.g. chronological progress) along one
of the axes.
|
