Clustered edge routing

Q.W. Bouts, B. Speckmann

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)
237 Downloads (Pure)


The classic method to depict graphs is a node-link diagram where vertices (nodes) are associated with each object and edges (links) connect related objects. However, node-link diagrams quickly appear cluttered and unclear, even for moderately sized graphs. If the positions of the nodes are fixed then suitable link routing is the only option to reduce clutter. We present a novel link clustering and routing algorithm which respects (and if desired refines) user-defined clusters on links. If no clusters are defined a priori we cluster based on geometric criteria, that is, based on a well-separated pair decomposition (WSPD).We route link clusters individually on a sparse visibility spanner. To completely avoid ambiguity we draw each individual link and ensure that clustered links follow the same path in the routing graph. We prove that the clusters induced by the WSPD consist of compatible links according to common similarity measures as formalized by Holten and van Wijk [17]. The greedy sparsification of the visibility graph allows us to easily route around obstacles. Our experimental results are visually appealing and convey a sense of abstraction and order.
Original languageEnglish
Title of host publication2015 IEEE Pacific Visualization Symposium (PacificVis2015, Hangzhou, China, April 14-17, 2015)
EditorsS. Liu, G. Scheuermann, S. Takahashi
PublisherInstitute of Electrical and Electronics Engineers
Publication statusPublished - 2015


Dive into the research topics of 'Clustered edge routing'. Together they form a unique fingerprint.

Cite this