Drawing directed graphs using quadratic programming.
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.
Dwyer
Tim
T
Clayton School of Information Technology, Monash University, Victoria, Australia. Tim.Dwyer@infotech.monash.edu.au
Koren
Yehuda
Y
Marriott
Kim
K
D003196:Computer Graphics; D003198:Computer Simulation; D003626:Data Display; D016208:Databases, Factual; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D016014:Linear Models; D014584:User-Computer Interface