Clustered edge routing

Q.W. Bouts, B. Speckmann

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

6 Citaten (Scopus)
133 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.
Originele taal-2Engels
Titel2015 IEEE Pacific Visualization Symposium (PacificVis2015, Hangzhou, China, April 14-17, 2015)
RedacteurenS. Liu, G. Scheuermann, S. Takahashi
UitgeverijInstitute of Electrical and Electronics Engineers
StatusGepubliceerd - 2015

Vingerafdruk Duik in de onderzoeksthema's van 'Clustered edge routing'. Samen vormen ze een unieke vingerafdruk.

Citeer dit