Details

Autor(en) / Beteiligte

• Lipp, Fabian
• Wolff, Alexander
• Zink, Johannes

Titel

Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition

Ist Teil von

• Graph Drawing and Network Visualization, p.52-59

Ort / Verlag

Cham: Springer International Publishing

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• The force-directed paradigm is one of the few generic approaches to drawing graphs. Since force-directed algorithms can be extended easily, they are used frequently. Most of these algorithms are, however, quite slow on large graphs as they compute a quadratic number of forces in each iteration. We speed up this computation by using an approximation based on the well-separated pair decomposition. We perform experiments on a large number of graphs and show that we can strongly reduce the runtime—even on graphs with less then a hundred vertices—without a significant influence on the quality of the drawings (in terms of number of crossings and deviation in edge lengths).