In this work, we propose a new strategy for graph drawing utilizing layouts of many sub-graphs supplied by a large group of people in a crowd sourcing manner. We developed an algorithm based on Laplacian constrained distance embedding to merge sub-graphs submitted by different users, while attempting to maintain the topological information of the individual input layouts. To facilitate collection of layouts from many people, a light-weight interactive system has been designed to enable convenient dynamic viewing, modification and traversing between layouts. Compared with other existing graph layout algorithms, our approach can achieve more aesthetic and meaningful layouts with high user preference.
Even though there are many existing automatic graph layout algorithms of different style, but together these may not satisfy the users' special needs. For example, if we want to force a ten-node circle in the layout, or achieve other specific topological structures when visualizing graphs from applications in chemistry or biology, the aforementioned automatic algorithms cannot retain such user defined local structures. Inspired by the scientific visualization literature where the Laplacian vector is used for mesh editing and deformation, we would like to maintain topological information of the user input subgraphs, we seek to preserve the distance between each pair of nodes in the user subgraphs, because by the knowing pairwise distances among all nodes in a subgraph, we can exactly realize the layout of the subgraph. In the following figure (a) is a simple graph, (b) is the coresponding Laplacian matrix, (c) the red nodes are edited by users and the dotted lines represent virtual edges, (d) is the Laplacian matrix embeded user input subgraph information.
Then we use the stress majorization technique to solve the following nonlinear system. It works as follows: starting from the initial layout of the whole graph |V|x2 matrix x in the right hand side of the linear system, we solve the linear system with given right-hand-side, and insert the solution again into the right hand side. This process is repeated until the layout stablizes.
Inorder to compare the effect of LCDE algorithm, we propose CFDP, a constrained force directed algorithm (Constrained Force Directed Placement algorithm). It replaces the ideal edge length of each pair of nodes by the distance of user defined subgraphs. Since CFDP maintains user input indirectedly through force coefficients, it's effect is not good as the LCDE. From the following case, we can see LCDE is better than CFDP algorithm.
This is a biochemical metabolic pathway. (a) left figure is a metabolic pathway from a textbook, middle figure are subgraphs from wikipedia, right figure are input subgraphs, (b) is a layout result by force-directed layout algorithm, (c) the layout result by CFDP algorithm, (d) the layout result by the LCDE algorithm with numbers indicating similarity scores. The background shadowed hulls in blue and pink indicate sbugraphs from (a) respectively. We easily recognize that the symbolic stick of Glycolysis process and cycles of Citric Acid Cycle are kept and LCDE is better than CLDP.
Based on this algorithm, we develop a Intelligent Graph Layout editing Tool(IGT), it can automatically generate the graph layout, and allows users to interactly edit subgraph layout, it also provides edge bundling function.
Video
Article
Software Download
Tutorial
Citation
Xiaoru Yuan, Limei Che, Yifan Hu, and Xin Zhang . Intelligent Graph Layout Using Many Users’ Input. IEEE Transactions on Visualization and Computer Graphics (InfoVis’12), 18(12):2699-2708, 2012.