-------------------- More Recent Research -------------------- - The article presents the barycentric heuristic for reordering nodes in an arc diagram, for example. In investigating the matter a bit more, I have found preliminary theoretical and empirical evidence that the barycentric heuristic works slightly better if, when computing the average position of neighbors, we give a weighting to each node's current position that is slightly greater than 1.0. So, if we define a variable weight = 1.1 we could then modify two lines of the pseudocode in the article to implement the weighting (lines 5 and 11 below, both starred). I don't know if the matter of this weighting has been investigated before, but I recommend readers use this weighting in their implementations. It seems to allow the algorithm to converge faster, in some cases. 1 // compute average position of neighbors 2 for i1 = 0 to N-1 3 node1 = nodes[i1] 4 p1 = positionOfNode(i1) 5* sum = p1 * weight 6 for j = 0 to node1.neighbors.length-1 7 i2 = node1.neighbors[j] 8 node2 = nodes[i2] 9 p2 = positionOfNode(i2) 10 sum = sum + p2 11* orderedNodes[p1].average = sum / ( node1.neighbors.length + weight ) 12 13 // sort the array according to the values of average 14 sort( orderedNodes, comparator ) - For a survey of algorithms for reordering, see Michael Behrisch, Benjamin Bach, Nathalie Henry Riche, Tobias Schreck, Jean-Daniel Fekete Matrix Reordering Methods for Table and Network Visualization Computer Graphics Forum 35(3), June 2016, pages 693-716 (EuroVis 2016 State of The Art Report (STAR)) https://hal.inria.fr/hal-01326759 http://dx.doi.org/10.1111/cgf.12935 - I have learned about a much more efficient way to implement force-directed layout: stress majorization. The article "Graph drawing by stress majorization" by Gansner, Koren, and North ( http://scholar.google.ca/scholar?q=Gansner+Koren+North+%22Graph+drawing+by+stress+majorization%22 ) describes this. Much of the article presents somewhat complicated mathematics, however most of these details can be ignored. The reader can skip over equations (3) through (11) and focus on implementing equation (12), which is simple to implement. Each iteration of the algorithm brings the layout closer to the optimal layout, with none of the stability problems or oscillations associated with traditional force-directed layout. Before performing stress majorization, you must generate a matrix of desired distances d_{i,j} between nodes i and j, for all pairs of nodes, to serve as input to the stress majorization. This matrix can be computed efficiently and easily with the Floyd-Warshall algorithm ( https://en.wikipedia.org/wiki/Floyd-Warshall_algorithm ). ----------------------- Additional Related Work ----------------------- - For more on edge simplification in node-link diagrams, see Dwyer, Tim, Nathalie Henry Riche, Kim Marriott, and Christopher Mears. "Edge compression techniques for visualization of dense directed graphs." IEEE transactions on visualization and computer graphics 19, no. 12 (2013): 2596-2605. Bach, Benjamin, Nathalie Henry Riche, Christophe Hurter, Kim Marriott, and Tim Dwyer. "Towards unambiguous edge bundling: Investigating confluent drawings for network visualization." IEEE Transactions on Visualization & Computer Graphics 1 (2017): 1-1. - The article cites Alper et al. (2011) as an example of visualizing subsets of nodes. More recent work on this topic includes Kasper Dinkla, Marc J. van Kreveld, Bettina Speckmann, and Michel A. Westenberg Kelp Diagrams: Point Set Membership Visualization Eurographics Conference on Visualization (EuroVis) 2012 DOI: 10.1111/j.1467-8659.2012.03080.x Meulemans, Wouter, Nathalie Henry Riche, Bettina Speckmann, Basak Alper, and Tim Dwyer. "KelpFusion: A hybrid set visualization technique." IEEE transactions on visualization and computer graphics 19, no. 11 (2013): 1846-1858. http://scholar.google.ca/scholar?q=kelpfusion+meulemans+riche @inproceedings{efrat2014, author={Efrat, Alon and Hu, Yifan and Kobourov, Stephen G and Pupyrev, Sergey}, title={{MapSets}: Visualizing Embedded and Clustered Graphs}, booktitle={Symposium on Graph Drawing (GD)}, year={2014} } % http://vcg.github.io/upset/about/ @article{lex2014, author = {Lex, Alexander and Gehlenborg, Nils and Strobelt, Hendrik and Vuillemot, Romain and Pfister, Hanspeter}, title = {{UpSet}: Visualization of Intersecting Sets}, journal = {{IEEE} Transactions on Visualization and Computer Graphics ({InfoVis} '14)}, year = {2014}, } Corinna Vehlow, Fabian Beck, and Daniel Weiskopf The State of the Art in Visualizing Group Structures in Graphs Eurographics Conference on Visualization (EuroVis) (2015) http://groups-in-graphs.corinna-vehlow.com/ Visualizing Sets and Set-typed Data: State-of-the-Art and Future Challenges Bilal Alsallakh, Luana Micallef, Wolfgang Aigner, Helwig Hauser, Silvia Miksch, Peter Rodgers EuroVis 2014 http://www.cvast.tuwien.ac.at/node/657 http://www.setviz.net/ , http://www.cvast.tuwien.ac.at/SetViz http://www.cvast.tuwien.ac.at/~alsallakh/SetViz/literature/www/ Rodgers et al. Visualizing Sets with Linear Diagrams ACM TOCHI 22(6), 2015 http://dx.doi.org/10.1145/2810012