Drawing Large Graphs by Multilevel Maxent-Stress Optimization

Meyerhenke, Henning and Nöllenburg, Martin and Schulz, Christian (2015) Drawing Large Graphs by Multilevel Maxent-Stress Optimization. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 30-43(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_3).

Full text not available from this repository.


Drawing large graphs appropriately is an important step for the visual analysis of data from real-world networks. Here we present a novel multilevel algorithm to compute a graph layout with respect to a recently proposed metric that combines layout stress and entropy. As opposed to previous work, we do not solve the linear systems of the maxent-stress metric with a typical numerical solver. Instead we use a simple local iterative scheme within a multilevel approach. To accelerate local optimization, we approximate long-range forces and use shared-memory parallelism. Our experiments validate the high potential of our approach, which is particularly appealing for dynamic graphs. In comparison to the previously best maxent-stress optimizer, which is sequential, our parallel implementation is on average 30 times faster already for static graphs (and still faster if executed on one thread) while producing a comparable solution quality.

Item Type: Conference Paper
Classifications: M Methods > M.300 Dynamic / Incremental / Online
M Methods > M.400 Force-directed / Energy-based
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 16:21
Last Modified: 04 May 2016 16:21
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1475

Actions (login required)

View Item View Item