Drawing directed graphs using quadratic programming |
| |
Authors: | Dwyer Tim Koren Yehuda Marriott Kim |
| |
Affiliation: | Clayton Sch. of Inf. Technol., Monash Univ., Clayton, Vic., Australia; |
| |
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 nonhierarchical, 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 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. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|