Drawing Large Graphs by Low-Rank Stress Majorization

Simple item page
dc.contributor.authorKhoury, Marcen_US
dc.contributor.authorHu, Yifanen_US
dc.contributor.authorKrishnan, Shankaren_US
dc.contributor.authorScheidegger, Carlosen_US
dc.contributor.editorS. Bruckner, S. Miksch, and H. Pfisteren_US
dc.date.accessioned2015-02-28T07:01:46Z
dc.date.available2015-02-28T07:01:46Z
dc.date.issued2012en_US
dc.description.abstractOptimizing 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.en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume31
dc.identifier.doi10.1111/j.1467-8659.2012.03090.x
dc.identifier.issn1467-8659en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2012.03090.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltd.en_US
dc.titleDrawing Large Graphs by Low-Rank Stress Majorizationen_US
Files
Collections
31-Issue 3
EuroVis12: Eurographics Conference on Visualization