Drawing Large Graphs by Low-Rank Stress Majorization
Loading...
Date
2012
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd.
Abstract
Optimizing a stress model is a natural technique for drawing graphs: one seeks an embedding into Rd which best
preserves the induced graph metric. Current approaches to solving the stress model for a graph with jVj nodes
and jEj edges require the full all-pairs shortest paths (APSP) matrix, which takes O(jVj2 log jEj+jVjjEj) time
and O(jVj2) space. We propose a novel algorithm based on a low-rank approximation to the required matrices.
The crux of our technique is an observation that it is possible to approximate the full APSP matrix, even when
only a small subset of its entries are known. Our algorithm takes time O(kjVj+jVj logjVj+jEj) per iteration with
a preprocessing time of O(k3 +k(jEj+jVj logjVj)+k2jVj) and memory usage of O(kjVj), where a user-defined
parameter k trades off quality of approximation with running time and space. We give experimental results which
show, to the best of our knowledge, the largest (albeit approximate) full stress model based layouts to date.
Description
@article{10.1111:j.1467-8659.2012.03090.x,
journal = {Computer Graphics Forum},
title = {{Drawing Large Graphs by Low-Rank Stress Majorization}},
author = {Khoury, Marc and Hu, Yifan and Krishnan, Shankar and Scheidegger, Carlos},
year = {2012},
publisher = {The Eurographics Association and Blackwell Publishing Ltd.},
ISSN = {1467-8659},
DOI = {10.1111/j.1467-8659.2012.03090.x}
}