Evolutionary Graph Drawing Algorithms

In this paper, graph drawing algorithms based on genetic algorithms are designed for general undirected graphs and directed graphs. As being shown, graph drawing algorithms designed by genetic algorithms have the following advantages: the frames of the algorithms are unified, the method is simple, different algorithms may be attained by designing different objective functions, therefore enhance the reuse of the algorithms. Also, aesthetics or constrains may be added to satisfy different requirements.

A Graph Drawing Algorithm for Visualizing Multivariate Categorical Data

In this paper, a new approach for visualizing multivariate categorical data is presented. The approach uses a graph to represent multivariate categorical data and draws the graph in such a way that we can identify patterns, trends and relationship within the data. A mathematical model for the graph layout problem is deduced and a spectral graph drawing algorithm for visualizing multivariate categorical data is proposed. The experiments show that the drawings by the algorithm well capture the structures of multivariate categorical data and the computing speed is fast.

Social Choice Meets Graph Drawing: How to Get Subexponential Time Algorithms for Ranking and Drawing Problems

We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.

Toward automatic comparison of visualization techniques:Application to graph visualization

Many end-user evaluations of data visualization techniques have been run during the last decades.Their results are cornerstones to build efficient visualization systems.However,designing such an evaluation is always complex and time-consuming and may end in a lack of statistical evidence and reproducibility.We believe that modern and efficient computer vision techniques,such as deep convolutional neural networks(CNNs),may help visualization researchers to build and/or adjust their evaluation hypothesis.The basis of our idea is to train machine learning models on several visualization techniques to solve a specific task.Our assumption is that it is possible to compare the efficiency of visualization techniques based on the performance of their corresponding model.As current machine learning models are not able to strictly reflect human capabilities,including their imperfections,such results should be interpreted with caution.However,we think that using machine learning-based preevaluation,as a pre-process of standard user evaluations,should help researchers to perform a more exhaustive study of their design space.Thus,it should improve their final user evaluation by providing it better test cases.In this paper,we present the results of two experiments we have conducted to assess how correlated the performance of users and computer vision techniques can be.That study compares two mainstream graph visualization techniques:node-link(NL)and adjacency-matrix(AM)diagrams.Using two well-known deep convolutional neural networks,we partially reproduced user evaluations from Ghoniem et al.and from Okoe et al..These experiments showed that some user evaluation results can be reproduced automatically.

Inverse Markov Process Based Constrained Dynamic Graph Layout

In online dynamic graph drawing,constraints over nodes and node pairs help preserve a coherent mental map in a sequence of graphs.Defining the constraints is challenging due to the requirements of both preserving mental map and satisfying the visual aesthetics of a graph layout.Most existing algorithms basically depend on local changes but fail to do proper evaluations on the global propagation when setting constraints.To solve this problem,we introduce a heuristic model derived from PageRank which simulates the node movement as an inverse Markov process hence to give a global analysis of the layout's change,according to which different constraints can be set.These constraints,along with stress function,generate layouts maintaining spatial positions and shapes of relatively stable substructures between adjacent graphs.Experiments demonstrate that our method preserves both structure and position similarity to help users track graph changes visually.

Simple Algorithms for Network Visualization:A Tutorial

The graph drawing and information visualization communities have developed many sophisticated techniques for visualizing network data, often involving complicated algorithms that are difficult for the uninitiated to learn. This article is intended for beginners who are interested in programming their own network visualizations, or for those curious about some of the basic mechanics of graph visualization. Four easy-to-program network layout techniques are discussed, with details given for implementing each one： force-directed node-link diagrams, arc diagrams, adjacency matrices, and circular layouts. A Java applet demonstrating these layouts, with open source code, is available at http：//www.michaelmcguffin.com/research/simpleNetVis/. The end of this article also briefly surveys research topics in graph visualization, pointing readers to references for further reading.

A machine learning approach for predicting human shortest path task performance

Finding a shortest path for a given pair of vertices in a graph drawing is one of the fundamental tasks for qualitative evaluation of graph drawings.In this paper,we present the first machine learning approach to predict human shortest path task performance,including accuracy,response time,and mental effort.To predict the shortest path task performance,we utilize correlated quality metrics and the ground truth data from the shortest path experiments.Specifically,we introduce path faithfulness metrics and show strong correlations with the shortest path task performance.Moreover,to mitigate the problem of insufficient ground truth training data,we use the transfer learning method to pre-train our deep model,exploiting the correlated quality metrics.Experimental results using the ground truth human shortest path experiment data show that our models can successfully predict the shortest path task performance.In particular,model MSP achieves an MSE(i.e.,test mean square error)of 0.7243(i.e.,data range from−17.27 to 1.81)for prediction.