ImPrEd: An Improved Force-Directed Algorithm that Prevents Nodes from Crossing Edges

Simple item page
dc.contributor.authorSimonetto, Paoloen_US
dc.contributor.authorArchambault, Danielen_US
dc.contributor.authorAuber, Daviden_US
dc.contributor.authorBourqui, Romainen_US
dc.contributor.editorH. Hauser, H. Pfister, and J. J. van Wijken_US
dc.date.accessioned2014-02-21T20:23:52Z
dc.date.available2014-02-21T20:23:52Z
dc.date.issued2011en_US
dc.description.abstractPrEd [Ber00] is a force-directed algorithm that improves the existing layout of a graph while preserving its edge crossing properties. The algorithm has a number of applications including: improving the layouts of planar graph drawing algorithms, interacting with a graph layout, and drawing Euler-like diagrams. The algorithm ensures that nodes do not cross edges during its execution. However, PrEd can be computationally expensive and overlyrestrictive in terms of node movement. In this paper, we introduce ImPrEd: an improved version of PrEd that overcomes some of its limitations and widens its range of applicability. ImPrEd also adds features such as flexible or crossable edges, allowing for greater control over the output. Flexible edges, in particular, can improve the distribution of graph elements and the angular resolution of the input graph. They can also be used to generate Euler diagrams with smooth boundaries. As flexible edges increase data set size, we experience an execution/drawing quality trade off. However, when flexible edges are not used, ImPrEd proves to be consistently faster than PrEd.en_US
dc.description.number3en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume30en_US
dc.identifier.doi10.1111/j.1467-8659.2011.01956.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2011.01956.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltd.en_US
dc.subjectG.2.2 [Discrete Mathematics]en_US
dc.subjectGraph Theoryen_US
dc.subjectGraph Algorithmsen_US
dc.titleImPrEd: An Improved Force-Directed Algorithm that Prevents Nodes from Crossing Edgesen_US
Files
Collections
30-Issue 3
EuroVis11: Eurographics/ IEEE Symposium on Visualization