Paper Info
Title
Clustered edge routing
Abstract
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.
Year
DOI
Venue
2015
10.1109/PACIFICVIS.2015.7156356
2015 IEEE Pacific Visualization Symposium (PacificVis)
Keywords
Field
DocType
I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Multipath routing,Visibility graph,Vertex (geometry),Circle graph,Destination-Sequenced Distance Vector routing,Theoretical computer science,Spanner,Cluster analysis,Theta graph,Mathematics
Conference
ISSN
Citations 
PageRank 
2165-8765
3
0.39
References 
Authors
22
2
Name
Order
Citations
PageRank
Quirijn W. Bouts1103.05
Bettina Speckmann287679.40